# Pushdown Automata Challenge

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.

my reasoning is:

(1) and (3) and (4) generates a, but (2) couldent generate a. PDA Language is {$a^n$ | n is odd}

thanks to all.

• Your "reasoning" is just a list of claims. What is your reasoning for them, respectively? – Raphael Aug 28 '14 at 12:52

You identified the language of the PDA correctly.

However, you misidentified the languages generated by the grammars:

Grammar 1 can generate $aa$ via $S \to aBaa$ and $aB \to \epsilon$.

Grammar 2 can generate $a$ via $S \to aaB$ and $aB\to \epsilon$. Also each application of $aB \to aaaB$ inbetween will add exactly 2 $a$'s. So grammar 2 generates the correct language.

Grammar 3 can generate $aa$ via $S\to aaB$, $aB\to aaB$, and $aB\to \epsilon$.

Grammar 4 is equivalent to grammar 2, except every intermediate sentential form is on $a$ shorter.

• Dear FrankW, you means just 2 is correct? – Mina Simin Aug 28 '14 at 10:13
• 2 and 4 generate the language of the PDA, so 1 and 3 are correct answers to the question. – FrankW Aug 28 '14 at 10:16