0
$\begingroup$

I am trying to construct a DFA with $\Sigma = \{0,1\}$ that accepts $L = (0\mid10)^*$, below is my attempt, but I'm a bit stuck.

enter image description here

The quiz marked it wrong since there's no transition from $q_1$ under $1$, but if I add a loop on $q_1$ for $1$ onto itself then I'm not actually accepting $10$, it would be $110$?

$\endgroup$
1
  • $\begingroup$ One common technique for dealing with substrings that guarantees rejection is introducing a non-accepting state that the DFA enters and never leaves. See this. Apart from what you have noted, there are other problems with your solution. Your DFA does not accept empty string, which the given language admits. Also, your transition from q2 to q0 will allow the string 10110 to be accepted. $\endgroup$
    – Russel
    Mar 20 at 9:51

2 Answers 2

1
$\begingroup$

I don't know how your teachers introduced you to the construction of deterministic finite automata. The brief introduction is that we have a way of converting regular expressions into ε-NFA, then into NFA and, finally, DFA, as shown here, (adapted from Hopcroft and Ullman's 1979 Introduction to automata theory, languages and computation):

enter image description here

In your case, you have a language described by a regex: $$ L = (0 | 10)^* $$ To be as pedantic as possible, you may use the McNaughton–Yamada–Thompson algorithm to build an ε-NFA, then use the ε-closure method to build an NFA and the powerset construction to conclude with a DFA.

In this case, the regex is fairly simple and we can proceed by intuition. We want our automaton to accept the empty string ε, and we already know that our initial state will also be one of the final states:

step_0

Then, we know we may read a $0$ or a $1$, therefore we want two transitions out of the initial state for these two symbols:

step_1

of these two new states, we can read $0$ and accept the string, therefore $q_1$ is final as well. When we read a $1$ we must read a $0$ after it, so we need to add a transition from $q_2$ to $q_1$:

step_2

Now, we considered what we can do when reading a symbol from the starting state $q_0$. If we read a $1$ from state $q_1$ we need it to be followed by a $0$ to be in a valid state, which is the same situation as state $q_2$; if we read a $0$ in state $q_1$ we can stay in the same state: step_3

As @Nathaniel pointed out, technically there should be a sink state when reading a $1$ from state $q_2$, which is something we won't accept. In my experience, this state is often left implicit and not drawn; however, to be precise, we can insert it:

sink

Note that this DFA is not minimal. You can minimize it using one of Hopcroft's, Moore's or Brzozowski's algorithms.

$\endgroup$
2
$\begingroup$

The language of this automaton is $\mathcal{L}(((0|10)(0|1))^*(0|10))$. It accepts $0110$ which is not in the language $\mathcal{L}((0|10)^*)$.

There is a complete DFA with 3 states recognizing $\mathcal{L}((0|10)^*)$, but you'd need to note the following:

  • the start state must be a final state because $\varepsilon \in \mathcal{L}((0|10)^*)$ ;
  • you need a non-final sink state that you reach after reading $11$.

I will add more details if necessary.

$\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.