The Gateway to Computer Science Excellence
+4 votes
909 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
in Theory of Computation by (285 points)
edited by | 909 views
+2

See example $9,10,11$ here.

0
all of these, isn't it?
0
No..answer is C.
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.

So answer is 3
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]?

4 Answers

+7 votes
Best answer
(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 (56.9k points)
selected by
+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...

+2 votes
by Loyal (6.3k 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 (422k points)
0
thank u sir.....got it
+1 vote

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.

by Active (4.1k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,666 questions
56,136 answers
193,697 comments
93,480 users