Three distinct projects from CMSC 410 -- Automata Theory
Deterministic Finite Automata (DFA) simulator. The program prompts the user for a string to evaluate. The output is a computation and an indication of acceptance or rejection.
The DFA will be input from a file named DFA.txt. The file will be in the following format: Line 1: The first line of your file will be a single integer that indicates how many states the DFA contains. A note about states: States are represented by consecutive integers starting from zero. State zero is always the start state. All states of the DFA must be represented; this includes the dead state. Line 2: The second line of the file contains a space-separated list of integers that represent accepting states. Line 3: Alphabet: a space-separated list of characters in the DFA's alphabet. Lines 4 – end: Transitions: These will be represented in a table indexed by state number and character. The input file will have one line for each row of the table. Each row consists of integers that represent the states the machine will transition to on each of the alphabet characters. If the DFA has seven states and three characters, there will be seven lines containing three integers each. The first row corresponding to the transitions from state zero, the second from state one, etc. Note that all transitions must be represented; do not assume a missing transition for a character is to the dead state.
Deterministic Pushdown Automata (PDA) simulator. The program prompts the user for a string to evaluate. The output is a computation and an indication of acceptance or rejection.
The PDA will be input from a file named PDA.txt. The file will be in the following format: Line 1: The first line of your file will be a single integer that indicates how many states the DFA contains. A note about states: States are represented by consecutive integers starting from zero. State zero is always the start state. All states of the PDA must be represented; this includes the dead state. Line 2: The second line of the file contains a space-separated list of integers that represent accepting states. Line 3: Input Alphabet: a space-separated list of characters in the language’s alphabet. Line 4: Stack Alphabet: a space-separated list of characters in the stack’s alphabet. This must include a symbol to indicate the bottom of the stack. This symbol is always the last symbol in the stack alphabet. Assume that the stack beings with only bottom-of-stack symbol in it. Lines 4 – end: Transitions: These will be on subsequent lines. The input file will have one line for each valid. Each transition consists of the number of the state, a pair consisting of the input character and the character that was popped off the top of the stack, an arrow, and a pair consisting of the state and the character pushed onto the stack. Note that only the valid transitions are represented; assume that a just popped off the stack.missing input/popped off stack pair will transition to the dead state and push the same character that was
Turing Machine (TM) simulator. I struggled the most on this specific project. The simulator will compute a function on the input. When the TM halts, the tape will contain the result of the function. The input is a TM and an input string. The output consists of a series of configurations.
The TM will be input from a file named TM.txt.
- The first line of your file will be a single integer that indicates how many states the TM contains. States are represented by consecutive integers starting from zero. State zero is always the start state.
- The second line contains the number of the halting state.
- The remaining lines represent the transitions. These will be stored in a table indexed by state number and character. The input file will have one line for each row of the table. Each row represents one transition, indicating the character to write on the current cell, the direction to move the read‐write head, and the state to transition to. Blank cells will be represented using an underscore ( _ ).