Which of the following languages is/are regular? \(L_1: \left\{ wxw^R \mid w,…
2015
Which of the following languages is/are regular?
\(L_1: \left\{ wxw^R \mid w, x \in \{a, b\} ^* \text{ and } |w|, |x| > 0\right\}, w^R \text{ is the reverse of string } w\)
\(L_2: \left\{ a^nb^m \mid m \neq n \text { and } m, n \geq 0 \right\}\)
\(L_3: \left\{ a^pb^qc^r \mid p, q, r \geq 0 \right\}\)
- A.
\(L_1\)and\(L_3\)only - B.
\(L_2\)only - C.
\(L_2\)and\(L_3\)only - D.
\(L_3\)only
Attempted by 147 students.
Show answer & explanation
Correct answer: A
Key insight: determine regularity of each language.
L1: { w x w^R | w,x ∈ {a,b}*, |w|,|x|>0 } is regular. Take w of length 1: strings become a x a or b x b, so L1 is exactly the set of strings of length ≥2 whose first and last symbol are equal. A regular expression is (a(a|b)+a) ∪ (b(a|b)+b).
L2: { a^n b^m | m ≠ n } is not regular. Reason: a*b* is regular. If L2 were regular then a*b* \ L2 = { a^n b^n } would be regular as a difference of regular languages, contradicting the known non-regularity of { a^n b^n }.
L3: { a^p b^q c^r | p,q,r ≥ 0 } is regular since it equals a*b*c*.
Therefore the regular languages are L1 and L3.
A video solution is available for this question — log in and enroll to watch it.