Minimizarea DFA

Minimizarea DFA este construirea unui DFA echivalent bazat pe un automat finit determinist (DFA) care are cel mai mic număr posibil de stări.

DFA minim

Pentru orice limbaj obișnuit, există un DFA minim care îl acceptă, adică un DFA cu cel mai mic număr posibil de state. Un astfel de automat este unic până la izomorfism.

Algoritmi

Algoritmul lui Hopcroft

Algoritmul lui Brzozowski

Lasă - DKA. Se notează cu automatul inversat . Se notează prin automatul determinist obținut din procedura de construire a submulților. Următorul rezultat este valabil [1] : ${\mathcal {A}}$ $r({\mathcal {A}})$ ${\mathcal {A}}$ $d({\mathcal {A}})$ ${\mathcal {A}}$

Lăsați aparatul să recunoască limba . Apoi, DFA minim pentru limbă poate fi găsit ca ${\mathcal {A}}$ $L$ $L$ ${\mathcal {A}}_{L}=drdr({\mathcal {A}}).$

Vezi și

Note

↑ Thomas Paranthoën, Ahmed Khorsi, Jean-Marc Champarnaud. Împărțiți și uniți pentru a minimiza: algoritmul lui Brzozowski . nedefinit (2002). Preluat la 27 iulie 2019. Arhivat din original la 27 iulie 2019.

Literatură

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introducere în teoria automatelor, limbaje și calcul, ediția a II-a // ACM SIGACT News. - 01-03-2001. - T. 32 , nr. 1 . - S. 60 . — ISSN 0163-5700 . doi : 10.1145 / 568438.568455 .

Link -uri

Algoritmul lui Brzhozovsky // Wikisummary al Universității ITMO
Minimizare DFA, algoritmul lui Hopcroft (complexitate O(n log n)) // Wikisummary al Universității ITMO

Limbi formale și gramatici formale
Concepte generale	Ierarhia Chomsky Alfabet Cuvânt
Tip 0	Gramatică nelimitată mașină Turing limbaj enumerat Limbajul rezolvabil
Tipul 1	Gramatică sensibilă la context Limbaj sensibil la context Automat delimitat liniar
Tipul 2	Gramatică fără context Gramatică ambiguă Limbaj fără context Automat Pushdown ( determinist ) Lema de creștere Lema lui Ogden Teorema lui Cook
Tip 3	Gramatica obișnuită limbaj obișnuit Expresie uzuala Mașină de stări ( deterministă , nedeterministă ) Minimizarea DFA Determinarea NFA Teorema Myhill-Nerode
analizare	Analizor LL Analizor LR Metoda coborârii recursive Algoritmul Kok-Younger-Kasami