See example $9,10,11$ here.

The Gateway to Computer Science Excellence

+4 votes

Which of the following is a non-regular language?

- $L = \{wxwy \mid x,y,w \in (a+b)^+\}$
- $L = \{xwyw \mid x,y,w \in (a+b)^+\}$
- $L = \{wxyw \mid x,y,w \in (a+b)^+\}$
- All of these

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

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

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

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.

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

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.

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

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

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.4k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.7k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,666 questions

56,136 answers

193,697 comments

93,480 users