0
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ In the definition of $L$ they say that $d$ can be any word in $\{a,b\}^*$. Those are any words in the letters $a$ and $b$, not only those of the form $a^nb^n$. $\endgroup$ – plop Mar 1 at 17:28
  • $\begingroup$ So how that would look compare to what i wrote? Also based on that is my thinking correct? $\endgroup$ – Demokles Mar 1 at 17:31
  • $\begingroup$ Just the definition of $L$, as written, is a good description of what $L$ is. The re-phrasing that you wrote is not the same language. Now, when applying the pumping lemma you can restrict yourself to any word $w\in L$ that is convenient to you, as long as $|w|\geq p$. Since you can do that, I would go for even simpler words, like $w=a^pba^p$. $\endgroup$ – plop Mar 1 at 17:35
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ The argument in the spoiler is not correct. For example, maybe $w=aaaaa$, with $d=aa$ and $k=a$, $N=3$, $x=a$, $y=aa$ and $z=aa$. Then $xy^0z=aaa$, which is in $L$. I think you assumed that when testing if $xy^0z$ is in $L$ the $k$ and the $d$ need to be the same as for $xyz$, but this is not required. $\endgroup$ – plop Mar 1 at 22:19
  • $\begingroup$ To fix the argument, observe that the word in the conclusion of the pumping lemma is arbitrary, as long as it is long enough. Therefore, to show that the negation of the conclusion of the pumping lemma is satisfied, you can just exhibit a conveniently chosen word. Since you can choose it, just take a word that forces what should be the $k$. For example, $w=a^Nba^N$. This forces a factorization $w=xyz$ with $x=a^m,y = a^{n}$ and $z=a^{N-m-n}ba^N$. $\endgroup$ – plop Mar 1 at 22:24
  • $\begingroup$ Thanks @plop, I should have fixed it. I assume you wanted to say $N = 2$ in your first comment right? That doesn't make a difference anyway. $\endgroup$ – Acsor Mar 2 at 7:58

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.