As x is getting repeated, I think this means same pattern shall be repeated for x...

please explain

Dark Mode

13,013 views

21 votes

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?

- $L_1$ is regular and $L_2$ is context- free.
- $L_1$ context- free but not regular and $L_2$ is context-free.
- Neither $L_1$ nor $L_2$ is context- free.
- $L_1$ context- free but $L_2$ is not context-free.

2

1

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.

1

18 votes

Best answer

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

@gatecse, you’re right, as any even length string can be broken into 2 odd sized substrings.

But, what's the guarantee that the split where one is described by A and other by B or vice versa will always be such that the alphabet in the middle is different ? Ex: x=ababaa, y=ababab string = ababaaa|babab (Here | is the boundary, and b's are in the middle) string = ababaaaba|bab (Similarly here are two a's in the middle) string = ababaaababa|b (This follows AB) But there must be some string for which Only AA or BB are possible? or is it not?

0

15 votes

Answer : A

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

L2: is CFL. Check here

4

edited
Feb 1, 2022
by palashbehra5

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__0__1001__0__1001

__0__1001__1__1001

__1__1001__0__1001

__1__1001__1__1001

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

__0100__1__1100__1

__1100__1__0100__1

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

3

1 vote

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