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?
Best Answer
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.