Question

Give an example of a non-regular Context-Free Language that can be recognize by a Deterministic Pushdown automata and one that cannot.

Answer 1

Non regular context free language (NRCFL) is that which is Context free but not regular.

a) L={aⁿ bⁿ : n>0} is an example of NRCFL. It is not regular can be proved using pumping lemma for regular languages. It can be recognized by Deterministic push down automata. The steps would be push all a's to stack and pop a's for every corresponding b's. Empty stack or final state acceptability will hold.

b) L={w w^r: w belongs to {a,b}⁺} is an example of NRCFL. It is not regular can be proved using pumping lemma for regular languages. It cannot be recognized by Deterministic push down automata because you would never know when the mid of input string occurs. Like w=abab ww^r=ababbaba. You cant tell when mid occurs So deterministic PDA cannot recognize it.

For Non determistic PDA, the steps would be push characters to stack and when stack top and current character is same, there will be 2 paths, either to push character to stack assuming mid not reached or start popping character assuming this is the mid of input string.