[Edit] Descriere
Luați în considerare un alfabet finit. Să - un set de cuvinte în alfabet. mașină Sufix - în cazul în care un set
- - un set finit de stări,
- - starea inițială,
- - un set de stări terminale,
- - funcția de transfer.
Pentru și determinate în cazul în care statul este accesibil de tranziția de la simbolul. Funcția de tranziție de cuvinte și înseamnă că, dacă există, statul a fost atins după ce a citit cuvintele statului. Aparatul detectează limba.
Sufix pentru linie automata este un graf orientat aciclic. cu un nod inițial și o multitudine de noduri terminale, marginile care cu simboluri sunt marcate:
- în partea de sus a graficului - aparatul de stat, iar marginile - tranzițiilor
- fiecare tranziție în mașină - margine în grafic, marcată de unele simbol, și toate muchiile care provin dintr-un vârf au etichete diferite,
- unul dintre state este numit inițial, pentru că a realizat toate celelalte state,
- unul sau mai multe state sunt marcate ca terminalul - dacă te duci la starea inițială la terminalul de orice fel și, astfel, a scrie simboluri pe perioada de tranziție, obținem unul din șirul sufixul.
EXEMPLU automaton sufix pentru rând.
Stare primește linie în cazul în care există o cale de la starea inițială astfel încât, atunci când scrie secvențial litere la marginile în calea, de a primi linie.
Masina are un șir de caractere, în cazul în care primește cel puțin unul dintre statele finale.
Deoarece aparatul este determinist, atunci fiecare cale corespunde liniei.
În cazul în care se iau două linii și o stare de orice mașină, apoi pentru orice linii de coarde, și a acceptat sau nu a fost acceptată în mod automat, în același timp. Într-adevăr, indiferent de modul în care am ajuns la stat, dacă vom Hai să ieșim din el pe calea corespunzătoare liniei, vom putea spune exact în ce stare ne (în special, dacă acesta va fi definitivă). Aceasta înseamnă că orice stat corespunde unei multitudini de rânduri, pe care le traduce într-unul din statele finale.
Setul se numește starea de contextul potrivit.
Contextul este definit drept nu numai pentru condiția, dar, de asemenea, pentru liniile pe care le ia - rânduri contextul potrivit coincide cu statul contextul potrivit.
Statele în aparatul nu mai puțin decât contextul juridic diferit în subșiruri, pentru care este construit, iar în aparat se realizează printr-un minim de limita inferioară.
Să presupunem că mașina are două stări și astfel încât. Putem elimina starea și traduce pasaje care duc la starea lui. Am primit o mulțime de rânduri nu se va schimba, prin urmare, putem continua atâta timp cât numărul de state nu este egal cu numărul de contexte potrivite distincte.
Astfel, DFA este minimă, dacă și numai dacă toate contextele potrivite statele sale sunt distincte. Acest context drept sufix automaton reciproc singur rând corespunde unei multitudini de apariții de poziții potrivite linie în șir. Astfel, fiecare mașină de stat primește rândul cu același set de poziții corecte de apariție a acestora și vice-versa, toate șirurile cu o multitudine de poziții adoptate de acest stat.