in Theory of Computation retagged by
17,819 views
33 votes
33 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
17.8k views

4 Comments

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.

 

7
7

4 Answers

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

@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

@ Sir, may you please elaborate what you meant by 

In reverse order PDA can do both string matching and mismatching.
But in straight order PDA can do only string mismatching.

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

Given $L1 =$ {$wxyx\ | w,x,y ∈ (0 + 1)^{+}$}

As w, x, y can be any strings of length one or more, as x is arbitary we can minimize x as much as we can because that will allow a superset of strings to be part of $L1$ and will not hinder the given condition, so we can rewrite $L1$ in the following way also : 

$L1 =$ {$pq\ | p,q ∈ (0 + 1)^{+}\ and\ p,q\ ends\ with\ the\ same\  symbol$}

Now we can clearly see that $L1$ is a regular language. Regular expression for $L1$ will be – 

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

For $L2$ there exists a CFG as mentioned in :

  1. https://gateoverflow.in/333199/gate-cse-2020-question-32?show=333362#a333362
  2. https://cs.stackexchange.com/questions/19151/is-the-complement-of-ww-context-free

So option (A) is the correct answer.

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