Let L be a regular language. Consider the constructions on L below: repeat (L)…
2006
Let L be a regular language. Consider the constructions on L below:
repeat (L) = {ww | w ∊ L}
prefix (L) = {u | ∃v : uv ∊ L}
suffix (L) = {v | ∃u uv ∊ L}
half (L) = {u | ∃v : | v | = | u | and uv ∊ L}
Which of the constructions could lead to a non-regular language?
- A.
Both I and IV
- B.
Only I
- C.
Only IV
- D.
Both II and III
Attempted by 24 students.
Show answer & explanation
Correct answer: B
Regular languages are closed under prefix and suffix operations. Therefore, if L is regular, prefix(L) and suffix(L) are always regular.
Similarly, the 'half' operation preserves regularity for any regular input language L.
However, the 'repeat' operation defined as {ww | w ∈ L} is not closed under regularity. For example, if L = Σ*, the resulting language {ww} is non-regular.
Thus, only construction I could lead to a non-regular language.