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 ?

  1. A.

    S1 is not correct and S2 is not correct.

  2. B.

    S1 is not correct and S2 is correct.

  3. C.

    S1 is correct and S2 is not correct.

  4. 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.

Explore the full course: Mppsc Assistant Professor