Search code examples
theorydfa

DFA and regular languages


I've been thinking about the following and I think the answer's in the affirmative.

Is it true that every subset of a DFA-acceptable language that is regular is also DFA-acceptable?


Solution

  • No. Counterexample: Alphabet is numbers digits. DFA accepts all natural numbers. Subset: DFA accepts all prime numbers.

    Edit: Alphabet is digits. Sorry, wrong terminology there.

    Natural numbers can be expressed as a regular language (and therefore a DFA can be constructed for them):

    0|([1-9][0-9]*)