###### Theory-of-Computation

October 6, 2023###### Theory-of-Computation

October 6, 2023# Theory-of-Computation

Question 19 |

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 context-free but not regular and L_{2} is context-free. | |

Neither L _{1} nor L_{2} is context-free.
| |

L _{1} is regular and L_{2} is context-free.
| |

L _{1} is context-free but L_{2} is not context-free. |

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