Description
This programming assignment will be extended in future assignments, so you should try to ensure that it is adaptable to maximize code reuse. Use a Visual C++ Win32 Console Application project. Note: You may also use C# .NET, however we will use C++ in class.
For this assignment, your program should read in a deterministic finite automata (some transitions may be left undefined), followed by one or more strings. Your program should run each of the input strings through the automata and output if the string is part of the language defined by the automata.
The input is provided by a text file, read through stdin by your program. The format of the input file is as follows:
comment
number of states
current state, input symbol, next state
…
F: final states, separated by commas
strings
For example:
‘Ends in a
2
S, a, A
S, b, S
A, a, A
A, b, S
F: A
aba
bbaabba
bbabab
aaaab
b
a
The machine will begin in the state listed with the first transition. In this example ‘S’. The final states will be listed at the end of the automata and marked with ‘F:’ (F will never be a state). Your program does not need to handle incorrectly formatted files.
Following the final state will be the list of strings to run through the machine. If a transition is not defined when processing a given input string, you should reject the string. The input alphabet will consist of only the letters ‘a’ and ‘b’.
The program should output ‘accept’ or ‘reject’, followed by a tab, followed by the string to indicate if the string was accepted by the machine. For example:
accept aba
accept bbaabba
reject bbabab
reject aaaab
reject b
accept a
Turn in your source code by removing the bin and obj directories and then zipping the folder containing the solution and all sub-folders. Name the file CST229_Assign2_your_name.zip, where “your_name” is really YOUR NAME. For example, I would name my zip file “CST229_Assign2_pete_myers.zip”. Submit your zip file on Canvas to turn in your assignment.