This project is designed to perform various operations on Finite Automata (FA), including reading, displaying, standardizing, determinizing, completing, minimizing, and testing word recognition
The program is divided into several stages:
- Reading a FA: The program reads a FA from a text file, stores it in memory, and displays it on the screen
- Displaying FA Information: The program checks if the FA is deterministic, deterministic and complete, or standard, and displays the results
- Standardization: If the FA is not standard, the program can standardize it on demand
- Determinization and completion: If the FA is not complete or deterministic, the program can convert it into an equivalent complete deterministic FA
- Minimization: The program can minimize a complete deterministic FA
- Word Recognition: The program can test if a given word is recognized by the FA
- Complementary Language: The program can create a complementary automaton of the given FA
- Python 3.x
csvandoslibraries (included in Python standard library)
You have 2 options to install our project. You can install the project using git clone :
git clone https://github.com/timotheetacca/finite_automata_ope.git
You can also directly install the latest release of our project from here
The text file representing an automaton should have the following structure:
2
5
1 0
1 4
6
0 a 1
0 a 0
0 b 0
1 b 2
2 a 3
3 a 4
- Line 1: Number of symbols in the automaton's alphabet
- Line 2: Number of states
- Line 3: Number of initial states, followed by the initial states separeted by space
- Line 4: Number of final states followed by the final states separeted by space
- Line 5: Number of transitions
- Lines 6 and beyond: Transitions in the form
<source state> <symbol> <target state>
All the results of the FA tests are available in the fa_result file, in the following format:
- Display information
- Display the classic FA
- Display the complete and determinized FA
- Display the minimized FA
If you'd like to use the program's functions, here are a few examples
# Initialize the FA with a file path
fa = finite_automata("fa_example.txt")
# Read and display the FA
fa.get_fa_information()
fa.get_csv_from_fa("fa_output.csv")
# Check if the FA is deterministic
fa.is_deterministic(display=True)
# Standardize the FA if it is not standard
if not fa.is_standard():
fa.standardization()
# Determinize and complete the FA
fa.determinization_and_completion("determinized_fa.csv")
# Minimize the FA
fa.minimized_fa()
# Create a complementary FA
fa.complementary()If you have any feedback, please reach out to us at timothee.tacca@efrei.net, kim-lan.tran@efrei.net, julien.oudin@efrei.net ,thomas.loesch@efrei.net or daif.moindjie@efrei.net