Ekvivalencia determinisztikus és nem determinisztikus véges automaták - a
Ekvivalencia determinisztikus és nem determinisztikus véges automaták
Az állam gép - az algoritmusok elmélete, a matematikai absztrakció. lehetővé teszi, hogy leírja az utat egy objektum állapotának függvényében változik a jelenlegi állapot és a bemeneti adatokat. azzal a megkötéssel, hogy az összes lehetséges állapotok véges. Az állam gép egy speciális esete az absztrakt gép.
Vannak különböző megvalósításait véges automata munkát. Például, az állam gép is megadható, pl öt paraméterek: ahol:
- Q - véges halmaza az automata;
- q0 - kezdeti állapot ();
- F - beállított végső (vagy engedélyező) megállapítja, hogy;
- Σ - megengedett bemeneti ábécé (véges halmazát lehetséges bemeneti szimbólumok), amelyek vannak kialakítva sorok géppel olvasható;
- δ - az előre meghatározott leképezés egy több részcsoportja a beállított Q: (néha függvény δ automata átmenetek).
Automatikus kezdődik állapotban q0. olvasás egy karakter karakterlánc. Tekinthető egy szimbólum a gép fordítja az új állapotba a Q összhangban az átmenet funkcióval. Ha befejezésekor az olvasó a bemeneti szó (karakterlánc) gép az egyik elfogadó államok, a „hozott” automatikusan. Ebben az esetben azt mondjuk, hogy nyelvhez tartozik a gép. Ellenkező esetben a „elutasított”.
Más módon leírására
- A állapotdiagram (vagy néha átmeneti grafikon) - grafikus ábrázolása állapotok egy halmaza és az átmeneti függvény. Ez egy betöltött egyirányú grafikonon. csúcsok - SC állapotban, az ív - az átmenetet az egyik állapotból a másikba, és a terhelés - szimbólumok, amelyek alapján egy adott átmenetet. Ha az átmenetet a Q1-Q2 végezhetjük a megjelenése egy több karakter, több mint az ív kell címkézni mindet.
- átmenet táblázat - táblázat nézet funkció δ. Jellemzően ebben a táblázatban minden sor megfelel egy állam, és az oszlopot - egy érvényes bemeneti jel. A sejt a kereszteződésekben a sor és oszlop rögzített intézkedéseket, hogy el kell végeznie az automatikus, ha egy olyan helyzet, amikor ebben az állapotban, ő kapta a karakter beviteli.
determinizmus
Véges gépek vannak osztva determinisztikus és nem determinisztikus.
Determinisztikus véges állapotú gép
- Determinisztikus véges automata (DFA) egy géppel, amelyben minden egyes szekvenciát a bemeneti jelek létezik csak egy állapot, amelynél a gép tudja mozgatni ki a jelenlegi.
- Determinisztikus véges automata (NFA) általánosítása a determinisztikus. Határozatlansági gépek érjük két módja van:
Vannak olyan szakaszok jelölt üres láncot ε
Az egyik állapotból ki néhány olyan részeket, melyek vannak jelölve az azonos szimbólum