Given the following statements : S1 : If L is a regular language then the…
2013
Given the following statements :
S1 : If L is a regular language then the language {uv | u ∈ L, v ∈ LR} is also regular.
S2 : L = {wwR} is regular language.
Which of the following is true ?
- A.
S1 is not correct and S2 is not correct.
- B.
S1 is not correct and S2 is correct.
- C.
S1 is correct and S2 is not correct.
- D.
S1 is correct and S2 is correct.
Attempted by 81 students.
Show answer & explanation
Correct answer: C
Answer: S1 is correct and S2 is not correct.
S1 — Reason: If L is regular then the reversal L^R is regular (regular languages are closed under reversal). The concatenation of two regular languages is regular, so {uv | u ∈ L, v ∈ L^R} equals L · L^R and is regular.
S2 — Reason: The language {ww^R | w ∈ Σ*} is the set of even-length palindromes (each string is a string followed by its reverse). For alphabets with at least two symbols this language is not regular because it requires matching an arbitrary-length first half with the second half; this can be formalized using the pumping lemma or Myhill–Nerode theorem. (Note: over a unary alphabet the language becomes the set of all even-length strings, which is regular; but the general statement without restricting the alphabet is false.)
A video solution is available for this question — log in and enroll to watch it.