1

If I have a language $L$ such that $L= \{xww^r \mid \text{ $x$ and $w$ belong to }(a+b)^+) \}$.

Then can't we write regular expression for this to be $(a+b)^+(ab+ba)$?
What's wrong in this regular expression ?

Also what if I have $L= \{wxw^r \mid \text{$x$ and $w$ belong to }(a+b)^+) \}$ or $L=\{ww^rx \mid \text{$x$ and $w$ belongs to }(a+b)^+) \}$

Does the position of $x$ affect the nature of the language ?

J.-E. Pin
  • 40,163
radhika
  • 361

2 Answers2

1

Hint. Take $x = w = a$. Does $xww^r$ match your regular expression?

J.-E. Pin
  • 40,163
1

HINT: J.-E. Pin has suggested why your regular expression doesn’t generate $L$. To prove that $L$ isn’t regular (and hence that no regular expression generates $L$), you can use the pumping lemma. If $p$ is the pumping length, let $w=a(ab)^p(ba)^p\in L$. If $L$ were regular, there would be a decomposition $w=xyz$ of $w$ such that $|y|\ge 1$, $|xy|\le p$, and $xy^kz\in L$ for all $k\ge 0$. Since $1\le |xy|\le p$, while $|a(ab)^p|=2p+1$, we know that $xy$ has the form $a(ab)^\ell$ or $a(ab)^\ell a$ for some $k\ge 0$.

  • Determine the possible forms of $y$.
  • Then show that no matter what form $y$ has, the word $xz=xy^0z\notin L$.
Brian M. Scott
  • 616,228
  • For this particular $w = a(ab)^p(ba)^p$, could I not pick $y$ as simply $a$ and pump it? The result would still be $(a + b)^+ w w^R$? (I'm setting $\ell = 0$ in one of your forms) – sprajagopal Jan 08 '21 at 11:12
  • 1
    @sprajagopal: If $y$ is the initial $a$, you get $(ab)^p(ba)^p$, which is not in $L$: $L$ requires that $x$ be non-empty. And if $y$ is an $a$ in $(ab)^p$, either it’s the first $a$, which has the same problem, or no suffix of the resulting word has the form $ww^r$. – Brian M. Scott Jan 08 '21 at 22:11