edited by
3,212 views
7 votes
7 votes

Which of the following is a non-regular language?

  1. $L = \{wxwy \mid x,y,w \in (a+b)^+\}$
  2. $L = \{xwyw \mid x,y,w \in (a+b)^+\}$
  3. $L = \{wxyw \mid x,y,w \in (a+b)^+\}$
  4. All of these
edited by

4 Answers

Best answer
7 votes
7 votes
(C) $\left \{ wxyw|w,x,y \in (a+b)^{+} \right \}$ is NOT regular

But, (A) and (B) are regular.

regex for $\left \{ wxwy|w,x,y \in (a+b)^{+} \right \} = \left ( a(a+b)^{+}a + b(a+b)^{+}b \right )(a+b)^{+}$

and regex for $\left \{ xwyw|w,x,y \in (a+b)^{+} \right \} = (a+b)^{+} \left ( a(a+b)^{+}a + b(a+b)^{+}b \right )$

NOTE : put the minimal strings in w first and you get two regex $R_1$ and $R_2$. Then for next higher strings of w try to build (1) (Or, (2) ) using those $R_1$ , $R_2$. If it is possible to derive all the next strings of L = $\left \{ wxwy \right \}$ only using $R_1$ and  $R_2$, then $R_1 + R_2$ is the net regular expression for L.
selected by
2 votes
2 votes

Answer : c

There's a small observation that makes difference in option c from option a and b i.e in option c starts and ends both with w while other two options have x and y thus giving us more choices.

For option a : wxwy : Here we can start with w i.e (a+b)^+ and end corresponding to w as we have y in end.Hence regex is [a(a+b)+a(a+b)+ + b(a+b)+b(a+b)+]

Similarly for option b : xwyw : regex is [(a+b)+a(a+b)+a  + (a+b)+b(a+b)+b ]

But we can't do something like this in c option as we don't have x or y at end or start to make choices... hence makes it non regular.

Answer:

Related questions

5 votes
5 votes
3 answers
1
Hirak asked May 25, 2019
1,739 views
Consider the following statements:$S_1:\{(a^n)^m|n\leq m\geq0\}$$S_2:\{a^nb^n|n\geq 1\} \cup \{a^nb^m|n \geq1,m \geq 1\} $Which of the following is regular?$S_1$ only$S_2...
0 votes
0 votes
1 answer
2