In this project you will implement a Deterministic Pushdown Automata $($PDA$)$ simulator. The input is a file containing a description of some PDA $($described below$).$ After constructing the PDA, your program should prompt the user for a string to evaluate. Your program$$s output is a computation and an indication of acceptance or rejection.

You may implement your code in either Java or Python, but you must implement the functionality of the PDA yourself. Do not use any packages or classes that you may find in the APIs.

$-$ Language:

L $=\{$aibj : j $=4$i $+2\}$

L $=$ bottom of stack

$\{$e$\}=$ empty string

$-$ My file "PDA.txt$"$:

$5$

$4$

a b

a L

$0$ a$/$L $->1/$aaaaL

$0$ b$/$L $->3/$L

$1$ a$/$a $->1/$aaaa

$1$ b$/$a $->2/\{$e$\}$

$2$ b$/$a $->2/\{$e$\}$

$2$ b$/$L $->3/$L

$3$ b$/$L $->4/$L

$-$ Explanation of the PDA input file

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 missing input$/$popped off stack pair will transition to the dead state and push the same character that was just popped off the stack.$$

$-$Sample Output:

$>>>$Loading PDA.txt$...$

$>>>$Please enter a string to evaluate:$$

aabbbbbbbbbb

$>>>$Computation...

$0,$ aabbbbbbbbbb$/$L $->1,$ abbbbbbbbbb$/$aaaaL

$1,$ abbbbbbbbbb$/$a $->1,$ bbbbbbbbbb$/$aaaaaaaaL

$1,$ bbbbbbbbbb$/$a $->2,$ bbbbbbbbb$/$aaaaaaaL

$2,$ bbbbbbbbb$/$a $->2,$ bbbbbbbb$/$aaaaaaL

$2,$ bbbbbbbb$/$a $->2,$ bbbbbbb$/$aaaaaL

$2,$ bbbbbbb$/$a $->2,$ bbbbbb$/$aaaaL

$2,$ bbbbbb$/$a $->2,$ bbbbb$/$aaaL

$2,$ bbbbb$/$a $->2,$ bbbb$/$aaL

$2,$ bbbb$/$a $->2,$ bbb$/$aL

$2,$ bbb$/$a $->2,$ bb$/$L

$2,$ bb$/$L $->3,$ b$/$L

$3,$ b$/$L $->4,\{$e$\}/$L

$4,\{$e$\}/$L $$

ACCEPTED

$>>>$Please enter a string to evaluate:

b

$>>>$Computation...

$0,$ b$/$L $->3,\{$e$\}/$L

$3,\{$e$\}/$L

REJECTED

$>>>$ Please enter a string to evaluate:

ccc

INVALID INPUT

$>>>$Please enter a string to evaluate:$$

Quit

$>>>$Goodbye!

$-$Rubric:

Code compiles

Code reads a file in the local directory called $$PDA$.$txt$$

Code prompts user for an input string

Correctly produces the computation for input strings

Correctly accepts a valid string

Correctly rejects invalid strings

Handles invalid input characters by indicating the character and rejecting the string

In Python please, thank you.