If w,x,y ∈ (a+b)^+

1)L=wxwy 2)L=xwyw 3)L=wxyw

According to me all of them should be non-regular since we can't actually check what will be the starting symbol of first occurrence of w since it will be present at the bottom of the stack so we can't compare it with the first symbol of second occurrence of w , Am I thinking in the right direction or not ?


I assume that $w, x,y $ are not just fixed nonempty strings, otherwise all three of these languages contains one string (and is therefore regular). More precisely, then,

  1. $L = \{wxwy\mid w,x,y\in (a+b)^*\}$

and similarly for 2. and 3.

You're thinking in the right direction, yes — you need to remember $w$, somehow, in order to recognize these languages; however, in all cases the first occurrence of $w$ can be arbitrarily far away from the second occurrence. However, a finite automaton can only remember things using its finitely many states, there's no stack or any other auxiliary storage.

The Pumping Lemma for regular languages makes this intuition sharp and provides the right tool for proving that none of these languages are regular. Strong form of Pumping Lemma:

For any regular language $L$, there is an integer $p\ge 1$ such that for any string $s\in L$ (and for all strings $x,y,z$), if $s=xyz$ with $|y|\ge p$, then there are strings $u,v,w$ such that

  • $y=uvw$,
  • $|v|\ge 1$, and
  • for all integers $k\ge 0$, $xuv^kvz\in L$.

That is, for any string $s\in L$, if $s$ is long enough, then any substring of $s$ that's long enough has a substring that can be "pumped" so that the resulting string is also in the language.

Given this, we can show that the language $L$ of 1. is not regular. Every string $s_n = a^nba^nb$ is in $L$, for $n>0$. If $L$ is regular, let $p$ be as given by the pumping lemma. Consider $s_p$. Then the initial prefix $a^p$ has a substring that can be pumped: for some $i>0$, $a^p = a^ha^ia^j$ (for some $h,i,j$ with $h+i+j=p$), and for all $k$, $a^ha^{ik}a^jba^pb\in L$. But $a^ha^{ik}a^jba^pb = a^{p-i}a^{ik}ba^pb$, so for $k=2$ this string equals $a^pa^iba^pb$, which has too many $a$s before the first $b$ and thus is not in $L$ — contradiction.


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.