2
$\begingroup$

I would like to verify that the following language is not regular.

I know that if the pumping lemma is not valid then the language is not regular. (but its not enough to prove that the language is in fact regular if the pumping lemma is valid)

So, given the following language,

$\Sigma =\{a,b\}$, $L=\{v\cdot u\cdot u: v,u\in\Sigma^*,u\neq \varepsilon\}$

Can I show that the pumping lemma is not valid here?

Side note:

I think I can prove that this language is regular by using regular expressions like so:

denote $r= (a\cup b)^*$ now, $L=(a\cup b)^*\cdot (aa\cup bb)\cdot r\cdot r$

Is this true?

$\endgroup$
1
$\begingroup$

Your language is not regular. Indeed, let $n$ be the pumping lemma constant, and consider the word $ab^nab^na = a(b^na)^2 \in L$. Suppose that your language were regular. Then you could write $ab^nab^na = xyz$, where $|xy| \leq n$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$. We consider two cases:

  • Case 1: $x = \epsilon$, and so $y = ab^t$ for some $t \geq 0$. Then $xy^0z = b^{n-t}ab^na$. Suppose this were of the form $vu^2$. Considering the second copy of $u$, we see that $u$ ends in $a$. Since there are two copies of $a$, necessarily $u = b^na$. This is only possible if $t = 0$ (which is OK) and $v \neq \epsilon$ (which is not OK).

  • Case 2: $x = ab^t$, and so $y = b^s$ for some $t \geq 0$ and $s \geq 1$. Then $xy^0z = ab^{n-s}ab^na$. Suppose this were of the form $vu^2$. Since $v \neq \epsilon$, the word $u^2$ is a suffix of $b^{n-s}ab^na$, and so as before, necessarily $u = b^na$ and we reach a contradiction since $s \neq 0$.

Now, why does your regular expression $(a+b)^* (aa+bb) (a+b)^* (a+b)^*$ not work? You are implicitly assuming that if you write "$r \cdot r$" then the semantics are that the same word must be chosen twice. However, this need not be the case. For example, the word $aab$ matches your regular expression, but is not in $L$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ We don't verify correctness here. This is your TA's job. $\endgroup$ – Yuval Filmus Apr 25 at 14:02
0
$\begingroup$

Given the word $w = ab^p ab^p$, clearly $w\in L \land |w|=2\cdot(p+1)\geq p$.

Now, consider the division $w=xyz$ where $|xy|\leq p \land |y|>0$ then

  • Case 1: $x=\varepsilon$, $\forall s\geq0\ ,y=ab^s$ then if $i=0$ we get that $xy^0z$ is actually $b^{p-s}ab^p$ and that's clearly not in L, because of the '$a$' in the middle of the new word.

  • Case 2: $x\not=\varepsilon$ then $\forall s>0:\ y=b^s$ then again if $i=0$ we get that $xy^0z = ab^{p-s}ab^p$ and because $s>0$ then there is not a repeatable word (because $u=ab^p$ or $u=ab^{p-s}$) so we can conclude that $w\notin L$.

Thus $L\notin REG$.

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