Consider the following languages: L1 = { ww | w ∈ {a, b}* } L2 = { ww^R | w ∈…
2001
Consider the following languages:
L1 = { ww | w ∈ {a, b}* }
L2 = { ww^R | w ∈ {a, b}+, w^R is the reverse of w }
L3 = { 0^(2i) | i is an integer }
L4 = { 0^(i^2) | i is an integer }
Which of the languages are regular?
- A.
Only L1 and L2
- B.
Only L2, L3 and L4
- C.
Only L3 and L4
- D.
Only L3
Attempted by 7 students.
Show answer & explanation
Correct answer: D
L1 contains strings of the form ww, where w is any string over {a, b}. This is not regular because a finite automaton cannot remember an arbitrary first half w and then verify that the second half is exactly the same.
L2 = {ww^R | w ∈ {a, b}+} is the language of even-length palindromes over {a, b}, which is not regular.
L3 = {0^(2i) | i is an integer} represents strings of even length over a unary alphabet. It is regular; a DFA only needs to remember whether the number of 0s seen so far is even or odd.
L4 = {0^(i^2) | i is an integer} contains unary strings whose lengths are perfect squares. This is not regular; in a unary regular language, the accepted lengths must eventually be periodic, but the gaps between consecutive squares keep increasing.
Therefore, only L3 is regular. Hence, option D is correct.