0
$\begingroup$

The question was to construct a DFA which accepts the language $$\{ x \in \{0,1\}^* \mid x\text{ starts with a }0\text{ and has at most one }1\}$$

So I first constructed DFA for '$x$ starts with a $0$' and a DFA for 'has at most one $1$' then I tried getting the product automaton of these, but the quiz says the automaton should not accept the string "" (empty string). Does that mean I just change $q_0p_0$ from accept state to normal state? or have I done something more wrong?

enter image description here

$\endgroup$
2
  • 1
    $\begingroup$ Here is a nice online tool to design/draw/experiment with automata. $\endgroup$
    – John L.
    Commented Mar 26, 2022 at 6:23
  • $\begingroup$ thanks that'll be useful $\endgroup$ Commented Mar 26, 2022 at 10:03

1 Answer 1

2
$\begingroup$

The "DFA for 'has at most one $1$-symbol'" in the question is not correct. It accepts $101$, $0101$, etc.

The right one should be like the following.

DFA that accepts strings with at most one 1, for cs150138. Made from http://ivanzuzak.info/noam/webapps/fsm2regex/


In the product automaton, you should label state $p_iq_j$ as accept state iff both $p_i$ and $q_j$ are accept states in their original automaton respectively, since the condition for string $x$ to be in the language is " ... and ...".

If the condition been "... or ...", then you should label state $p_iq_j$ as accept state iff at least one of $p_i$ and $q_j$ is an accept state in its original automaton.

$\endgroup$
1
  • $\begingroup$ thank you for pointing that out, makes sense now, I didn't notice that it would accept more 1's. $\endgroup$ Commented Mar 26, 2022 at 10:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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