Fall 2000, CSE 468: Assignment 5

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.

  1. (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.

    1. L = L(G) where G is the grammar
         S -> lambda | ( S ) S
      Note: L is the language of the balanced parentheses.

    2. L = { x in {a,b}* | #a(x) = #b(x) }

    3. L = { anx | 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.

  2. (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.)

    1. L = {anbnan | n >= 0}

    2. L = {ananbn | n >= 0}

    3. 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