retagged by
17,817 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.
retagged by

4 Answers

Best answer
25 votes
25 votes

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

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

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

Answer:

Related questions

18 votes
18 votes
7 answers
3
Arjun asked Feb 12, 2020
13,338 views
Consider the following language.$L = \{{ x\in \{a,b\}^*\mid}$number of $a$’s in $x$ divisible by $2$ but not divisible by $3\}$The minimum number of states in DFA that ...