🤖 ProjetAEF — Finite State Automata in Python

A Python academic project implementing a complete Finite State Automaton (FSA/AEF) library with a graphical interface. Covers the full theoretical pipeline: reading automata from files, word recognition, completion, determinization, minimization, and regular expression conversion.

ING1 GIA1 — Groupe 2 | CY Tech

Authors: Bezet Camille, Salaville Erwan, Fortier Théo, El Mabrouk Imen, Garcia-Megevand Thibault

---

✨ Features

Module	File	Description
Automaton loading	automaton_q1.py	Read and parse an automaton from a .txt file
Word recognition & completion	recognize_complete_q2_q3_q4.py	Check if a word is recognized; complete the automaton
Determinization	determinist.py	Convert an NFA to a DFA
Minimization	minimal_q12.py	Minimize a DFA using partition refinement
Regex conversion	regex_q8_q9_q10.py	Convert automaton to a regular expression
Extended automaton ops	automaton_q7.py	Additional automaton operations
Graphical interface	interface.py	Tkinter GUI for interactive automaton manipulation
Test suite	test.py / automatons_tests.py	Unit tests for all implemented functions

---

📂 Project Structure

ProjetAEF/
├── index.py                        # Entry point — launches the GUI
├── interface.py                    # Tkinter graphical interface
├── automaton_q1.py                 # Q1 — Automaton loading
├── recognize_complete_q2_q3_q4.py  # Q2/Q3/Q4 — Recognition & completion
├── determinist.py                  # Q5/Q6 — Determinization
├── automaton_q7.py                 # Q7 — Extended operations
├── regex_q8_q9_q10.py              # Q8/Q9/Q10 — Regex conversion
├── minimal_q12.py                  # Q12 — Minimization
├── excise.py                       # Helper utilities
├── debut.py                        # Initial scaffolding
├── test.py                         # Test runner
├── automatons_tests.py             # Test cases
├── automate1.txt                   # Sample automaton file
├── test.txt                        # Test automaton + expected results
└── AEF_Python-ING1GIA1_Groupe2.pdf # Full project report (French)

---

🚀 Getting Started

Prerequisites

• Python 3.x
• Required libraries:

pip install pandas tk

tkinter is included with most Python installations. If not, install it via your system package manager (e.g. sudo apt install python3-tk on Ubuntu).

Launch the graphical interface

python3 index.py

Run the test suite

python3 test.py

---

📄 Automaton File Format

Automata are described in plain .txt files. See automate1.txt and test.txt for examples of the expected format. The test.txt file also includes the expected output for each function, which can be used to verify correctness.

---

🧠 Theoretical Background

This project covers core concepts from formal language theory:

• NFA / DFA — Non-deterministic and deterministic finite automata
• Completion — Adding a sink state to make a total transition function
• Determinization — Subset construction algorithm (NFA → DFA)
• Minimization — Myhill-Nerode / partition refinement (DFA → minimal DFA)
• Regular expressions — State elimination method to derive a regex from an automaton