# 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 "$$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$$.
• I edited, i forgot to add the k, my bad :$– HenkieTee Sep 19 at 15:28 • Perhaps you can use the ideas in my answer to solve the new version of your question. – Yuval Filmus Sep 19 at 15:30 • I tried looking at it, but can not seem to find anything that enlightens me :( – HenkieTee Sep 19 at 15:34 • 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. – Yuval Filmus Sep 19 at 15:36
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.