DFA-minimal
Un algoritm care are ca input un DFA si face transformarea acestuia pana intr-o forma minimala a sa. Aceste are la baza Teorema lui Myhill-Nerode. Teorie: https://www.geeksforgeeks.org/minimization-of-dfa-using-myhill-nerode-theorem/?ref=rp
Cum functioneaza?
- separam starile in 2 grupe: stari nefinale si stari finale.
- marcam starile de forma (Qa, Qb), unde Qa este stare finala, iar Qb este stare nefinala.
- daca (Qa, x) si (Qb, x) sunt marcate, atunci vom marca si (Qa, Qb).
- repetam procesul anterior pana ce nu vom mai aduce nicio modificare.
Observatii:
- grupa initiala este grupa ce contine starea initiala.
- grupele finale sunt cele ce contin o stare finala.
