The language is { (a | b)^n c (a | b)^n | n>=1 }

abab c baba

aaaa c bbbb

Try the PDA-FS on abcaaa

Give the state and the stack for each char read until the PDA stops and REJECTS the input.

Char -> State Stack content

a

------------------------------------------------------------------------------------------------------------

) For the partial PDA you have designed above, finish it as a PDA-ES.

i) For PDA-ES: what should you do if you see Z on the top of the stack in q1?

(Hint: this means you have popped off all Xs). Describe:

j) Give the Trs to do this. Note that you do not read any input.

Trs(

k) Under what circumstance does this PDA-ES stop and accept?

Describe in English.

Remaining input is:

Stack is:

l) Try the PDA on abcaaa

Give the state and the top of stack for each char read until the PDA stops and REJECTS the input.

Char -> State Stack content

a

m) Is this PDA-ES deterministic? Explain.