„Determinisztikus véges állapotú gép” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
a Bot: következő hozzáadása: pt:Autômatos finitos determinísticos |
a kisebb formai javítások |
||
7. sor:
A DFA-t tekinthetjük egy speciális [[Turing-gép]]nek, amely nem tudja az olvasófejet mozgatni, és csak előre képes mozgatni a szalagját.
== Formális meghatározás ==
Egy DFA a következő [[n-es|ötö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]]ok halmaza.
24. sor:
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''-et elfogadja, ellenkező esetben visszautasítja.
Az automata által elfogadott stringek halmaza egy [[formális nyelv|nyelv]]i forma, az a nyelv, amelyet a DFA felismer.
== Példa ==
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'', Σ, ''T'', ''s'', ''A''), ahol
* Σ = {0, 1},
* ''S'' = {''S''<sub>1</sub>, ''S''<sub>2</sub>},
* ''s'' = ''S''<sub>1</sub>,
* ''A'' = {''S''<sub>1</sub>}, és
* A ''T'' átmeneti függvényt a következő [[állapotátmeneti tábla]] határozza meg:
{| border="0" cellpadding="1" align="center"
| || <center>'''0'''</center> || <center>'''1'''</center>
50. sor:
:[[Fájl: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.
''M'' nyelve egy [[szabályos nyelv]]vel írható le, egy adott [[szabályos kifejezés]] segítségével:
<!-- The \,\! is to keep the formula rendered as PNG instead of HTML to ensure consistency of representation. Please don't remove it.-->
65. sor:
== Források ==
* [[Michael Sipser]]: ''Introduction to the Theory of Computation''. PWS, Boston. 1997. ISBN 053494728X. Section 1.1: Finite Automata, pp. 31–47. Subsection "Decidable Problems Concerning Regular Languages" of section 4.1: Decidable Languages, pp. 152–155.
* Bach Iván: ''Formális Nyelvek''. Egyetemi tankönyv, második kiadás, Typotex Kiadó, 2001. 2.2. Fejezet: Determinisztikus és nemdeterminisztikus véges automaták
| |||