Prove, that $L:=\{w\cdot d\cdot \overleftarrow{w}\mid w\in \{a,b\}^+\}$ is not regular using the pumping-lemma

29 Views Asked by At

Let $\Sigma =\{a,b,d\}$. Prove, that $L:=\{w\cdot d\cdot \overleftarrow{w}\mid w\in \{a,b\}^+\}$ is not regular over $\Sigma$.
Definition: $\overleftarrow{w}$ is defined inductively:$\overleftarrow{\lambda}:=\lambda,\; \overleftarrow{v\cdot x}:=x\cdot \overleftarrow{v}$, with $x\in\Sigma$ and $v\in\Sigma^*$

I know the basic idea of the pumping lemma got explained here, but I wouldn't know if my solution is correct, that's why I am asking for help regarding whether this proof of mine is correct or not.


Assume, $L$ is regular. Let $n\in\mathbb{N}$ be the pumping-length and $w'=w\cdot d\cdot \overleftarrow{w}$ with ${\mid w\mid} = n$, $w'\in L$.

EDIT: This is wrong, because $"d"$ is just one letter and not a word, I will edit it as soon as possible.

No matter, how we partition $w'$ into 3 parts $w'=xyz$ with $x,y,z\in\Sigma^*$, we always have $x$ and $y$ only contain characters of word $w$, because ${\mid xy\mid}\leq n$.
Let ${\mid x\mid}=l$, ${\mid y\mid}=k$ and ${\mid z\mid}={\mid w\mid}-l-k+{\mid d\mid}+{\mid w\mid}$ with $l,k\in \mathbb{N}:l+k\leq n$.
For $i=2$, we have $$xy^2z=l+2k+{\mid w\mid}-l-k+{\mid d\mid}+{\mid w\mid}$$, which is equal to $k+n+c+n$, where $k+n>n$, because $k>0$. That means, that ${\mid y+w\mid}>{\mid w\mid}$. Therefore, the first word $w$ contains more characters than $\overleftarrow{w}$, which means $xy^2z\notin L$.

Edit2: Because my first solution is wrong, here is a second thought:

Let $L$ be regular and $n$ be the pumping length. We choose $w=a^n\cdot d\cdot a^n$. Now we can show that this doesn't satisfy the pumping lemma similar to $L=\{a^nb^n\mid n\in\mathbb{N}\}$ Is this ok?

1

There are 1 best solutions below

1
On BEST ANSWER

Your argument is not correct, since it is only based on the length of words and does not depend on the alphabet. If it was correct, it would work for $\Sigma = \{a\}$ and prove that the language $L =\{w\cdot d\cdot \overleftarrow{w}\mid w\in \{a\}^+\}$, where $d$ is some fixed word of $a^*$, is not regular. But this language is regular.

Edit. In answer to your Edit2, yes, you can use this argument. More precisely, suppose that $L$ is regular, then $L \cap a^+da^+ = \{a^nda^n \mid n > 0\}$ would be regular and then you can use the pumping lemma to conclude that it is not the case.