Question

Which of the following languages is/are regular ?

$L_1:\{wx{w}^R\mid w,xϵ{\{a,b\}}^{\ast }and\mid w\mid ,\mid x\mid >0\}$ $w^R$ is the reverse of string w

$L_2:\{a^n{b}^m\mid m\ne nandm,n\ge 0\}$

$L_3:\{a^p{b}^q{c}^r\mid p,q,r\ge 0\}$

Answer 1

$L^1=\{wx{w}^R\mid w,xϵ{\{a,b\}}^{\ast }and\mid w\mid ,\mid x\mid >0\}$

w cannot be put as "$ϵ$ " since $\mid w\mid >0.$ So we put w as its smallest string which is 'a' and 'b' and get the regular expression:


$r=a(a+b{)}^{+}a+b(a+b{)}^{+}b.$

Now putting w as any other string like say "ab" will not add any new string to the expression r. since any such string so generated will be either already generated by either $a(a+b{)}^{+}a$ or $b(a+b{)}^{+}b$

So the given language = $a(a+b{)}^{+}a+b(a+b{)}^{+}b$ which is clearly regular.

$\therefore L_{1}isregular$

$L_2=\{a^n{b}^m\mid m\ne n\}.$ This language has infinite comparision between number of a's and b's. $L_2$ is not regular language.

$L_3:\{a^p{b}^q{c}^r\mid P,q,r\ge 0\}$ = $a^{\ast }{b}^{\ast }{c}^{\ast }$ is a regular language.