Recall from your first CS theory course the idea of a finite automaton: for a given alphabet, a FA consists of a set of states, subset of the states designated as accepting states, a single state designated as the initial state, and a relation called the next-state relation that governs the behavior of the FA when it is in a given state and observing a particular symbol from the input alphabet.
In a deterministic FA (DFA) the next-state relation maps a given state and symbol to at most one next state. A DFA accepts an input if, after having completely processed in the input, the DFA is in an accepting state.
In non-deterministic FA (NFA) the next-state relation may map a given state and symbol to more than one next state. An NFA accepts an input if, after having completely processed the input, it is possible for the NFA to be in an accepting state by making the correct choice of transition rule at each step (the "correct" choice is not known a priori).
Problem 1: build a set of types and/or datatypes appropriate for representing DFAs. Think ahead to how you would modify these types/datatypes to represent NFAs. Use your types to build DFAs to recognize (accept/reject) 1) strings over the alphabet {0,1}, such that each 0 has a 1 immediately to its left; 2) strings over {0,1} such that each 0 has at least 2 1's immediately to its right. Define a function
acceptDFA :: DFA -> String -> Boolthat returns True if the DFA accepts the string and False if it doesn't.
Problem 2: extend your types/datatypes of problem 1 to represent NFAs. (Use a different set of type/datatype declarations with distinct names -- I want to see both your DFA and NFA versions.) Use your types to build an NFA to recognize strings over {0,1} containing either two consecutive 0's or two consecutive 1's (or both).
For problem 2, use the "non-deterministic computation" interpretation of the List monad to implement the function
acceptNFA :: NFA -> String -> Bool
What problem can you foresee with using this approach (List monad) to implement NFAs in practice.
Work in groups of 2 or 3 if you wish. Make sure that all group members names are in the code file that you turn in.