PDA for a language where the second part is not the reverse of the first part

Question

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!

Answer 1

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$.

Answer 2

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.

Answer 3

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$.