I came across an exercise for constructing a PDA for the following language:

$$L = \{ncm \mid n,m\in\{a,b\}^* \text{ and } n \ne m^R\}.$$

Where $L \subseteq ({a,b,c})^*$

So $n$ and $m$ are both a combination of any number of $a$'s and $b$'s, but $n$ is not the reverse of $m$.

Does anyone have some tips or advice, would be much appreciated!


This answer is for the original version of the question, in which "$k$" was missing.

Your language contains all non-empty words. Indeed, if $w \neq \epsilon$ then you can write $w = nm$, where $m = \epsilon$ and $n = w \neq \epsilon = m^R$. In contrast, if $\epsilon = nm$ then $n=m=\epsilon$ and so necessarily $n=m^R$.

  • $\begingroup$ I edited, i forgot to add the k, my bad :$ $\endgroup$ – HenkieTee Sep 19 '20 at 15:28
  • $\begingroup$ Perhaps you can use the ideas in my answer to solve the new version of your question. $\endgroup$ – Yuval Filmus Sep 19 '20 at 15:30
  • $\begingroup$ I tried looking at it, but can not seem to find anything that enlightens me :( $\endgroup$ – HenkieTee Sep 19 '20 at 15:34
  • $\begingroup$ What is $k$? Is it a string? A new letter? Try to spend 10 minutes on making sure that you copied the exercise correctly. It's unreasonable for me to spend more time answering your question than you copying it correctly. $\endgroup$ – Yuval Filmus Sep 19 '20 at 15:36
  • $\begingroup$ Sorry for being unclear, k is a letter, perhaps I could've chosen 'c' to be more clear, my apologies $\endgroup$ – HenkieTee Sep 19 '20 at 15:38

Suppose that $w = ncm$, where $n \neq m^R$, say $n$'th $i$-th letter from the left, $\sigma$, differs from $m$'s $i$-th letter from the right, $\tau$. Then $$ w \in \Sigma^{i-1} \sigma \Sigma^* c \Sigma^* \tau \Sigma^{i-1}, $$ where $\Sigma = \{a,b\}$. Conversely, every $w$ of this form is in your language. You take it from here.


If you want to read a word $w$ with a PDA, and know if $w\in L$ or not, then you could:

  1. put the letters of $w$ in the stack of the PDA until you read a $c$;
  2. read the $c$ without changing the stack. If there is no $c$, then $w\notin L$;
  3. read the remaining of $w$:
    • if you read another $c$, then $w\notin L$;
    • if the stack is empty before the end of $w$, then $w\in L$;
    • if you reach the end of $w$ before the stack is empty, then $w\in L$;
    • if you reach the end of $w$ and the stack is empty, then $w\notin L$;
    • if the letter read in $w$ is different than the letter on the top of the stack, then $w\in L$;
    • if these letters are the same, then remove it from the stack and continue reading $w$.

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.