# Drawing a dfsa where L is a set of strings that contains at most 4 zeros

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?

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.

• 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^{*}$
– shah
Nov 5, 2018 at 10:38
• Depends on the definition. Are you allowed to have $\epsilon$ transitions (empty word)? Nov 5, 2018 at 10:41
• 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
– shah
Nov 5, 2018 at 10:44
• So you can have a set of accepting states, not just one. Nov 5, 2018 at 10:46
• Do you know how to explain each state? For example: $s_0:$ x has an even number of 1's. Not sure how too
– shah
Nov 5, 2018 at 10:51