Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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$.
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.
