Math
Automi finiti
Trasforma espressioni regolari in automi e leggi una sequenza di ingresso.
Da provare
Modifica un'espressione regolare su a e b usando |, *, parentesi e concatenazione. Un NFA di Thompson viene convertito in sottoinsiemi raggiungibili di un DFA. Leggi la parola una lettera alla volta; i doppi cerchi accettano. Limite: 16 stati del DFA.
Equazioni del modulo
Equazioni
Costruzione di Thompson: simbolo, concatenazione, unione, stella di Kleene
stato iniziale del DFA = ε-closure(NFA, stato iniziale)
δ(S,c) = ε-closure({q : p ∈ S e p —c→ q})
Un sottoinsieme accetta se e solo se contiene lo stato di accettazione dell'NFA
