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?
- (Related to the aside at the start of the video.) Let
be the set of strings in 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 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 can have?