** URGENT **

Finite Automata - WorkShop 20

Language - C (-std=c99 -Wall -Werror)

Intro The purpose of this WorkShop is for you to demonstrate your understanding of the formal model of finite automata by designing and implementing a framework that programmers can use to define and execute automata. You will then demonstrate the use of your framework by using it to create and execute a number of automata that each recognizes a given pattern.

Part 1: Deterministic Finite Automata You must 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: 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 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 automaton (b) Strings ending with ed, such as Fred (c) Strings containing exactly two 2s, such as 21a72 (d) Binary input with an odd number of both 0s and 1s (e) At least one other interesting pattern (hopefully different from other students)

Part 2: Nondeterministic Finite Automata You must 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: 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 Read-Eval-Print Loop (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 head, such as ahead. (b) Strings containing zz, such as jazzy and zzz. (c) Strings whose letters cannot be anagrams of the word woodpecker since they have more than one c, d, k, p, r, or w, or more than two es or os. (d) At least one other interesting pattern (hopefully different from other students)

Part 3: Equivalence of DFAs and NFAs You must 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. For example: DFA* NFA_to_DFA(NFA* nfa)

Demonstrate your NFA to DFA translator by using the first two NFAs from Part 2, translating 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 four functions that produce NFAs for Part 2 of the WorkShop. For the first two of those, pass the NFA that they return to your converter and run the resulting DFA on user input as described below.

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.

General Requirements 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.

Note that you do not need to be able to read in the specification of a pattern (for example as a regular expression) and create the instance of the automaton data structure. You may hard-wire it, meaning that your automaton-creating functions each create their specific automaton using your framework.

You must submit code that compiles into a single executable program that addresses all parts of the WorkShop. Your program must print to standard output (printf, etc.) and read from standard input (scanf, fgets, but do not use gets).

Furthermore, your program should pass valgrind with no error messages.

Sample Execution The following is an example of roughly what your program should look like when it runs. Note that it is your responsibility to ensure that we can understand what your program is doing and whether thats correct. You should always prompt for input. You should always print back the users input as confirmation. You should make sure the results are clearly visible.

CSC173 Project 1 by George Ferguson

Testing DFA that recognizes exactly "csc173"... Enter an input ("quit" to quit): csc Result for input "csc": false Enter an input ("quit" to quit): csc173 Result for input "csc173": true Enter an input ("quit" to quit): quit

Testing DFA that recognizes an even number of 9s... Enter an input ("quit" to quit): 987123 Result for input "987123": false Enter an input ("quit" to quit): 9999 Result for input "9999": true Enter an input ("quit" to quit): quit ...

Code Bundle - bit.ly/3fZYAmq We have provided the following code in a bundle for your use if you want:

DFA.h, NFA.h: Example header files for possible implementations of both DFAs and NFAs. These give you an idea of a possible API for your own implementation, as well as how to specify (partial) data types and (external) functions in header files. You are welcome to use them, change them, ignore them, whatever. IntHashSet: Full code for an implementation of a set of ints using a hashtable with linked-list buckets. BitSet: Full code for an implementation of a set of ints using a bit-mask method. This is faster than a hashtable but only works for ints between 0 and either 31 or 63, depending on your platform. I recommend that you NOT use this. LinkedList: Full code for a generic implementation of a linked list that can store any reference (pointer) type. Might be useful now or in the future. Use at your own risk.

You have to create a program in C and implement all the requirements mentioned above with help of the files (link provided) and implement them as per your need.

If you need more information, please tell me which information do you need specifically.

All the parts are of just ONE single question and can only be implemented combinedly so please answer all of the parts. I cannot post them separately because of that reason. I will 100% upvote if you do that, I promise.

Transcribed image text