1
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I edited, i forgot to add the k, my bad :$ $\endgroup$ – HenkieTee Sep 19 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 at 15:30
  • $\begingroup$ I tried looking at it, but can not seem to find anything that enlightens me :( $\endgroup$ – HenkieTee Sep 19 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 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 at 15:38
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.