Theory-of-Computation
October 6, 2023Theory-of-Computation
October 6, 2023Theory-of-Computation
| Question 10 |
Consider the following languages.
- L1 = {wxyx | w,x,y ∈ (0 + 1)+}
L2 = {xy | x,y ∈ (a + b)*, |x| = |y|, x ≠ y}
Which one of the following is TRUE?
| L1 is context-free but not regular and L2 is context-free. | |
| Neither L1 nor L2 is context-free.
| |
| L1 is regular and L2 is context-free.
| |
| L1 is context-free but L2 is not context-free. |
Question 10 Explanation:
L1 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
L2 is CFL since it is equivalent to complement of L=ww.
Complement of L=ww is CFL.
Correct Answer: C
Question 10 Explanation:
L1 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
L2 is CFL since it is equivalent to complement of L=ww.
Complement of L=ww is CFL.
Subscribe
Login
0 Comments