Finite Automata, Context-Free Languages, Lexical analysis, Parsing

In these exercises, you will
- implement lexical analysers using lex (Problem 3);
- implement parsers using lex and yacc (Problems 1, 4);
- practise using the Pumping Lemma for regular languages (Problem 2);
- build a Turing machine (Problem 5);
- learn more about Finite Automata and universality (Problems 6-7).

Solutions to Problem 5 must be implemented in the simulator tuataraMonash, which is avail- able on Moodle.

How to manage this assignment

You should start working on this assignment now, and spread the work over the time until it is due. Aim to do at least three questions before the mid-semester break. Do as much as possible before your week 10 prac class. There will not be time during the class itself to do the assignment from scratch; there will only be time to get some help and clarification.

Don't be deterred by the length of this document! Much of it is an extended tutorial to get you started with lex and yacc (pp. 2-5) and documentation for functions, written in C, that are provided for you to use (pp. 5-7); some sample outputs also take up a fair bit of space. Although lex and yacc are new to you, the questions about them only require you to modify some existing input files for them rather than write your own input files from scratch.

Instructions
Instructions are as for Assignment 1, except that some of the filenames have changed. The file to download is now asgn2.tar.gz, and unpacking it will create the directory asgn2 within your FIT2014 directory. You need to construct new lex files, using chain.l as a starting point, for Problems 1, 3 & 4, and you'll need to construct a new yacc file from chain.y for Problem 4. Your submission must include (as well as the appropriate PDF files for the exercises requiring written solutions):
- a lex file prob1.l which should be obtained by modifying a copy of chain.l
- a lex file prob3.l which should also be obtained by modifying a copy of chain.l
- a lex file prob4.l which should be obtained by modifying a copy of prob3.l
- a yacc file prob4.y which should be obtained by modifying a copy of chain.y
- a Tuatara Turing machine file prob5.tm
PDF files for the exercises requiring written solutions, namely, prob1.pdf, prob2.pdf, prob6.pdf, and prob7.pdf.
To submit your work, simply enter the command ‘make' from within the asgn2 directory, and then submit the resulting .tar.gz file to Moodle. As last time, make sure that you have tested the submission mechanism and that you understand the effect of make on your directory tree.

INTRODUCTION: Lex, Yacc and the CHAIN language
In this part of the Assignment, you will use the lexical analyser generator lex or its variant flex, initially by itself, and then with the parser generator yacc.
Some useful references on Lex and Yacc:
- T. Niemann, Lex & Yacc Tutorial, http://epaperpress.com/lexandyacc/
- Doug Brown, John Levine, and Tony Mason, lex and yacc (2nd edn.), O'Reilly, 2012.
- the lex and yacc manpages
We will illustrate the use of these programs with a language CHAIN based on certain expressions involving strings. Then you will use lex and yacc on a language CRYPT of expressions based on cryptographic operations.

CHAIN
The language CHAIN consists of expressions of the following type. An expression consists of a number of terms, with # between each pair of consecutive terms, where each term is either a string of lower-case letters or an application of the Reverse function to such a string. Examples of such expressions include
mala # y # Reverse(mala)
block # drive # cut # pull # hook # sweep # Reverse(sweep) Reverse(side) # Reverse(direction) # Reverse(gear)
For lexical analysis, we wish to treat every lower-case alphabetical string as a lexeme for the token STRING, and the word Reverse as a lexeme for the token REVERSE.

Lex
An input file to lex is, by convention, given a name ending in .l. Such a file has three parts:
- definitions,
- rules,
- C code.
These are separated by double-percent, . Comments begin with /* and end with */. Any comments are ignored when lex is run on the file.
You will find an input file, chain.l, among the files for this Assignment. Study its structure now, identifying the three sections and noticing that various pieces of code have been commented out. Those pieces of code are not needed yet, but some will be needed later.
We focus mainly on the Rules section, in the middle of the file. It consists of a series of statements of the form
pattern { action }
where the pattern is a regular expression and the action consists of instructions, written in C, specifying what to do with text that matches the pattern.1 In our file, each pattern represents a set of possible lexemes which we wish to identify. These are:
- a string of lower-case letters;
- This is taken to be an instance of the token STRING (i.e., a lexeme for that token).

Problem 1.
(a) Construct prob1.l, as described above, so that it can be used with chain.y to build a parser for CHAIN.

(b) Show that the grammar for CHAIN given above is ambiguous.

(c) Find an equivalent grammar (i.e., one that generates the same language) that is not ambiguous.

Problem 2.
Prove that CRYPT is not regular.

Problem 3.
Using the file provided for CHAIN as a starting point, construct a lex file, prob3, and use it to build a lexical analyser for CRYPT.

Problem 4.
Make a copy of prob3.l, call it prob4.l, then modify it so that it can be used with yacc. Then construct a yacc file crypt.y from chain.y. Then use these lex and yacc files to build a parser for CRYPT.

Note that you do not have to program any of the cryptographic functions yourself. They have already been written: see the Programs section of the yacc file. The actions in your yacc file will need to call these functions, and you can do that by using the function call for reverse(. . . ) in chain.y as a template.

The core of your task is to write the grammar rules in the Rules section, in yacc format, with associated actions, using the examples in chain.y as a guide. You also need to do some modifications in the Declarations section to declare all tokens, using token, and declare all nonterminal symbols, using type.

Problem 5.
In this question, the Turing machine you build in Tuatara must have q1 as its Start State and q2 as its Accept State.

Build a Turing machine to compute the binary Vigenere cypher. Its input has the form xyk where the character y is used simply to separate the binary strings x and k. The output consists simply of the cyphertext z, a binary string of n bits. The output should have no y and/or keybits k after the cyphertext.

Your work on Tute 5, Q8, should help you get started on this Problem.

Problem 6.
Prove that a language is regular if and only if it is accepted by a Multistart FA.

Problem 7.

(a) Show that FA-REP is regular by giving a regular expression for it.

(b) Does a UFA exist? Give a proof for your answer. (It should help to use Problem 6 at some point.)