Construct a deterministic finite machine for the language $(01)^*$

91 Views Asked by At

I need to construct a deterministic finite machine that recognizes the language $(01)^*$. This is the machine I have constructed, is it valid?

Let $M=(Q,\Sigma,\delta,q_0,F)$ where $Q = \{q_0,q_1\}$ is the set of states, $\Sigma=\{0,1\}$ is the alphabet, $\delta:Q\times\Sigma\to Q$ is the transition function given by

finite machine

$q_0$ is the start state, and $F=\{q_0\}$ is the set of accept states.

1

There are 1 best solutions below

2
On BEST ANSWER

Your example won't work because the DFA must have at least three states. Let $M=(Q,\Sigma,\delta,q_0,F)$ where $Q = \{q^0,q^1,q^\Delta\}$ is the set of states, $\Sigma=\{0,1\}$ is the alphabet, $\delta:Q\times\Sigma\to Q$ is the transition function given by $$ \begin{array}{c|cc} q\overset{\LARGE\setminus}{\phantom{.}}\overset{\Large i}{\phantom{l}}&0&1\\\hline q^0&q^1&q^\Delta\\ q^1&q^\Delta&q^0\\ q^\Delta&q^\Delta&q^\Delta \end{array}, $$ $q_0=q^0$ is the start state, and $F=\{q_0\}$ is the set of accept states. Then $M$ recognizes the language described by the regular expression $(01)^*$.