Distributed: Published on the web on November 6.

Due: November 17 (in class).

Total maximum score: 100 points.

The purpose of this assignment is to to provide experience with context-free languages and with Pushdown automata.

Please write your solutions as clearly and concisely as possible.

- (50 pts)
For each of the following languages, give a pushdown automaton that accepts it,
and say whether the automaton is deterministic or not.
Try to give a deterministic automaton whenever possible.
- L = L(G) where G is the grammar
S -> lambda | ( S ) S

Note: L is the language of the balanced parentheses. - L = { x in {a,b}
^{*}| #_{a}(x) = #_{b}(x) } - L = { a
^{n}x | n >=0, x in {a,b}^{*}, and |x| = n } where "n >= 0" means "n greater than or equal to 0", and |x| is the length of x.

- L = L(G) where G is the grammar
- (50 pts)
For each of the following languages, say whether it is context-free
or not, and prove your answer. (If the language is context-free, the proof
can be done by defining the corresponding CFG or PDA. If the language is not
context-free, the proof can be done as a proof-by-contadiction via the
pumping lemma.)
- L = {a
^{n}b^{n}a^{n}| n >= 0} - L = {a
^{n}a^{n}b^{n}| n >= 0} - L = {xx
^{~}| x in {a,b}^{*}} where x^{~}represents the string obtained from x by changing all a's in b's and viceversa. Example: if x = aaba then x^{~}= bbab

- L = {a