Given the following two languages : \(L_{1} = \{uww^{R} ν | u, v, w \in (a,…
2016
Given the following two languages :
\(L_{1} = \{uww^{R} ν | u, v, w \in (a, b)^{+}\} \\ L_{2} = \{uww^{R} ν | u, ν, w \in (a, b)^{+} , |u| \geq |ν|\}\)
Which of the following is correct ?
- A.
𝐿1 is regular language and 𝐿2 is not regular language.
- B.
𝐿1 is not regular language and 𝐿2 is regular language.
- C.
Both 𝐿1 and 𝐿2 are regular languages.
- D.
Both 𝐿1 and 𝐿2 are not regular languages.
Attempted by 142 students.
Show answer & explanation
Correct answer: A
Conclusion: The first language is regular and the second language is not regular.
Reason L1 is regular: For any nonempty w, the string w w^R has the last character of w followed immediately by the same character (the first character of w^R). Thus w w^R always contains either "aa" or "bb". Therefore any string of the form u w w^R v contains "aa" or "bb" as a substring, so
L1 = (a+b)* (aa + bb) (a+b)*, which is a regular language.
Reason L2 is not regular: The constraint |u| ≥ |v| compares lengths of substrings before and after the central palindrome, which cannot be enforced by a finite automaton. A clear way to prove non-regularity is to intersect with a suitable regular language and apply the pumping lemma.
Consider L2 ∩ a* bb a* = { a^p bb a^q | p ≥ q ≥ 1 }.
Assume this intersection is regular. Let n be the pumping length. Take s = a^n bb a^n, which is in the intersection.
Any decomposition s = xyz with |xy| ≤ n forces y to consist only of a's from the left block. Pumping down (i = 0) yields xz = a^{n-|y|} bb a^n, where the number of a's before bb is now less than the number after bb, so xz is not in the intersection. This contradicts the pumping lemma.
Thus the intersection is not regular, so L2 cannot be regular.
Therefore the correct statement is: the first language is regular and the second language is not regular.