Regular Languages, Context-Free Languages, Pushdown Automata,
Lexical analysis, Parsing, and Turing machines
DUE: 11:55pm, Friday 11 October 2019
In these exercises, you will
implement lexical analysers using lex (Problem 3);
implement parsers using lex and yacc (Problems 1, 4);
practise proof by induction (Problem 2);
practise using the Pumping Lemma for regular languages (Problem 7);
learn some more about Turing machines (Problem 5);
learn more about Pushdown Automata (Problems 67).
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.
Dont be deterred by the length of this document! Much of it is an extended tutorial to get
you started with lex and yacc (pp. 25) and documentation for functions, written in C, that
are provided for you to use (pp. 57); 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 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 youll 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
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
PDF files for the exercises requiring written solutions, namely, prob1.pdf, prob2.pdf, prob5.pdf,
prob6.pdf, and prob7.pdf.