In homework we got to build a pushdown automaton for 2 languages, but in my opinion these are two exercises for which the automaton is the same for both.
As I understand it, we can build a non-deterministic pushdown automaton, and each time we read the character a, we can insert either a single A or twice A – at the 'discretion' of the automaton.
Next, a state is built for the character b, which each time he reads A he will pull it out of the stack.
In this way, the automaton knows how to handle both languages where the amount of a is equal to the amount of b, and also languages where like a is twice the amount of b.
Am I right? Or am I missing something?
If not, I would love to understand how to deal with the “or” condition in the first exercise.
Thank you.
Best Answer
Since $L_2\ne L_3$, they clearly cannot be accepted by the same pushdown automaton. It sounds like you have in mind an automaton that recognizes $L_3$. Probably the easiest way to design one to recognize $L_2$, is to design two deterministic pushdown automata, one for $\{a^nb^n:n\in\Bbb N\}$ and one for $\{a^{2n}b^n:n\in\Bbb N\}$. Then combine them into a single pushdown automaton that has transitions $\langle q_0,\varepsilon,Z,q_1,Z\rangle$ and $\langle q_0,\varepsilon,Z,q_2,Z\rangle$, where $q_0$ is the initial state of the combined PDA, $Z$ is the initial stack symbol, and $q_1$ and $q_2$ are the initial states of the two subsidiary pushdown automata. In other words, the first thing that the combined PDA does is ‘choose’ whether to look for a word of the type $a^nb^n$ or a word of the type $a^{2n}b^n$, and then it pursues that choice deterministically.