[Rule] Procesul de Toleranță
Inițial, aparatul se află în starea de pornire. Automată citește caracterele, la rândul său. Când citiți următoarele tranzițiile simbol aparatul la o stare în care - starea curentă a automatului. Procesul continuă până când, până când ajunge la sfârșitul cuvântului de intrare.
Noi spunem că autorizațiile automatului (Eng. Acceptați) cuvântul în cazul în care, după încheierea procesului de mai sus vor fi automat în starea de acceptare.
Notă. În cazul în care în orice punct din starea sa actuală nu este considerat un simbol al tranziției, vom presupune că aparatul nu permite cuvântul. Când puse în aplicare în loc de o analiză separată a cazului este uneori convenabil să se introducă un neterminal „diavol vertex“ dummy (de asemenea impas. Stoc), toate acestea conduc la o tranziție este în sine, și să înlocuiască toate tranzițiile inexistente tranzițiilor în „top diavolului“.
Reprezentarea [Rule] Metode
[Regula] Diagrama de tranziție
Diagrama de tranziție - un grafic ale cărui noduri corespund stările automatului, și marginile - tranzițiile între state.
- starea neterminal - starea terminalului, săgeata indică starea inițială.
model de căutare Mașină în text pentru rând.
Automată a primit linii non-goale de simboluri alternative, și fără „vârfuri diavolului.“
primirea automată șir non-gol de caractere alternative și un „top diavolului“.
[Rule] tranzițiilor Tabelul
tabelul de tranziție, dând funcția de vizualizare tabelă.
- ,
- ,
- ,
- ,
- - funcția de tranziție, reprezentată de tabel:
limbi [Edit] Automatul
Descrierea instantanee (configurare) (Eng instantaneu.) - pereche, unde - starea curentă, - caracterele rămase.
Noi spunem că este derivabilă din configurația într-o singură etapă, în cazul în care:
- ,
- .
Noi spunem că configurația derivabilă dintr-un număr finit de pași, în cazul în care
- ,
- .
.
Un set este numit limbaj mașină (limba ing. Automatelor lui).
Cu alte cuvinte, limba mașinii este mulțimea tuturor le-a permis să cuvinte. Limba este un automat arbitrar în cazul în care există un DFA, care să permită celor și numai acele cuvinte care aparțin limbii.
Multe limbi toate DFA definește o multitudine de limbi de stat.
[Articolul] izomorfism două automate
Mașini numite izomorfă (engleză izomorfe.), În cazul în care există o bijectie între vârfurile lor, astfel încât toate tranzițiile sunt conservate, statele terminale corespund terminalului, inițial - inițial
două automat finit determinist este setat. Stabili dacă acestea sunt izomorfe. Este garantat faptul că toate statele utilaje accesibile.
[Articolul] Algoritmul
Din definiția rezultă că în cazul în care mașinile sunt izomorfe, acesta poate fi starea lor numerotată într-un fel, astfel încât nodurile din mașini diferite, cu aceleași numere sunt egale - adică, în fiecare dintre aceste două state, există o tranziție de la un stat cu același număr, care și tranziția de aceeași literă într-un alt stat. Prin urmare, putem rezolva unele de numerotare, de exemplu, pentru a trece adâncimea de caractere în ordine lexicografica și trebuie doar să verificați starea cu aceleași numere de egalitate. În cazul în care toate statele sunt egale, atunci mașinile vor fi egale, în acest caz, se va urmări izomorfismul a două mașini. Algoritmul asymptotic coincide cu by-pass asimptotică în profunzime, adică unde - numărul total de noduri în mașinile - numărul total de muchii.
[Articolul] pseudocod
- - o mulțime de cupluri. în cazul în care,