Monash University FIT2014 Assignment 2

Due: 11:55pm, Friday 4 October 2024

1. Introduction

   In this assignment, you will:

   Implement a lexical analyser using lex (Problem 3).

   Implement parsers using lex and yacc (Problems 1 – 6). Program a Turing machine (Problem 7).

   Learn about some aspects of quantum circuits and quantum registers (Problems 2 – 6). Practise skills related to Pumping Lemmas and Context – Free Languages (Problem 8).

2. Assignment Management

   Start working early and spread the work over time. Do as much as possible before week 10. Don’t be deterred by the length of the document. Much of it is a tutorial and documentation.

3. How to Begin

   1. Download the workbench asgn2.zip from Moodle.

   2. Create a new Ed Workspace and upload the file, let Ed extract it.

   3. Edit the student – id file with your name and student ID.

   4. Open a terminal and change into the asgn2 directory.

4. Files in the Directory

   plus – times – power.l : Starting point for some lex files. plus – times – power.y : Starting point for some yacc files. quant.h : Should remain unaltered.

   prob6.awk : An awk program for a specific task.

5. Submission Requirements

   Your submission must include:

   student – id file edited with your name and student ID.

   prob1.l : Obtained by modifying a copy of plus – times – power.l .

   prob2.pdf : Your solution to Problem 2 (Context – Free Grammar for QCIRC).

   prob3.l : Obtained by modifying a copy of plus – times – power.l .

   prob4.l : Obtained by modifying a copy of prob3.l .

   prob4.y : Obtained by modifying a copy of plus – times – power.y .

   prob5.l : Obtained by modifying a copy of prob4.l . prob5.y : Obtained by modifying a copy of prob4.y . prob6.txt : Ten lines, solution to Problem 6.

   prob7.tm : Tuatara Turing machine file.

   prob8.pdf : Your solution to Problem 8.

6. Assignment Tasks

   Problem 1 (2 marks)

   Construct prob1.l to be used with plus – times – power.y to build a parser for PLUS – TIMES – POWER.

   Problem 2 (3 marks)

   Write a Context – Free Grammar for the language QCIRC over the alphabet {I, H, X, Y, Z, CNOT, TOF,

   *, , (, ) } and save it as prob2.pdf .

   Problem 3 (3 marks)

   Construct a lex file prob3.l starting from plus – times – power.l to build a lexical analyser for QCIRC.

   Problem 4 (6 marks)

   Make a copy of prob3.l called prob4.l and modify it for use with yacc. Construct a yacc file prob4.y from plus – times – power.y .

   Build a parser for QCIRC that can evaluate expressions.

   Problem 5 (5 marks)

   Make copies of prob4.l and prob4.y called prob5.l and prob5.y respectively. Modify them further to build a parser for QUANT.

   Problem 6 (5 marks)

   Use the prob6.awk program to convert your student ID to a quantum register expression. Copy the expression into prob6.txt as the first line.

   Run your parser on the expression and append the result to prob6.txt .

   Problem 7 (7 marks)

   Build a Turing machine in Tuatara v2.1 that computes the number choice function and save it as

   prob7.tm .

   Problem 8 (9 marks)

   Prove there is no Universal Regular Expression using the Pumping lemma for Regular Languages.

   Prove there is no Universal Context – Free Grammar using the Pumping lemma for Context – Free Languages. Save the proof as prob8.pdf .

7. Lex and Yacc Basics

   Lex

   An input file to lex ends in .l and has three parts: definitions, rules, C code.

   The plus – times – power.l file is used as an example. It identifies tokens like nonnegative integers (NUMBER), Power (POWER), and specific characters.

   When lex runs on the file, it generates lex.yy.c which can be compiled to create a lexical analyser.

   Yacc

   An input file for yacc ends in .y and has three parts: declarations, rules, programs.

   The plus – times – power.y file is used as an example. It has a grammar for PLUS – TIMES – POWER and declarations for tokens and nonterminals.

   To generate a parser, you need to modify prob1.l and use plus – times – power.y along with some compilation steps.

8. Quantum Circuits and Registers

   A quantum computer uses quantum physics for computation.

   It has a register that stores information in a superposition and a quantum circuit expression that transforms the register.

   The languages QCIRC, QREG, and QUANT are defined to describe quantum expressions.

   QCIRC is for valid quantum circuit expressions, QREG for valid quantum register expressions, and QUANT is their union.

9. The Number Choice Function

   Input: A sequence k, x1, x2, …, xn encoded as akbax1 bax2 b ⋯ axn . Output: xk encoded as axk .

   A Turing machine for this function should reject invalid inputs.

10. Universal Models

Universal regular expressions and universal context – free grammars are defined.

The goal is to find expressions/grammars that can match/generate all relevant strings for a given set of regular expressions/context – free grammars.