véges automaták
Az állam gép - egy absztrakt gépet. több belső állapotok, amelyek lehetővé természetesen.
Vannak különböző módon meghatározza egy algoritmus véges automata. Például az állam gép úgy van meghatározva, rendezett öt elem az egyes készletek:
- V - bemeneti ábécé (véges halmaza a bemeneti jelek), amelyből a bemeneti szavakat képződik. érzékelt állapotú gép;
- Q - több belső állapotokat;
- q 0> - kezdeti állapotban (q 0 ∈ Q) \ Q)>;
- F - készlet végső, vagy utolsó Államok (F ⊂ Q);
- δ - átmenet funkciót. definíció szerint egy leképezés δ. Q × (V ∪ <ε> ) → Q) \ rightarrow Q>. oly módon, hogy δ (q. a) =
> \, \, R \ >>. azaz az érték az átmeneti függvény a rendezett párt (állami, bemeneti szimbólum vagy egy üres karakterlánc) a készlet minden vonatkozik, amelyben egy adott állam egy átmenet a bemeneti karakter vagy üres string (ε).
Arról, hogy úgy vélik, hogy az állam gép megkezdi az állami q 0> gombot. egymás után kiolvassuk egy karaktert bemeneti szó (input karaktersorozat). Tekinthető egy szimbólum a gép fordítja az új állapotba összhangban az átmeneti függvény.
Olvasás a bemeneti karaktersorozatot x és így az átmenetet, hogy az államtól, az automata elolvasása után az utolsó karaktere bemeneti szó lesz egy bizonyos állapotban q”.
Ha ez a feltétel az utolsó, akkor azt mondjuk, hogy az automatát készített egy x szót.
Más módon leírására szerkesztése
- A állapotdiagram (vagy néha átmeneti grafikon) - grafikus ábrázolása állapotok egy halmaza és az átmeneti függvény. Ez egy címkézett irányított gráf. csúcs - SC az ív - az átmenetet az egyik állapotból a másikba, és ívek címkék - karakterek, amelyekre az átmenet az egyik állapotból a másikba. Ha az átmenetet a Q1-Q2 elvégezhető egy több karakter, mindegyik kell elhelyezni a chart ív.
- á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íti az állapotot, amelyben a gép kell menni, ha ebben az állapotban tartotta a bemeneti jel.
Véges gépek vannak osztva determinisztikus és nem determinisztikus.
- Determinisztikus véges automata (DFA) egy géppel, amelyben nincs ív címke ε (ajánlatot, amely nem tartalmaz karakter), és minden állam bármely szimbólum nem tolható egynél több állam.
- Determinisztikus véges automata (NFA) általánosítása a determinisztikus. gépek határozatlansági érhető el két módon: vagy lehetnek átmenetek jelölt egy üres e-lánc, vagy az egyik állapotból mehet több átmenetet jelöli az azonos szimbólum.
-
Determinisztikus véges állapotú gép
Determinisztikus üres átmenetek
Determinisztikus automatát átmenet az egyik állapotból jelölt az azonos szimbólum
Ha azt az esetet, amikor a gép beállítása a következőképpen: M = (V. K. S. F. δ). ahol S - a beállított kezdeti állapotok automatánk, oly módon, hogy az S ⊆ V. A harmadik jellemző megjelenik a nem-determinizmus - a jelenléte több kezdeti (kiindulási) állapotai az automata M.
Tétel a determinizmus azt állítja, hogy ezzel egyenértékű determinisztikus véges automata (két véges automaták egyenértékű, ha a nyelv ugyanaz) építhető bármely véges automata. 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 szerkesztése
Megadhatja a nyelv (szavak halmazának) a véges állapotú gép a V ábécé. ami azt is elismeri - az úgynevezett beszéd olvasás gép, amely lefordítja a kezdeti állapotban az egyik végső állapot.
Kleene „s tétel kimondja, hogy egy nyelv reguláris akkor és csak akkor, ha hagyjuk néhány állam gép használt nyelvet.
Speciális programozási nyelv szabályai
- Sorozatos Function Chart SFC (Sequential Function Chart) - egy grafikus programozási nyelv. széles körben használt 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 szerkesztése
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 azt a fentiekben megjegyeztük, az utóbbi probléma megoldható, a felhasználót nem determinisztikus gép.
Mit lehet „csinálni” az állam gép és a szekvenciális gép? szabály
A választ a különböző kifejezések, attól függően, hogy az automatikus (P, Machine) autonóm vagy nem [1]. Önálló állapotú gép, kezdve egy bizonyos stroke, csak létrehoz egy periodikus sorozata Államok x (rendre, n-gép - a kimeneti szimbólum szekvenciát y). Ha ez a sorozat áll, csak egy karaktert, akkor az azt jelenti, hogy miután véges számú ciklus a gép eléri az egyensúlyi állapot. Ha ez a szekvencia több szimbólummal, az azt jelenti, hogy a gép halad egymás kimondja megfelelő ezeket a szimbólumokat, majd a munka gép végtelenségig ismételt időközönként. Sőt, bármilyen államok időszakos sorozata véges hosszúságú, mindig önálló állam gép lehet kialakítani, amely, kezdve a második ütem generálja ezt a sorozatot. Semmi más, mint a periodikus ismétlése változatlan állapotban vagy végleges állapot szekvencia, önálló gép „csinálni” nem lehet. Mivel azonban az a tény, hogy az egymást követő végrehajtása egy adott működési ciklus jellemző számos területen a modern technológia, dinamikus rendszerek, amelyek elfogadhatónak tekinthető idealizációt önálló gép, széles körben használják.
A klasszikus példa az automatikus-doll végez bonyolult műveletsorozat, mint az írás a papíron bizonyos szöveget zongorázni előre játszani, stb ...
A modern például szolgálhatnak sok automata, automata vonalak és automatikus vezérlés ciklikus produkciókat. Ha a gép nem önálló, azaz a bemeneti állapot változik verte a ritmust, a válasz arra a kérdésre, hogy mit tud „csinálni”, és nem „nem” az állam gép, lehet adni a különböző feltételek mellett. Például, a válasz lehet nyelvén megfogalmazott bemutató eseményeket. Sőt, a nem önálló állam gépnek vagy szekvenciális gép csak átalakítani a bemeneti szimbólumok sorozatát a sorrendben államok vagy kimeneti szimbólum, és azt mondani, hogy mit lehet és mit nem „do” az állam gép, akkor megtudja, mi az átalakulás szekvenciák lehetnek az állam gép, és hogy mi lehetséges. De ahogy az államok száma (illetve kimeneti szimbólum) Természetesen ez a kérdés egyenértékű egy ilyen kérdés: milyen bemeneti szekvenciák akkor minden lehetséges állapot (vagy mindegyik kimeneti jel). Ez az utolsó kérdés a szempontból elfogadott elmélet véges automaták is az alábbiak szerint történik: milyen események és mit nem képviselhetik az állam gép minden lehetséges államok (vagy az egyes kimeneti jel).
A válasz által adott tételei Kleene. Ez a válasz pontos, mivel a tétel a Kleene létre a szükséges és elégséges feltételei képviselhetoségének egy eseménysorozatot a gép, azaz bevezeti egy speciális szekvenciák a bemeneti jelek - rendszeres készletek. A megjelenése a bemeneti sorozat ilyen szett nevezzük megfelelő rendszeres esemény. Kleene tétel kimondja, hogy az állam gép leírható a rendszeres esemény, és csak azokat. Így a nyelv benyújtásának események a választ a kérdésre, hogy lehet „csinálni” az állam gép egyértelmű: egy olyan gép is csak a rendszeres esemény. Számos fontos készlet bemeneti szekvenciák, amelyek gyakran kell foglalkozni a gyakorlatban nyilvánvalóan szabályos. Például, ismert, rendszeresen állítsa álló bármely véges számú bemeneti szekvenciák véges hosszúságú; több bármilyen periodikus bemeneti sorozat; több végtelenített szekvenciák, amelyek előre meghatározott véges szekvenciák az elmúlt több ciklust, és így tovább. d.
Általában, ha bármilyen önkényesen meghatározott végtelen számú bemeneti sorozatok, a kérdés továbbra is, hogy ez egy szabályos készlet. Az a tény, hogy a fogalom a rendszeres készlet bevezetett indukciós, azaz meghatározott algoritmus felépítésének minden szabályos készletek. Azonban nincs kellően hatékony módon megoldani az inverz probléma, azaz annak megállapítása, hogy minden adott sor szabályos.
Bár Kleene tétel és válaszoljon a kérdésre, hogy mit tehet egy állam gép, de erre a kérdésre válaszolni hatékonyan. Tette az első kísérletei más nyelven a válasz adható hatékonyan. A nyelvi probléma, amely döntő szerepet játszik megszerzésében hatékony válasz arra a kérdésre, hogy mit lehet és mit nem „do” az állam gép kritikus szintézisének első szakaszában a gép, hogy van, hogy válaszoljon a második a fentebb felsorolt kérdésekben. Ha kibontja az osztály dinamikus rendszerek, amit határozza meg a „államgépezet” és a „szekvenciális gép”, a befogadás végtelen memória (végtelen memória modell lehet, például a végtelenített szalag tárolására karakter végtelen számú államok), a dinamikus rendszerek ennek szélesebb osztály (absztrakt osztály ennek a rendszernek nevezzük a Turing-gép) választ arra a kérdésre: „Mit csinálnak?” sokkal könnyebb - tudják végrehajtani bármely előre kijelölt algoritmus. Így tehát, a maga az algoritmus kezelni a modern matematika mint megvalósítása kiszámításának értékeit rekurzív függvény. Egy ilyen egyértelmű és világos választ arra a kérdésre, hogy „Mit tehet egy Turing-gép?” Ad egy lehetőséget, hogy a koncepció a Turing-gép alapjául meghatározását az algoritmus: az algoritmus minden olyan folyamat, amely elvégezhető a célgép, kiegészítve végtelen memória, hogy algoritmikusan komplett gépek , egy Turing-gép meghajtó nagyböjt et al.
- ↑ Yzerman M. Gusev LA Rozonoer LI Smirnova im Tal AA logikát. Machines. Algoritmusok. Go. ed. Sci. Irodalom, 1963. 556 p.
Kapcsolódó cikkek