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. You may also use C# .NET, however we will use C++ in class.
For this assignment, your program should read in a deterministic push down automata, 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. You do not need to handle non-deterministic 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 (not including final state F)
current state, action, data, next state
…
strings
For example:
‘Ends in a
2
S, read, a, A
S, read, b, S
A, read, a, A
A, read, b, S
A, read, z, F
aba
bbaabba
bbabab
aaaab
b
a
The end of the input string and empty stack will be marked with ‘z’. There is a single final state, named F. On entering state F, halt all processing on the string and accept the string.
The action will be ‘read’ input from string, ‘pop’ from stack, or ‘push’ onto stack. For a read, the data is the value to check against to move to the next state. For a pop, the data is the value to check against to move to the next state. For a push, the data is the value to place onto the stack.
Example: S, read, a, A
Means, from state S, read the current input letter. If it is an ‘a’, then transition to state A. If the current input letter is not an ‘a’, then this transition does not apply, and another transition should be used. If there is no transition for input ‘a’, then the string is rejected.
Example: X, pop, a, A
Means from state X, pop the stack. If the removed letter from the stack is an ‘a’, transition to state A. If the current input letter is not an ‘a’, then this transition does not apply, and another transition should be used. If there is no transition for input ‘a’, then the string is rejected.
Note that for any given state, you will always perform the same action (read, push, or pop).
If a transition is not defined for the current state of the machine, you should halt and reject the string.
The letter ‘z’ in the machine definition indicates end of input. The letter ‘z’ will never appear in the actual input.
Example: S, read, z, B
Means, from state S, if you are out of input, move to state B.
Example: B, pop, z, F
Means, from state B, if the stack is empty, move to state F and halt. F is the only final state. Accept the string.
The output should be exactly the same format as Assignment 2. 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_Assign3_your_name.zip, where “your_name” is really YOUR NAME. For example, I would name my zip file “CST229_Assign3_pete_myers.zip”. Submit your zip file on Convas to turn in your assignment.