TheoryofComputation
October 6, 2023TheoryofComputation
October 6, 2023TheoryofComputation
Question 10

Consider the following languages.
 L_{1} = {wxyx  w,x,y ∈ (0 + 1)^{+}}
L_{2} = {xy  x,y ∈ (a + b)*, x = y, x ≠ y}
Which one of the following is TRUE?
L_{1} is contextfree but not regular and L_{2} is contextfree.


Neither L_{1} nor L_{2} is contextfree.


L_{1} is regular and L_{2} is contextfree.


L_{1} is contextfree but L_{2} is not contextfree.

Question 10 Explanation:
L_{1} is regular. y can be expanded and w can also expanded. So x can be either “a” or “b”.
So it is equivalent to
(a+b)^{+} a (a+b)^{+} a + (a+b)^{+} b (a+b)^{+} b
L_{2} is CFL since it is equivalent to complement of L=ww.
Complement of L=ww is CFL.
Correct Answer: C
Question 10 Explanation:
L_{1} is regular. y can be expanded and w can also expanded. So x can be either “a” or “b”.
So it is equivalent to
(a+b)^{+} a (a+b)^{+} a + (a+b)^{+} b (a+b)^{+} b
L_{2} is CFL since it is equivalent to complement of L=ww.
Complement of L=ww is CFL.
Subscribe
Login
0 Comments