„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ó |
a kozmetikai javítások |
||
12. sor:
Egy DFA a következő [[n-es|5-ös]]sel írható le:
(''S'',
* (''S'') az állapotok véges halmaza
* (
* (''T'' : ''S'' ×
* (''s''
* (''A''
Legyen '''M''' egy DFA amelynél '''M''' = (''S'',
''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>''
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'',
*
*''S'' = {''S''<sub>1</sub>, ''S''<sub>2</sub>},
*''s'' = ''S''<sub>1</sub>,
50. sor:
''M'' [[állapot diagramm]]ja :
:[[
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.
|