1. Implement deterministic finite automata that recognize the following languages:

(a) Exactly the string ab

(b) Any string that starts with the characters ab

(c) Binary input with an even number of 1s

(d) Binary input with an even number of both 0s and 1s

(e) At least one other pattern that you think is interesting (and hopefully different from other students) For all automata, you may assume that the input alphabet contains exactly the char values greater than 0 and less than 128. This range is the ASCII characters, including upper- and lowercase letters, numbers, and common punctuation. If you want to do something else, document your choice.

2. Implement non-deterministic finite automata that recognize the following languages:

(a) Strings ending in -man

(b) Strings with more than one a, g, h, i, o, s, t, or w, or more than two ns. This automaton is described in FOCS as part of a project to find words that can be made from the letters of the word Washington (so-called partial anagrams). In this automaton, acceptance means that the input string is not a partial anagram of washington, because it has too many of some letter.

(c) At least one other pattern that you think is interesting (and hopefully different from other students)

3. Implement a translator function that receives as input an instance of an NFA and produces as output a (new) instance of a DFA that is equivalent to the original NFA (accepts the same language). Your code should demonstrate the equivalence by running the original NFA and its translation on the three languages you used in Question 2 (the two given in the problem and the one you made up yourself). That is, you will have three functions that produce NFAs from Part 2 of the project. Pass the output of those functions to your converter and run the resulting DFA on user input as described previously.

Please include comments