Assignment 1 
------------

Part A (conceptual)
-------------------

1. a) Generate a nondeterministic finite automaton that recognizes the
language described by the regular expression ab {a,b}* ba {a,b}* ab

b) Generate a deterministic finite automaton for the  same language.

2. Write context free grammars, if possible, for the following
   languages. If it is not possible to write a context free grammar
   for the given language, explain clearly why not.

a) {a^n b^m, where m >= n}

b) {a^n b^m, where m < n }

c) The set of all palindromes, of both even and odd length,
constructed with the alphabet {a, b}

3. Solve the following exercises from the textbook. 

a)  2.3c
b)  2.4 (for 2.3c only)
c)  2.7

Part B (computer)
-----------------

5. Use the UNIX commands grep and wc to count the number of lines in
file ~eem/www/3136/file.txt that contain the word "shape" in singular
or plural, capitalized or not, as an independent word or as a
hyphenated element of a composite word (e.g. shape-based).

6. Read the online lex and yacc tutorial in
 http://epaperpress.com/lexandyacc/index.html

In http://www.cs.dal.ca/~eem/3136/lexYacc/
files arith.l and arith.y are the lex and yacc sources for a
simple arithmetic expression parser/calculator similar to that
described in the tutorial under yacc/practice II. 
Command "make all" will create the executable file "arith".
Executing "arith" runs an expression interpreter: type an
expression to it and see the result.

Modify the given sources arith.l and arith.y as needed to print the
parse tree for a given expression. For full credit, explain clearly
your modifications.

Show the output of your program (i.e. the parse tree) for the
expression     2 + 3 * (4 + 1)

Print the parse tree in the simplest possible way. Graphics is not
required, only some textual output that conveys the shape of the tree
via indentation whose depth that depends on the depth of the node in
the tree would be sufficient.
Feel free to add lines with a pencil to link nodes of the tree in your
printed output.

Hint: You need to modify the C program fragments in arith.y. You may
find it useful to introduce a global integer variable (in the first
section of arith.y) that keeps track of the level of indentation, or
equivalently the depth of recursion of the call to "evaluate".