1
$\begingroup$

A deterministic finite automaton without $\epsilon$ steps for the language $0^*1^*$ is required. Any nice picture ? I have created a NFA for this language which has 2 states $Q_1,Q_2$, both are accepting, $Q_1$ is initial, there is a move under $0$ from $Q_1$ to $Q_1$, a move under $1$ from $Q_1$ to $Q_2$ and finally a move from $Q_2$ to $Q_2$ under $1$.

$\endgroup$
2
$\begingroup$

To construct a DFA, note the following:

  • An empty string or any string containing only $0$s is accepted, so any $0^*$ is accepted.

  • Zero or more $0$s followed by one or more $1$s is accepted, so any $0^*11^*$ is accepted.

  • Zero or more $0$s followed by one or more $1$s followed by $0$ is rejected, so any $0^*11^*0$ is rejected.

  • Any extension to a rejected string is also rejected (i.e. there is no route back from a rejecting state to an accepting state), so any $0^*11^*0(0+1)^*$ is rejected.

This suggests a three state DFA with two accepting states and one rejecting state ...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.