Az állam gép - egy
Az állam gép - absztrakt automata kimeneti stream, a számos lehetséges állapotok véges. Az eredmény a gép határozza meg a végső állapot.
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 - több Államok automatánk;
- q0 - kezdeti (Start) állapotban automata ();
- 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 - állapotban SC, a bordák - átmenet egyik állapotból a másikba, és a terhelés - szimbólumok, amelynél az aktív átmenet. Ha az átmenetet a Q1-Q2 végezhetjük a megjelenése egy több karaktert, a diagram ív (ága a grafikon) fel 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
Ha azt az esetet, amikor a készülék beállítása a következő: ahol:
- S - a beállított kiindulási állapotot automata, úgy, hogy;
Aztán ott van a harmadik jele nondeterminism - jelenlétében néhány kezdeti (kiindulási) körülmények között a gép.
Van egy tétel, amely kimondja, hogy „Bármely nem determinisztikus véges automata lehet alakítani egy determinisztikus, hogy nyelvük ugyanaz” (az ilyen gépeket hívják egyenértékű). Azonban, mivel az államok száma a egyenértékű DFA legrosszabb exponenciálisan nő a növekvő mennyiségű kiindulási RNS államok, a gyakorlatban az ilyen determinization nem mindig lehetséges. Ezen túlmenően, egy véges állapotú gép, a hozam általában nem alkalmasak determinization.
Azáltal utóbbi két megállapítás ellenére rendkívül összetett a nem determinisztikus véges automaták, a problémák feldolgozásával kapcsolatos szöveget, ez elsősorban az NCA alkalmazni.
Automaták és reguláris nyelvek
Ahhoz, hogy az automata lehet meghatározni nyelv (szavak halmazának) az ábécé Σ, ez jelenti - az úgynevezett szó, amely, ha belép a gép átmenetek a kezdeti állapotból több államban F.
Kleene tétele kimondja, hogy a nyelvek osztályát, leírható véges automaták egybeesik az osztály reguláris nyelvek. Ezen túlmenően, ez az osztály egybeesik a nyelvek osztálya által meghatározott reguláris nyelvtan.
Speciális programozási nyelvek
- Sorozatos Function Chart SFC (Sequential Function Chart) - grafikus programozási nyelv széles körben használják a programozási ipari logikai vezérlők (PLC).
Az SFC program írja le vázlatosan lépések sorozata, a kombinált átmenetek.
Makettek kidolgozása véges automaták
Véges gépek lehetővé teszik számunkra, hogy állítson össze egy modellt a párhuzamos feldolgozás rendszerek azonban változtatni a több párhuzamos folyamatok olyan modellre van szükség, hogy jelentős változások a modell maga. Ezenkívül egy kísérlet arra, hogy dolgozzon ki egy komplex modell a célgép vezet gyors növekedése az államok száma, amelyek végül teszi a fejlesztés egy ilyen modell rendkívül unalmas. Amint fentebb leírtuk, ez utóbbi probléma megoldható, a felhasználót nem determinisztikus gép.
jegyzetek
Nézze meg, mi az „állam gép” más szótárak:
Az állam gép - egy matematikai modellt az eszköz véges memória. Állami gép feldolgozza a több bemeneti bináris jelek sokaságát kimeneti jelek. Különbséget tenni szinkron és aszinkron áiiapotgépek. Magyarul: véges állapotú gép Lásd ... Pénzügyi szótár
állapotú gép - baigtinis automaták statusas T sritis automatika atitikmenys: angl. véges automata; véges állapotú gép vok. endlicher automata, m; Finalautomat, m rus. állapotú gép, m pranc. automatizálni végleges, m; automatizálni Fini, m; automatizálni terminális, m; ... ... Automatikos termínu žodynas
AUTOMATA END - automatikusan, hogy a cerned állapotok halmaza, és több bemeneti és kimeneti jelek véges. C. a. Ez a modell a tech. eszközök (számítógép, relé eszköz) vagy Biol. rendszer (idealizált. állat idegrendszer). Fontos ... ... Nagy Encyclopedic szótár Polytechnic
Az állam gép memória - az állam gép matematikai modell memória eszközök, akinek a viselkedése függ a bemeneti feltételek, és az előző állapot. A leírás, egy olyan gép nyelvét kezelő rendszerek használt memória, rendszeres ... ... Wikipedia
Moore automata - (automatikus másik fajta) az elméleti számítási az állam gép, a kimeneti jel értékét, amely attól függ, csak a jelenlegi állapotában az automata, és nem függ közvetlenül, ellentétben a Lisztes automatát, a bemeneti értékeket. Moore automata nevű ... Wikipedia
- Programozás: formális nyelvek és fordítóprogramok. Tankönyv középiskolák. Malyavko AA A könyv bemutatja az elméleti alapjait a készülék nyelv (reguláris kifejezések) és szintaktikai (formai nyelvtan) programozási nyelv elemei véges automaták elmélete ... Tovább Vásárolja 1200 rubelt
- Az állam gép. Dzhessi Rassel. Ez a könyv lesz összhangban a rendelését Technology Print-on-Demand technológiát. High Quality Content Wikipedia cikket! Az állam gép - absztrakt automata nélkül kiadási ... Tovább Vásárlás 1147 rubelt
- Programozás: formális nyelvek és fordítóprogramok. Tankönyv középiskolák. Malyavko AA A könyv bemutatja az elméleti alapjait a készülék nyelv (reguláris kifejezések) és szintaktikai (formai nyelvtan) programozási nyelv elemei véges automaták elmélete ... Tovább Vásárlás 1090 UAH (Ukrajna esetében)