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

enter image description here

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

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


2) S->aaB


3) S->aaB|a


4) S->aB


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.


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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.