Pda... questions


show that {anbn | n>=1} U {amb2m| m>=1} cannot be accepted by a deterministic pda.


Only Context Free Languages are accepted by Pushdown Automata. So, here you actually have to proove that the given language is not context free. That means you need to apply Pumping lemma for context free language in this question. If you don’t know pumping lemma for CFL, then you can learn it from the following links:

To see an example:


A determistic machine can’t have two paths for an input . It has to be unique. In this language, for b it has to take two paths … one for checking a = b and other for a = 2b.