CSC173: Project 1

0. Finite automata are simple computing “devices” that recognize patterns, as seen in class
   and in the textbook.
   For this project, you must implement a framework that you (or any programmer) can use
   to define and execute automata in order to recognize patterns. The framework comes
   directly from the formal model of automata.
   Using your framework, you should be able to define and execute any finite automaton
   for any pattern that can be recognized by a finite automaton.
   Note: The project is not about writing programs that recognize specific patterns. Yes,
   you will use your framework in a program that creates and executes a number of different
   automata (details below). But the specific patterns are not the point of the project. In
   fact, I recommend that you not even think about the specific patterns as you design and
   implement the framework.
   Process not product.
   Once you have the framework, for each pattern that you need to recognize, you must:
   • Design the automaton for the pattern, probably by drawing its graph on your white
   board or on paper.
   • Translate the graph into the elements of the formal model of automata, in particular
   the transition function/table that comes from the edges of its graph.
   • Write a function that uses your framework to create and return an instance of an
   automaton with that definition.
   • Demonstrate your framework by running such an instance interactively, asking the
   user for input strings, running the automaton on the strings, and printing the results.
   The rest of this document gives you the specific requirements as well some suggestions
   for how to get started. Read the requirements and instructions carefully. You must meet
   the requirements to get the points.
   If you are new to C and haven’t yet done Homework 0.0, you should do that now
   
   

   Part 1: Deterministic Finite Automata (50%)

   Implement a framework for defining and executing deterministic finite automata (DFAs),

   as follows:

   • You must define a DFA data structure and whatever functions you need to create,

   inspect and configure instances (constructor, accessors, and mutators).

   • For each required DFA (see below), you must have a function that creates and

   returns a properly-configured DFA. For example, for a DFA that accepts strings

   containing “abc”:

   DFA* DFA_for_contains_abc()

   • You must have a function that can execute any DFA on a given input string and

   return true or false (accept or reject). For example:

   bool DFA_run(DFA* dfa, char* input)

   • You must have a function that can run any DFA in a “Read-Eval-Print Loop” (REPL):

   prompting for user input, running the DFA on the input, and printing the result. For

   example:

   void DFA_repl(DFA* dfa)

   • Your main function must run instances of each of the required DFAs in a REPL

   one after the other, printing informative messages.

   You must demonstrate your DFA framework on all of the following languages:

   (a) Exactly the string “dfa” (without the quotes)

   (b) Strings that start with the sequence “cat” (without the quotes).

   (c) Strings containing exactly two 2’s (and perhaps other characters also).

   (d) Binary input (input consisting of only 0’s and 1’s) where there are an even number

   of 0’s and an odd number of 1’s. (If you are not sure whether zero is even or odd,

   please got to study session.)
   
   

   Part 2: Nondeterministic Finite Automata (30%)

   Implement a framework (or extend your previous framework) to allow the definition and

   execution of non-deterministic finite automata (NFAs), as follows:

   • You must define an NFA data structure and whatever functions you need to create,

   inspect and configure instances (constructor, accessors, and mutators).

   • For each required NFA (see below), you must have a function that creates and

   returns a properly-configured NFA. For example, for an NFA that accepts strings

   ending with “ing”:

   NFA* NFA_for_ends_with_ing()

   • You must have a function that can execute any NFA on a given input string and

   return true or false (accept or reject). For example:

   bool NFA_run(NFA* nfa, char* input)

   • You must have a function that can run any NFA in a REPL, prompting for user

   input, running the NFA on the input, and printing the result. For example:

   void NFA_repl(NFA* nfa)

   • Your main function must run each of the required NFAs in a REPL one after the

   other, printing informative messages.

   You must demonstrate your NFA framework on all of the following languages:

   (a) Strings ending in ked, such as “liked” and “sacked”, but not, for example,

   “shakedown”.

   (b) Strings containing ath, such as “athletic”, “bather”, and “path”.

   (c) Strings that have more than one o, f, or r, or more than two c’s or n’s, or more than

   three e’s. In this automaton, acceptance means that the input string is definitely

   not a partial anagram of conference, because it has too many of some letter.

   Note that this automaton does not accept all strings that are not anagrams of

   conference. See FOCS Ex. 10.6 and Fig. 10.14 for a similar automaton and the

   story behind it. The automaton in the book accepts when the criterion is met, but

   you will probably need to do something slightly different to accept an entire string

   meeting the criterion
   
   

   Part 3: Equivalence of DFAs and NFAs (20%)

   Implement a translator function that takes an instance of an NFA (any NFA) as its only

   parameter and returns a new instance of a DFA that is equivalent to the original NFA

   (accepts the same language), using the standard algorithm as seen in class and in the

   textbook. For example:

   DFA* NFA_to_DFA(NFA* nfa)

   Demonstrate your NFA to DFA translator by using the first two NFAs from Part 2, trans

   lating them to DFAs, printing out how many states are in the resulting DFA, and running

   it on user input as described below. That is, you will have three functions that produce

   NFAs for Part 2 of the project. For the first two of those, pass the NFA that they return to

   your converter and run the resulting DFA using your DFA REPL function.

   You should also try to convert the third NFA from Part 2. You might want to think about

   (a) the complexity of the Subset Construction itself, and (b) the implementation of the

   data structures used by your translator, such as lists and sets. You can’t beat (a), see

   FOCS pp. 550–552, but you could profile your code and try to do better on (b).

   FWIW: My implementation using IntHashSet on an M1 MacBook Pro with 32GB

   of RAM took about ten minutes to convert the “Washington”-based NFA from FOCS

   Ex. 10.6