Please program these problems using C. (specifically c99). Make a struct of a DFA and NFA. Please include comments

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) Starts with uni-

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) ends with -atic.

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