I define language $L = \{a^k a^m b^m c^k \} \cup \{a^n b^n b^k c^k\}$ and I want to determine if it's deterministic context free language or it is nondeterministic. so I tried to create pushdown automata for this language like below.

first I read $a$ and push it to stack till it ends. right know number of $a$ in the stack is $x = k + m$ or $x = n$. now for each $b$ we can erase a $a$ from stack and there will appear tree case

  • case 1: stack will be empty and we can still read $b$ so the string should be in $\{a^n b^n b^k c^k\}$

  • case 2: stack will be contain some $a$s and string should be in $ \{a^k a^m b^m c^k \}$

  • case 3: stack will be empty and there is no $b$ to read so $k$ should be zero.

in case one we can push $b$ into stack and after that we have $k$, $b$s in the stack and we can pop each one of $b$ instead of reading a $c$. in case two the number of $a$ in the stack is $k$ and like case one read $c$ and pop $a$ until stack will be empty. so I think this $DPDA$ should accpet language $L$ but I heard from someone that this language is not deterministic context free language. is my $DPDA$ wrong? where is the problem?


1 Answer 1


The language that is usually cited as not accepted by any DPDA is $\{a^mb^nc^nd^m\} \cup \{a^mb^mc^nd^n\}$. This is because we don't know whether to push or pop when $b$ arrives. The language you describe seems to be accepted by the DPDA you have constructed.


Your Answer

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

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