consider the PDA given below we need to find the language accepted by the given PDA

$L$ is the language accepted by the above PDA :
$L = \{a^n\mid n\geq 0\}\cup\{a^n b^n\mid n\geq 0\}$ and is deterministic context-free is the language accepted by the PDA how can we accept $a^n$? As it doesn't contain an epsilon transition at the end right ? Is acceptance by both the final state and empty stack possible in the same PDA?


1 Answer 1


The PDA can accept $a^n$ because :

  1. Till we don't read a $b$, we stay in start state.
  2. The start state is a final state.

By acceptance by final state, the PDA accepts strings of the form $a^n$.

For strings $a^nb^n$, we have the following :

  1. $X^n$ is pushed on the stack, by reading $a^n$ and looping over the start state.
  2. For the first $b$, pop the stack, and continue to pop till we get only $Z$ in the stack.
  3. When only $Z$ remainded, we have only one choice to do, and even if it's an epsilon transition, because it's the only possible transition at this point, the automaton is still deterministic.

We have also here an acceptance by final state.

In addition, we can define both acceptance by final state and by empty stack on the same PDA, but generally, the two don't lead to the same language. For your language, acceptance by empty stack lead to an empty language, because the stack can never be empty.

  • $\begingroup$ sir but isn't an epsilon transition compulsory at the end of input ?? and can u please show some good source which shows we can define both acceptance by final state and by empty stack on the same PDA its new to me because i have not seen any such example before :/ $\endgroup$
    – venkat
    Commented Jan 23, 2018 at 12:17
  • $\begingroup$ I don't know what you mean by "a compulsory epsilon transition". For the source, there's the wikipedia article : en.wikipedia.org/wiki/Pushdown_automaton#Formal_definition (look at computations). $\endgroup$
    – user80502
    Commented Jan 23, 2018 at 15:16
  • $\begingroup$ sir what i am saying is the strings in PDA are assumed to be terminated by an epsilon right? so we define the move ε,Z/Z on the above PDA but similarly for strings of the language a^n also should be terminated by ε right but there was no ε move in the first state $\endgroup$
    – venkat
    Commented Jan 23, 2018 at 16:51
  • 1
    $\begingroup$ You can take the transition $\epsilon,Z/Z$ even if you aren't at the end of your string, you can take it everytime you want if you can. Also, the transition $\epsilon,Z/Z$ isn't necessary to accept the word, if you are in a final state, the word is accepted, even if you haven't gone through an epsilon transition. You should revise the basics of PDA acceptance. $\endgroup$
    – user80502
    Commented Jan 23, 2018 at 17:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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