1
$\begingroup$

I know a regular language is the one which can be expressed as a regular expression or we can create a DFA corresponding to it. Unless a language has a pattern in which one part has to match with other like in $$a^nb^n|n\geq 0 (CFG)$$ It'll be regular. Like AP Series of symbols can be easily expressed as Regular expression but GP Series can not.

But I failed to understand why the following languages are regular

$L_1=\{wxw^R \mid w,x \in (a,b)^+\}$

$L_2=\{wxwy \mid w,x,y \in (a,b)^+\}$

$L_3=\{xwyw \mid w,x,y \in (a,b)^+\}$

Improve this question
$\endgroup$
3
  • $\begingroup$ See a very similar question here, where it is explained how both $L_2$ are indeed regular, as you can take very short strings $w$. $\endgroup$
    – Hendrik Jan
    Jan 24 '15 at 12:59
  • $\begingroup$ @DaveClarke - I think all of them are regular, as $w$ could be a single letter.. $\endgroup$
    – R B
    Jan 25 '15 at 14:11
  • 1
    $\begingroup$ You are making a confusion between languages and grammars. There are no grammars in your question. $\endgroup$
    – J.-E. Pin
    Jan 27 '15 at 12:25
0
$\begingroup$

All these languages are regular. This comes from the fact $w$ could simply be a single letter, and thus the languages admit the following regular expressions (assuming here $\Sigma=\{a,b\}$, but this would work for any finite alphabet):

$$L_1=a(a+b)^+a+b(a+b)^+b$$ $$L_2=a(a+b)^+a(a+b)^++b(a+b)^+b(a+b)^+$$ $$L_2=(a+b)^+a(a+b)^+a+(a+b)^+b(a+b)^+b$$

A more detailed explanation:

In the definition we had: $w\in\{a,b\}^+$.

This mean that $w$ could be a single letter, $a$, or $b$, and thus we can attribute the rest of the word to $x$ (or $y$).

For example, if: $$u=abbababa\in L_1$$, because it can be decomposed as $w=a, x=bbabab$ and $$u=wxw^R$$. Similarly, each word which starts and ends with a $a$ is in $L_1$ (pick $w=a$), and each word that starts and ends with a $b$ is also in $L_1$ (pick $w=b$). This is why $$L_1=\{axa|x\in\{a,b\}^+\}\cup\{bxb|x\in\{a,b\}^+\}$$, and thus regular. Same tricks apply to the other languages and all three are indeed regular (by the regex I gave).

Improve this answer
$\endgroup$
16
  • $\begingroup$ What does it mean to say 'w' can be a single letter, Please explain in details $\endgroup$
    – Atinesh
    Jan 27 '15 at 11:56
  • $\begingroup$ @Atinesh, in your definition: $w\in\{a,b\}^+$. This mean that $w$ could be a single letter, $a$, or $b$, and we can attribute the rest of the word to $x$ (or $y$). For example: $u=abbababa\in L_1$, because it can be decomposed as $w=a, x=bbabab$ and $u=wxw^R$. Similarly, each word which starts and ends with a $a$ is in $L_1$ (pick $w=a$), and each word that starts and ends with a $b$ is also in $L_1$ (pick $w=b$). This is why $L_1=\{axa|x\in\{a,b\}^*\}\cup\{bxb|x\in\{a,b\}^*\}$, and thus regular. Same tricks apply to the other languages and all three are indeed regular (by the regex I gave). $\endgroup$
    – R B
    Jan 27 '15 at 12:06
  • $\begingroup$ Thanks RB now I get this concept, but lets modify the regular expression little bit suppose w,x,y belongs to (a+b)* then I think for L1 regular expression will be (a+b)* instead of a(a+b)*a+b(a+b)*b. $\endgroup$
    – Atinesh
    Jan 27 '15 at 12:19
  • $\begingroup$ @Atinesh - indeed. In fact, if we require $|w|\geq k $, for any fixed $k$, this is still regular ($^*$ is $k=0$, $^+$ is $k=1$). $\endgroup$
    – R B
    Jan 27 '15 at 12:23
  • $\begingroup$ And what about $L_2$ and $L_3$ in case of w,x,y$\in (a+b)^*$, Do they also have RE as $(a+b)^*$ $\endgroup$
    – Atinesh
    Jan 27 '15 at 12:26

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.