Consider the following languages. \(\begin{array}{ll} L_1= \{ wxyx \mid w,x,y…
2020
Consider the following languages.
\(\begin{array}{ll} L_1= \{ wxyx \mid w,x,y \in (0+1)^{+} \} \\ L_2= \{xy \mid x,y \in (a+b)^{*}, \mid x \mid=\mid y \mid, x \neq y \} \end{array}\)
Which one of the following is TRUE ?
- A.
\(L_1\)is regular and\(L_2\)is context- free. - B.
\(L_1\)context- free but not regular and\(L_2\)is context-free - C.
Neither
\(L_1\)nor\(L_2\)is context- free - D.
\(L_1\)context- free but\(L_2\)is not context-free
Attempted by 89 students.
Show answer & explanation
Correct answer: B
Answer: L1 is context-free but not regular, and L2 is context-free.
Reason for L1 being context-free: A nondeterministic pushdown automaton can guess the start of the substring x, push the symbols of x onto the stack, read a nonempty middle part y, and then pop and match the final x. This verifies the pattern w x y x with w,x,y nonempty, so L1 is context-free.
Why L1 is not regular: Enforcing equality of two arbitrarily long occurrences of x requires unbounded memory, which finite automata do not have. The intuitive limitation can be formalized using the pumping lemma or Myhill–Nerode arguments to show L1 is not regular.
Reason for L2 being context-free: L2 consists of even-length strings whose first half and second half have the same length but are not identical. A PDA can nondeterministically guess the midpoint, push the symbols of the first half, then pop while reading the second half and nondeterministically check for a position where the symbols differ; if a mismatch is found the machine accepts. Thus L2 is context-free.