Pushdown Automata and Challenge in Grammar

Question

I read one old-midterm exam on Automata. consider:

the language that accepted by above pushdown automata is not generated by which of the following grammar?

1) S->aBaa|a$\epsilon$

aB->aS|$\epsilon$

2) S->aaB

aB->aaaB|$\epsilon$

3) S->aaB|a

aB->aaB|$\epsilon$

4) S->aB

B->aaB|$\epsilon$

i think (3) is true, but when we try to solve it with my friends, we think 1 and 3 is true? any hint or idea with detail highly appriciated.

thanks to all.

Answer 1

I'm not sure what your transition notation is for the automaton, but approaching it just as a "What's the odd grammar out?" question:

1. We can inline to get $S \rightarrow aSaa \mid aa \mid a$ and see that the language it generates is $L_1 = \{ a^n \mid n \not\equiv 0\pmod 3\}$
2. We can rewrite as $S \rightarrow aC$, $C \rightarrow aaC \mid \varepsilon$ and see that the language it generates is $L_2 = \{ a^n \mid n \equiv 1\pmod 2\}$
3. We can rewrite as $S \rightarrow aC$, $C \rightarrow aC \mid \varepsilon$ and see that the language it generates is $L_3 = \{ a^n \mid n > 0\}$
4. This is the same as our rewritten version of 2, so $L_4 = L_2$.

Thus you and your friends are correct that there is some mistake in the question. There is one obvious candidate. The production in the first grammar $S \rightarrow aBaa \mid a\varepsilon$ is very suspicious. $a\varepsilon$ is just $a$: the point of $\varepsilon$ is to be a placeholder when there's no other symbol in the string. I would double-check that production.