Determinisztikus véges automaták
A determinisztikus véges automata - egy sor öt elem, ahol a Sigma - ábécé, Q - több Államok, s - a kezdeti (start) állapotban, T - halmaza elfogadó államok, delta, ppm: - átmenet funkciót.
A determinisztikus véges állapotú gép egy speciális esete egy nem-determinisztikus véges állapotú gép, ahol
• Nincsenek államok e-átmenetek
• Minden állam s és bemeneti jel, és nincs több, mint egy ív áradó s jelölt is.
A determinisztikus véges állapotú gép van egy bemenete az egyes szimbólumok jelentése legfeljebb egy átmeneti ki minden állapotban. Ha DFA, hogy képviselje az átmenet funkciót táblázatot használjuk, akkor minden bejegyzés ez az egyetlen feltétel. Ezért könnyen ellenőrizhető, hogy a DFA megenged bizonyos húr, mert nincs egy útvonal kiindulási állapot a megjelölt sorban. Az alábbi algoritmus utánozza DFA feldolgozása során a bemeneti karakterlánc.
Q állapotgép M és Q „M” egyenértékűnek tekintjük, ha mind a gép fogadó ugyanazt a (sem) a bemeneti szimbólumok sorozatát, folyamat ugyanabban a kimeneti sorrendben.
Gép M és M „nevezzük ekvivalens, ha minden egyes állam a automata M van egy egyenértékű állapotban az M” és fordítva.
Más szóval, az egyenértékű gépek végrehajtott azonos átalakítás, de lehet, hogy különböző számú belső állapotok.
Az ekvivalencia fogalma az államok vonatkozhatnak egyetlen gép (hivatalosan, akkor feltételezhetjük, hogy M és M „azonos). különböző állapotokat lesz egyenértékű egyetlen gépen, amelyen keresztül egy és ugyanazon bemeneti szimbólum sorozatot átalakítjuk azonos kimeneti.
Pushdown automaták. Által elfogadott nyelvek pushdown automata. Építő pushdown automaták. átviteli függvény. Módszerek a feladata az automata átmenet funkciót pushdown.
CFG lánc határozza meg a szerkezet, és lehetővé teszi, hogy építsenek egy lánc egy adott nyelvet. Shop berendezésekhez hasonlóan véges automaták korábban tárgyaltuk, lehetővé teszi számunkra, hogy megoldja a környezetfüggetlen nyelvek elismerése probléma, ami az, hogy egy adott lánc van szükség annak megállapítására, hogy tartozik egy adott nyelvet.
A munkával kapcsolatos formális nyelvek és nyelvtanok pushdown automata modellt használnak. amely a bemeneti öv vezérlőberendezés és egy kiegészítő szalaggal, úgynevezett egy magazin vagy verem.
Bemeneti szalagot osztva sejtek (pozíció). amelyek mindegyike lehet
írásbeli karakter input ábécé. Feltételezzük, hogy a bemeneti sejtek a fel nem használt szalag elhelyezve üres jelek e.
A kiegészítő szalagot is osztva sejtek, amelyek lehet elhelyezni verem-ábécé karaktereit. Kezdve kiegészítő szalag nevű műhelyben. Kommunikációs egység szalagok két fej. amely mentén mozoghat a szalagot.
A fej a bemeneti szalag mozoghat csak egy irányban - a balra vagy
marad a helyén. Ez végre csak olvasható. Kiegészítő magnófej képes végrehajtani mind az olvasás és írás, de ezeket a műveleteket társított mozgó fej egy bizonyos módon:
- a felvétel fej pre-egy pozícióval eltolódik, majd a szimbólum kerül rögzítésre a szalagon,
- olvasása közben egy szimbólum található a fej alatt olvasható a szalagot, majd a fejet egy hellyel lejjebb tolja, t.o.golovka mindig szemben a legutóbbi rögzített karaktert. Pozíció található, a megfelelő időpontban, a fej, a nazyvayutvershinoy tárolni.
ahol
P - bemeneti ábécé,
S - ábécé államok
SO - az eredeti állapot,
SO O S,
F - készlet végső állapot, F részhalmaza S,
H - alfavitmagazinnyh karaktereket. felvett egy támasztó szalagot
ho - az alján a marker, mindig rögzítve a műhelyben, ho O H,
f - átmenet funkció
f.
> X S x H ® S x H *.
Ha M-gép - determinisztikus és
f:
> X S x H ® M (S x H *).
Ha M-automata - nem determinisztikus.
Az f függvény térképek tripletek (pi. Sj. Hk) a párban (sr. U). ahol u a H * és hk - szimbólum a verem tetején, determinisztikus automatát vagy több pár a nem-determinisztikus gép.
Ez a függvény írja le a változást az állami pushdown automata, amely akkor következik be, amikor a karaktert olvasni a bemeneti szalag és premeschenie bemeneti fejét.
Később, ha építési pushdown automata szükség kétféle funkciót átmenetek, amelyek megváltoztatják az állam a gép mozgatása nélkül a bemeneti fej 1) átmeneti függvény egy null karakter, mint a bemeneti karakter:
hogy nem számít, milyen a karakter alatt chitayushey Glowka bemeneti szalag megköveteli, hogy olvassa el a h jel a verem tetején, hogy változtatni az állam az automata, hogy s és a hangfelvétel tsepochkub a boltban.
2) az átmeneti függvény egy adott bemeneti szimbólum:
amely megköveteli a halmazállapot-változás, és a lánc lemezboltban a feltétellel, hogy a szimbólum egy olvasási input fej és a tetején a tároló a h jel.
Dopustimoydlya úgynevezett lánc M, ha van egy sorozata konfigurációk, ahol az első konfiguráció egy primer-lánc C-a. és az utolsó - az utolsó. (Így egy, ho.) | - * (s1 $ $ ..). ahol S1 F.
A készlet húrok engedélyezett automata M nevezzük nyelv vagy meghatározható automatikusan engedélyezett M és L jelöli (M).
EsliG =
A bizonyítás alapja egy eljárást pushdown automatát egy adott COP-grammatike.Chtoby hogy a folyamatot a gép egyszerűbb és egyértelműbb, vállalja, hogy a vásárlás automata egy állami s0. Nos, nézzük ott kell adni a nyelvtan G =
mint az eredeti gép állapotát veszi s0 és a kivitelezést kereszteződések függvény az alábbiak szerint:
1. Minden Egy Mintegy VA. azok, amelyek megtalálhatók a bal oldalon a szabályok
® a. építeni egy csapatot típusa:
2. Minden olyan konstrukció formájában csapatok OVT
3. Az átmenet a végső állapot, hogy építsenek egy csapatot
4. A kezdeti konfiguráció a gép úgy definiáljuk, mint:
ahol w - adott lánc, rögzítésre kerül a bemeneti adatfolyam.
A gép szerint konstruált a fenti szabályok, a következőképpen működik. Ha a tároló felső terminál és egy szimbólum olvasni a bemeneti szalag egybeesik vele, a terminál eltávolítjuk a boltban, és a bemeneti fej mozog parancs típusát (2). Ha a tároló tetején a nem terminális, akkor a parancs típusa (1), amely ahelyett, hogy a terminál ír a üzletlánc, amely a jobb oldali részén a nyelvtani szabályok. Következésképpen, az automatikus, szekvenciálisan helyettesítve nemterminális megjelenő verem tetején épít a boltban bal oldali kimenet a bemeneti karakterlánc, eltávolításával kapott terminális szimbólumok, amelyek egybeesnek karaktereket a bemeneti karakterlánc. Ez azt jelenti, hogy mindkét lánc, amely beszerezhető a bal kimenet nyelvtani G, lehet beépített gép M.
Konfiguráció automata M jelentése egy hármas (s, a. G) Az S x P * x H *.
Feltételezzük, hogy a gép beolvassa a szimbólum a. alatt található a fej, és a h jel.
található a tetején a verem meghatározza egy új állami s', és b üzletláncok
tárolni helyett h szimbólum. Ha b = $. A felső szimbólum eltávolítjuk a boltban.
Ez a változás a konfiguráció lehetséges, ha az f (s, a, h) meghatározott és a tulajdonában
érték (ek, b). Ismertetett műveletsort végezzük mozog a fej. Leírni a gép működését, szükségünk van egy másfajta stroke, vagyis változás áll be az állam és az áruház bejárata mozgatása nélkül a fej. Ha f 0 (S, E, H) van definiálva, és ez tartja az értékét (s', b). ez határozza meg a változás konfiguráció az alábbiak szerint:
Így előfordulhat, hogy három esetben a gépet:
- f (s, a, h) meghatározott és végre munkaciklus,
- f (s, a, h) nem határoztuk meg, de a meghatározott funkció F 0 (S, E, H) végezzük, és egy üres órát.
- A függvények f (s, a, h) és az f 0 (S, E, H) vannak megadva, ebben az esetben a készülék már nem működik.
Általában az intézkedések által feltett átmeneti függvény és automatikusan elvégezni, az alábbi jelölést:
f (s, <входной символ>, <магазинный символ>) = (S1. <заносимая цепочка>)
Meg kell jegyezni, hogy amikor a szélütés először olvassa el a karaktert a tetején, majd a helyére lépett új karakter vagy karakterlánc. Az egyes értékek az átmeneti függvény gyakran nevezik csapatok pushdown gép.
Kezdeti konfiguráció az úgynevezett Configuration (SO. A. Ho). ahol így a kezdeti állapotban és ho - alsó marker tárolja, és a végső - konfiguráció (s, $ $.). ahol s tartozik a készlet végső állapot F.
Szekvenciák azonosítására az egymást követő konfigurációk egyetértenek
a | - *. Így a szekvencia
Meg van írva a rövidített formában az alábbiak szerint: