Consider the following two statements about regular languages: S1: Every…
2021
Consider the following two statements about regular languages:
S1: Every infinite regular language contains an undecidable language as a subset.
S2: Every finite language is regular.
Which one of the following choices is correct?
- A.
Only S1 is true
- B.
Only S2 is true
- C.
Both S1 and S2 are true
- D.
Neither S1 nor S2 is true
Attempted by 136 students.
Show answer & explanation
Correct answer: C
Answer: Both statements are true.
S1 (Every infinite regular language contains an undecidable language as a subset): Let R be any infinite regular language. Regular languages are decidable, so we can enumerate the elements of R computably as r0, r1, r2, .... Fix any known undecidable set of indices U ⊆ ℕ (for example, an encoding of the halting set). Define S = { rn | n ∈ U }. Since the mapping n ↦ rn is computable and its inverse is computable by enumerating R until a string is reached, membership in S would decide U. Therefore S is undecidable, and S ⊆ R, so R contains an undecidable subset.
S2 (Every finite language is regular): Any finite language can be recognised by a finite automaton: build a finite-state machine that has a distinct accepting path for each string in the language (or equivalently express the language as a finite union of literal strings in a regular expression). Hence every finite language is regular.
Therefore both statements are true.
A video solution is available for this question — log in and enroll to watch it.