1. What are deterministic finite machines and non-deterministic finite machines? List out the differences between them.
2. How do you translate a regular expression to an NFA? Translate (a|b|c)?d into an NFA and draw its transition diagram.
3. Write an algorithm to interpret an NFA and report if a given string matches the NFA. Illustrate with an example.
4. What is a move set? What is an epsilon closure set? Give examples. How are they used in reporting if a given string matches a regular expression?