Question about deterministic finite automaton and accepting states

104 Views Asked by At

For $n \in \mathbb N$, an "$n-$DFA" is an automaton with exactly $n$ accepting states.

Let $\Sigma=\{0,1\}$. Prove that the set of the languages that can be accepted by "$1-$DFA" is a subset of the set of the languages that can be accepted by "$2-$DFA".

I have no idea what to do with this question. Frankly, I thought of a counter example of $ L_1 =\varnothing $ but I've been told that this language has a finite-automaton with $2$ accepting-states, is it possible?

1

There are 1 best solutions below

0
On

It's a trick answer: your states don't have to form a connected graph. (i.e. the states don't all have to be reachable from the start state).

So take any 1-DFA, add an accepting state that isn't connected to anything, and, hey, it's a 2-DFA.