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??
A.
L1 is regular and L2 is context-free.
B.
L1 is context-free but not regular and L2 is context-free.
C.
Neither L1 nor L2 is context-free.
D.
L1 is context-free but L2 is not context-free.
Solution:
L1 = {wxyx | w, x, y ∈ (0 + 1)+} is Regular language
Since in L1 = wxyx, we have two possibilities here, x can be 0 or 1, and w & y ∈ (0 + 1)+
So, overall we will get regular expressions as
(0 + 1)+0(0 + 1)+0 + (0 + 1)+1(0 + 1)+1
L2 = {xy | x, y ∈ (a + b)*, |x| = |y|, x≠y } is Context-free language (CFL)
There exists a Grammar for the above language.
G:
E → XY | YX
X → a | aXa | aXb | bXb | bXa
Y → b | aYa | aYb | bYb | bYa