in Theory of Computation retagged by
13,013 views
21 votes
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?

  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.
in Theory of Computation retagged by
by
13.0k views

4 Comments

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

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

5
5

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
1

3 Answers

18 votes
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

edited by

4 Comments

The given grammar for L2 does generate those strings.
1
1

@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
0
You can try parsing any such string using the given grammar :) And I didn't get your split part- I see that all even and odd length strings are generated by the given grammar.
0
0
15 votes
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 Comments

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...
4
4
edited by

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.

3
3

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

0
0

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

0
0
1 vote
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

1 comment

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

Can you please explain it in simple way!
0
0
Answer:

Related questions