11,036 views

Consider the following languages.

$$\begin{array}{ll} L_1= \{ wxyx \mid w,x,y \in (0+1)^{+} \} \\ L_2= \{xy \mid x,y \in (a+b)^{*}, \mid x \mid=\mid y \mid, x \neq y \} \end{array}$$

Which one of the following is TRUE?

1. $L_1$ is regular and $L_2$ is context- free.
2. $L_1$ context- free but not regular and $L_2$ is context-free.
3. Neither $L_1$ nor $L_2$ is context- free.
4. $L_1$ context- free but  $L_2$ is not context-free.

How come L1 is regular?
As x is getting repeated, I think this means same pattern shall be repeated for x...
edited

Useful gate cse link to understand why $L_1$ is regular.

According to me,

L1 should be CSL because it has 2 occurrences of x, which means whenever the x occurs a second time then it must be equivalent to the first x, which can be checked by LBA, (not by PDA because in PDA we use stack which uses LIFO approach, had it been wxyx^r then PDA can be used.) as here we will require 2 stacks to compare the values of x. FA won’t be able to store the first occurrence of x belonging to (0+1)* , so how would FA be able to check whether the first occurrence of x and second occurrence of x are similar or not? That’s why, I think L1 can’t be regular.

The approach which I can think of is, as we don’t need to worry about w and y , so we directly skip it without taking them into the stack. We have to only worry about x(1st occurrence) and x (2nd occurrence). We will use 2 stacks to compare them.

But this was a WRONG approach!

Instead, we have to think it like we have wxyx, where x is the one with the double occurrence, try to make its length as small as possible, after doing which we will get that x can be either 0 or 1. For rest we can assume that as w and y are altogether different, a certain part of x can be considered under w and y as even they both belong to (0+1)* . The place we need to take care is as x is present at the end, then the ending letter of wxyx would be equal to x and hence that same x’s value would be the value of the first occurrence of x. So, we can form a regular expression for it as shown by the best answer.

Subscribe to GO Classes for GATE CSE 2022

Here for $L_1$ a regular expression exists,

$L_1= (0+1)^{+}0 (0+1)^{+}0 + (0+1)^{+}1 (0+1)^{+}1$

So, $L_1$ is a Regular Language.

Now, for $L_2$ a context-free grammer exists which is shown below,

• $S→AB\mid BA$
• $A→a\mid aAa \mid aAb \mid bAb\mid bAa$
• $𝐵→𝑏\mid 𝑎𝐵𝑎 \mid 𝑎𝐵𝑏\mid 𝑏𝐵𝑏\mid 𝑏𝐵𝑎$

$L_2$ is the complement of $L=\{ww \mid w \in (a+b)^{*}\} \cup \{w \mid w \in (a+b)^{*} \text{ and } |w| \text{ is odd }\}$

Proof : https://cs.stackexchange.com/questions/19151/is-the-complement-of-ww-context-free

So correct option is : A

by
1 3 10

Isn’t the second part of the union can be avoided. ??
Wrong grammar mentioned for L2,not generating epsilon due to which strings of some lengths 4,8….are not generated

L1: (a+b)$(a+b)^{+} 0 (a+b)^{+} 0 + (a+b)^{+} 1 (a+b)^{+} 1$

L2: is CFL. Check here

by
97 200 538

how did you get that regualar expression, I m unable to get it. And the link has no proper explantion as to why it is CFL...
edited

Abhineet Singh, you want your second and last string character to be the same.

Edit :
Take any example of a string on {0,1} for x, let it be x: 1001
Substitute it in the string, we get  w1001y1001
Now take anything for w and u, let us take single characters for simplicity

0100101001

0100111001

1100101001

1100111001

Now, as w,x,y can be any non-empty strings

0100101001

0100111001

1100101001

1100111001 (The underlined strings are now w and y)

This works because both x's will always end with the same character, it is only needed to verify that character is same, as x's prefixes can be realised as w and y.

@palashbehra5 What if x=ab in L1, how the given regular expression justifies that?

@naveen_168 Yes, my comment is incorrect, however, the language is still regular.

so after going through all the links, i found the link to exact question.

https://cs.stackexchange.com/questions/307/show-that-xy-%e2%88%a3-x-y-x-%e2%89%a0-y-is-context-free

1 comment

I still didn’t get “how it is CFL” ?

Can you please explain it in simple way!

1
13,878 views