PDA for a language where the second part is not the reverse of the first part 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 &quot;$k$&quot; 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$.