989 views

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 | 989 views
+2

See example $9,10,11$ here.

0
all of these, isn't it?
0
0
0
1st and 2nd could be regular if we assume that x or y eats up everything in the string.

But  3rd could not be regular if we have a string abaaab.. here ab is w

We can not assume whole string as x or y..

I am not sure for the 3rd option
0
how u will eat up everything in the string..its (a+b)^+ not (a+b)* in option 1 and 2
0
Ya....but i got something

If we take w as abab

then 1. abab X abab Y ......we can write it as a babX a babY

2. X abab Y abab .... can be written as Xaba b Yaba b

3. abab X Y abab .....Here we can not merge as string of w and ending of w may not be same.

0
we can take w as anything and selecting w as single character will be best option and pushing rest of the things in x and y.
0
Nopes. A and B are regular.
0

@ Arjun sir,

what is wrong is if write {[a (a+b)a]+ [b (a+b)n b] \ n>=2}, so C option is also regular and I am getting none of these as answer. Please correct me if I am wrong.

0

in case of c can't we have [a(a+b)+a+a(a+b)+b+b(a+b)+a+b(a+b)+b]?

(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.
by Veteran (57.3k points)
selected
+1
How do you find RegExp for  $\big\{ wxwy \big\}$?
0
I wrote the method, above.
0

@Debashish Deka,

as like option a and b why can't we write reg exp for c as -

a(a+b)+(a+b) + b(a+b)+(a+b)

as w can start with either a or b and also end with either a or b???

+1

@Shubhanshu, this is not posssible with c because,

lets assume string starts with abab, then it must end with abab, so it will look like abab........abab, now no other string will be there in a language which has prefix abab but does not have a suffix abab , for eg there will be no string like abab........abaa, as we grow the length of prefix larger and larger we have to keep record of prefix so that it can be used as suffix, because that prefix has a unique(same) suffix, hence we can not do it with FA since we have to keep record...

in all other options a), b), c)...for particular prefix there could be infinite suffixes...

i dont know if you got what i want to say but please let me know if you got it...

by Loyal (6.4k points)
0
Question was asked on October 2016, how come your answer shows TS of Jan 21 2016 ?
I knew time travel was real!:D ;)
+1 vote
by Veteran (434k points)
0
thank u sir.....got it
+1 vote

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.

by Active (4.1k points)