1

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.

enter image description here

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.

StevenU
  • 75
  • 6
  • 1
    Your confusion seems to be about "the discretion of the automaton". For $L_2$, the automaton should decide once and for all, at the start of the computation, whether to push one A or two A's whenever it reads an a. All the a's in the input produce the same number of pushes. For $L_3$, the automaton can make a different choice for each a that it reads. The "choose once and for all" version is described in more detail in Brian Scott's answer, whereas the "choose independently for each input a" version seems to be what you were thinking of. – Andreas Blass Aug 16 '20 at 02:44
  • Actually, your description of the automaton seems to have the roles of $n$ and $m$ reversed from the definitions of $L_2$ and $L_3$. But that's a relatively minor issue. – Andreas Blass Aug 16 '20 at 02:46

1 Answers1

2

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.

Brian M. Scott
  • 616,228