Quick question on DFA

Question

I'm asked to list all DFA over the alphabet sigma = {0} such that the set of states is {s0, s1}, for which the initial state is s0 and the set of accept states is either {s0} or {s1}. And also asked to give what languages they accept.

This question seems quite vague to me but I'm pretty sure its probably something obvious - could someone explain what exactly I'm meant to do here (am I supposed to be give possible definitions of DFA's?)?

Many thanks!

Answer 1

Formally a DFA is a quintuple $M=\langle Q,\Sigma,q_0,\delta,F\rangle$, where $Q$ is a finite set of states, $\Sigma$ is a finite input alphabet, $q_0\in Q$ is the initial state, $\delta:Q\times\Sigma\to Q$ is the transition function, and $F\subseteq Q$ is the set of acceptor states. You’ve been given three of the five components:

• $Q=\{s_0,s_1\}$;
• $\Sigma=\{0\}$; and
• $q_0=s_0$.

You’re also told that $F$ is either $\{s_0\}$ or $\{s_1\}$. Thus, the possible DFAs are of the forms

$$\langle \{s_0,s_1\},\{0\},s_0,\delta,\{s_0\}\rangle$$

and

$$\langle \{s_0,s_1\},\{0\},s_0,\delta,\{s_1\}\rangle\;,$$

where $\delta$ can be any function from $\{s_0,s_1\}\times\{0\}$ to $\{s_0,s_1\}$.

There aren’t many possibilities for $\delta$: $\delta(s_0,0)$ can be either $s_0$ or $s_1$, and $\delta(s_1,0)$ can also be either $s_0$ or $s_1$. These choices are independent, so there are altogether $2\cdot2=4$ possible transition functions $\delta$. Each can be paired with either of the two possibilities for $F$, so there are altogether just $4\cdot2=8$ DFAs that meet the requirements of the problem.

Here’s a diagrammatic representation of one of them:

Here $\delta(s_0,0)=s_1$, $\delta(s_1,0)=s_0$, and $F=\{s_0\}$. You can easily show that a string $0^n$ of $n$ zeroes is accepted by this DFA if and only if $n$ is even, so the language accepted by this DFA is $\{0^{2n}:n\ge 0\}$.

Now just do the same thing for the other seven possible automata.