Exercises for the Week 12 part 1 lecture video

• If you make a DFSA that accepts the same language as this NFSA, how many states will the DFSA have?
  • show/hideIf you follow the procedure from the video, the DFSA will have 16 states, because there are 16 possible subsets of the 4 states of the NFSA. If you trim states that aren't reached, you'll be left with just 5:
• (Related to the aside at the start of the video.) Let \( L \) be the set of strings in \( \{ \texttt{a}, \texttt{b} \}^* \) such that the number of "a"s mod 3 is equal to the number of "b"s mod 3. For example, ab, aaaab, abab, baab, aaa are all in \( L \) but aabba isn't since there are 3 "a"s and two "b"s, and those are not equivalent mod 3. What's the smallest number of states a DFSA accepting \( L \) can have?
  • show/hideThree. The DFSA needs to remember the difference between the number of "a"s and "b"s, modulo 3. Here's what the smallest DFSA looks like. I've named each state after the difference mod 3.