Consider the following languages: \(L_1 = \{a^n w a^n \mid w \in \{a,…
2022
Consider the following languages:
\(L_1 = \{a^n w a^n \mid w \in \{a, b\}^*\}\)
\(L_2 = \{w x w^R \mid w,x \in \{a, b\}^*, |w|, |x| > 0\}\)
Note that \(w^R\) is the reversal of the string \(w\). Which of the following is/are TRUE?
- A.
\(L_1\)and\(L_2\)are regular. - B.
\(L_1\)and\(L_2\)are context-free. - C.
\(L_1\)is regular and\(L_2 \)is context-free. - D.
\(L_1\)and\(L_2 \)are context-free but not regular.
Attempted by 106 students.
Show answer & explanation
Correct answer: A, B, C
Answer: Both languages are regular.
Explanation for L1: Since n can be 0, for any string s ∈ {a,b}* we can choose n = 0 and w = s, so s = a^0 w a^0 is in L1. Therefore L1 = {a,b}*, which is regular.
Explanation for L2: If a string belongs to L2, then it has the form w x w^R with |w| ≥ 1. Writing w = c1c2…ck, the last character of the string is c1, so the first and last characters are equal. Conversely, any string whose length is at least 3 and whose first and last characters are the same can be written by taking w to be the first character and x to be the nonempty middle part. Thus L2 = { strings of length ≥ 3 whose first and last symbol are equal }.
Regular expressions (one way to see regularity):
For L1: {a,b}*
For L2: a(a|b)+a | b(a|b)+b
Conclusion: Both languages are regular (and therefore also context-free).
A video solution is available for this question — log in and enroll to watch it.