Gate2020 cs Q52
- Option : A
- Explanation : L1 is regular and L2 is CFL.L1: {ω xyx| ω, x, y ϵ (0 + 1)*}We can write the regular expression for this,Let, x = 0L11 = ω 0 Y 0 ⇒ ( 0 + 1)+ 0(0 + 1)+0x = 1L12 = ω 1 Y 1 ⇒ we can generate all the strings and since a regular expression can be written for 4, we can say 4 is regular.L2 is CFL:L2 = {xy| x,y ϵ (a + b)*, |x| = |y|, x ≠ y}L2 generates strings of even length, which can be done by PDA, therefore L2 is CFL.
