Pumping Lemma Proof (Type of wcw language)

Question

I have the language $L = \{ dkd\space \mid d \in \{a,b\}^*, k \in \{a,b\} \}$ and i have to show that it's non-regular using the pumping lemma.

The structure of the language i think can be explained as (based on definition above) $\{a^{n}b^{n}ca^{n}b^{n} \mid c \in \{a,b\}\}$

Based on pumping lemma, it must have this 3 properties:

1. $\lvert y \rvert \gt 0$
2. $\lvert xy \rvert \le p$
3. $xy^iz\in L$ for all $i \ge 0$.

Based on that, i have $a^{p}b^{p}ca^{p}b^{p}$ and $ 4p+1 \ge p $ Based on 2nd property there must be 9 scenarios (i guessed that from the theory):

One of them should be this one:

1. x = $\{a^{i}$} $\space $ y = $a^{p-i}$ $\space$ z= $b^{p}ca^{p}b^{p}$

Based on the 3rd property i can use $xy^{2}z$ = $a^{i}$$a^{p-i}$$a^{p-i}$$b^{p}ca^{p}b^{p}$ eventually giving me $a^{p}$$a^{p-i}$$b^{p}ca^{p}b^{p}$, the explaination is: it fails since $a$'s of the start arent the same (in number) with the $a$'s of the end.

If the above is correct how i find the other 8 scenarios and it does make any difference that my $c$ is ($a$ or $b$) instead of a single constant character?

Answer 1

The structure of the language i think can be explained as (based on definition above) $\{a^n b^n ~c~ a^n b^n |c \in \{a,b\} \}$

As explained in the comments, this is a wrong inference. If

$$ L = \left \{ d k d ~|~ d \in \{ a, b \}^{*}, k \in \{a, b\} \right \} $$

then $d$ can be any finite sequence (of any length) of $a$ or $b$ terminals. Recall that, for an alphabet $\Sigma$, Kleene star is defined inductively as

\begin{align} \Sigma^0 & = \{ \epsilon \} \\ \Sigma^n & = \{ \omega a ~|~ \omega \in \Sigma^{n - 1}, a \in \Sigma \} \\ \Sigma^{*} & = \bigcup_{n \ge 0}{\Sigma^n} \end{align}

So for example

$$ \{ \epsilon, a, b, ab, ba, abab, abbb, baba \} \subset \{ a, b \} ^{*} $$

while instead

$$ \{ a^n b^n | n \ge 0 \} = \{ \epsilon, ab, aabb, aaabbb, \ldots \} $$

To tackle your problem, I can recommend negating the Pumping lemma and then

• Fix an arbitrary $N > 0$
• Take $\omega = a^N b a^N$ with $d = a^N$ and $k = b$
• Equate $\omega = xyz$ and note that it must be $|xy| \le N$ and $|y| > 0$

Can you conclude your proof?

We just chose our $\omega \in L$. We must show that, whatever our decomposition, $\exists k \ge 0. ~ x y^k z \not \in L$. Let $x, y, z$ be such that \begin{cases} \omega & = xyz \\ |xy| & \le N \\ |y| & > 0 \end{cases} then, whatever $y$, for $k = 0$ you always have \begin{equation} x y^0 z = a^M b a^N \end{equation} with $M \neq N$. Thanks @plop for strenghening the proof.