Understanding Regular Grammers

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)^+\}$

• 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$. Jan 24 '15 at 12:59
• @DaveClarke - I think all of them are regular, as $w$ could be a single letter..
– R B
Jan 25 '15 at 14:11
• You are making a confusion between languages and grammars. There are no grammars in your question. Jan 27 '15 at 12:25

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

• What does it mean to say 'w' can be a single letter, Please explain in details Jan 27 '15 at 11:56
• @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).
– R B
Jan 27 '15 at 12:06
• 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. Jan 27 '15 at 12:19
• @Atinesh - indeed. In fact, if we require $|w|\geq k$, for any fixed $k$, this is still regular ($^*$ is $k=0$, $^+$ is $k=1$).
– R B
Jan 27 '15 at 12:23
• 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)^*$ Jan 27 '15 at 12:26