0
$\begingroup$

For each of the following languages over alphabet $Σ = \{0, 1\}$, construct a DFSA that accepts it and a regular expression that denotes it. Prove that your automata and regular expressions are correct. Use as few states as possible in your DFSA.

(a) $L_1 = \{x: \text{x is a set of string that contains at most 4 zeros} \}$

The regex is

$$R_1 = 1^{∗} + 1^{∗}01^{∗} + 1^{∗}01^{∗}01^{∗} + 1^*01^*01^*01^* + 1^*01^*01^*01^*01^*$$

How would I draw the dfsa for it?

$\endgroup$

1 Answer 1

1
$\begingroup$

Here are the state transitions:

$s_0\rightarrow_1 s_0$, $s_0\rightarrow_0 s_1$, $s_1\rightarrow_1 s_1$, $s_1\rightarrow_0 s_2$, $s_2\rightarrow_1 s_2$, $s_2\rightarrow_0 s_3$, $s_3\rightarrow_1 s_3$, $s_3\rightarrow_0 s_4$, $s_4\rightarrow_1 s_4$.

$s_0$ is the starting state and all states are final states.

Start in state $s_0$. Produce any number of 1's and then exit or read 0 and move to state $s_1$. In state $s_1$ produce any number of 1's and then exit or read 0 and move to state $s_2$, and so on.

$\endgroup$
5
  • $\begingroup$ Oh wait, this cant be done by dfsa because since it can only have one final state? If this question was changed to "x is a set of string that contains at most 1 zeros" would it be a dfsa and the regex will be $1^{*}$ $\endgroup$
    – shah
    Nov 5, 2018 at 10:38
  • $\begingroup$ Depends on the definition. Are you allowed to have $\epsilon$ transitions (empty word)? $\endgroup$
    – Wuestenfux
    Nov 5, 2018 at 10:41
  • $\begingroup$ A DFSA is a 5-tuple $M = (Q, \Sigma, \delta, s, f)$. Q is the set of states, $\Sigma$ is the input alphabet, $\delta$ is the transition, $s$ is the initial state, and $f$ is the set of accepting states. So yeah no $\epsilon$ transition $\endgroup$
    – shah
    Nov 5, 2018 at 10:44
  • 1
    $\begingroup$ So you can have a set of accepting states, not just one. $\endgroup$
    – Wuestenfux
    Nov 5, 2018 at 10:46
  • $\begingroup$ Do you know how to explain each state? For example: $s_0: $ x has an even number of 1's. Not sure how too $\endgroup$
    – shah
    Nov 5, 2018 at 10:51

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.