„Determinisztikus véges állapotú gép” változatai közötti eltérés

[nem ellenőrzött változat][nem ellenőrzött változat]
Tartalom törölve Tartalom hozzáadva
Nincs szerkesztési összefoglaló
SamatBot (vitalap | szerkesztései)
a kozmetikai javítások
12. sor:
 
Egy DFA a következő [[n-es|5-ös]]sel írható le:
(''S'', ΣΣ, ''T'', ''s'', ''A''), ahol
* (''S'') az állapotok véges halmaza
* (ΣΣ) az ábécé-nek nevezett véges halmaz
* (''T'' : ''S'' × ΣΣ → ''S'') az átmeneti [[függvény (matematika)|függvény]]
* (''s'' ∈ ''S'') a kezdő állapot
* (''A'' ⊆ ''S'') az [[elfogadó állapot|elfogadó állapotok]]ok halmaza.
 
Legyen '''M''' egy DFA amelynél '''M''' = (''S'', &Sigma;Σ, ''T'', ''s'', ''A''), és ''X = x<sub>0</sub>x<sub>1</sub> ... x<sub>n</sub>'' a &Sigma;Σ ábécéből alkotott string. '''M''' elfogadja az ''X'' stringet, ha létezik ''S''-ben a átmenetek
''r<sub>0</sub>,r<sub>1</sub>, ..., r<sub>n</sub>'' sorrendje a követekező feltételekkel:
# ''r<sub>0</sub>'' = ''s''
# ''r<sub>i+1</sub>'' = ''T''(''r<sub>i</sub>'', ''x<sub>i</sub>''), minden ''i'' = ''0, ..., n-1''
# ''r<sub>n</sub>'' &isin; ''A''.
 
Amint azt az első feltétel mutatja, a gép az ''s'' állapotból indul. A következő feltétel szerint az egyes állapotok változása a ''T'' átmeneti szabályok szerint következik be. Az utolsó feltétel szerint ha ''X'' utolsó szimbólumának beolvasása után a gép ''A'' állapotban van, akkor ''X'' elfogadott, ellenkező esetben visszautasított.
33. sor:
A következő példa azt mutatja, hogyan tudja az ''M'' automata, amely egy bináris ábécé-vel dolgozik, felismerni azt, hogy a bemeneti stringben páros számú 0 karakter van-e.
 
''M'' = (''S'', &Sigma;Σ, ''T'', ''s'', ''A'') ahol
*&Sigma;Σ = {0, 1},
*''S'' = {''S''<sub>1</sub>, ''S''<sub>2</sub>},
*''s'' = ''S''<sub>1</sub>,
50. sor:
''M'' [[állapot diagramm]]ja :
 
:[[képKép:DFA.png]]
 
Jól látható, hogy az ''S''<sub>1</sub> állapot felel meg annak a helyzetnek, amikor páros számú 0 érkezett eddig a bemeneten, míg ''S''<sub>2</sub> jelzi a páratlan számú 0-t. Egy 1-es érkezése az bemenetre nem változtatja meg az automata aktuális állapotát, és amikor a bemenet elfogyott, az automata állapota mutatja, hogy a bejövő string páros számú 0-t tartalmazott, vagy nem.