This command-line application allows you to read and test strings against finite automatons. It supports deterministic finite automatons (DFA), non-deterministic finite automatons (NFA), and pushdown automatons (PDA).
The alphabet can not consist of words. Only single characters may exist in the alphabet.
You can push multiple symbols at once, however you cannot consume multiple symbols at once.
Make sure you have the following dependencies installed:
- Python 3.x
- Clone the repository:
git clone <repository_url>
- Navigate to the project directory:
cd <project_directory>
- (Optional) Create and activate a virtual environment:
python -m venv venv
source venv/bin/activate
You can use the application through the command-line interface. Available commands are:
exit
: Exit the program.load <file_path>
: Load a DFA/NFA from a text file.test <input_string>
: Test an input string against the loaded DFA/NFA.lastpath
: Print the last path used to process a string through the DFA/NFA.info
: Print information about the loaded DFA/NFA.help
: Display the list of available commands.
To run the application, execute the following command:
python <filename.py>
Replace <filename.py>
with the name of the Python file containing the code.
Here are some examples of how to use the application:
-
Load an automaton from a file:
load example.txt
Replace
example.txt
with the path to the file containing the automaton. -
Test an input string against the loaded automaton:
test abc
Replace
abc
with the input string you want to test. -
Print the last path used to process a string through the automaton:
lastpath
-
Print information about the loaded automaton:
info
-
Exit the program:
exit
The automaton file should follow a specific format. Here is an example of the format (labels omitted):
An example format of a simple deterministic automaton would be as follows. Multiple examples are included (pda.txt, marmalade.txt, and threezeros.txt)
Alphabet: {a,b,c} // Comment
States: {q0,q1,q2,q3}
// A discarded line
Start State: q0
Accept States: {q3}
Transitions: (q0,a)->q1
(q1,b)->q2
(q2,c)->q3
// The last comment is taken as a machine description.
- The
Alphabet
line lists the symbols in the alphabet, separated by commas. - The
States
line lists all the states in the automaton, separated by commas. - The
Start State
line specifies the start state of the automaton. - The
Accept States
line lists the accept states of the automaton, separated by commas. - The
Transitions
section defines the transitions between states. Each transition is specified on a separate line in the format(source_state,input_symbol)->target_state
.
The format gets more complex for pushdown automatons: Examples included in pda.txt, and twoandthree.txt.
Alphabet: {0,1} // Comment
Stack Alphabet: {0,1}
States: {q1,q2,q3,q4}
Initial State: q1
Accept States: {q4}
Transitions: (q1,):(,$)->q2
(q2,):($,)->q4
// The last comment is taken as a machine description.
in addition to identical function above, there is one additional line that must be present for a PDA, and the formatting is extended.
-
The
Stack Alphabet
line lists the symbols in the stack alphabet, separated by commas. -
The
Transitions
section follows the format:(Source_State, Input Symbol):(Consume_Symbol, Push_Symbol) -> Result_State
- A consume operation is a pop operation.
- You may push more than one character at once, but you may only consume one character at a time.
This project is licensed under the MIT License.
This application was developed using the DFA/NFA object implementation provided in the code.