Automaattinen lehtimuistilla
Automaattiteoriassa pudotusautomaatti on äärellisen tilan kone , joka käyttää pinoa tilojen tallentamiseen.
Muodollinen määritelmä
Toisin kuin tavalliset äärelliset automaatit, työntöautomaatti on joukko [1]
missä
K on äärellinen joukko automaatin tiloja, on automaatin ainoa sallittu alkutila, — joukko lopputiloja, ja F=Ø ja F=K ovat sallittuja, Σ on kelvollinen syöteaakkosto, josta muodostetaan merkkijonoja, jotka automaatti lukee, S - muistin aakkoset (myymälä), on tyhjä muistimerkki.
Muisti toimii kuin pino , eli viimeinen siihen kirjoitettu elementti on luettavissa. Siirtymäfunktio on siis kartoitus . Toisin sanoen nykyisen tilan, syöttösymbolin ja myymälän yläosassa olevan symbolin yhdistelmän perusteella automaatti valitsee seuraavan tilan ja mahdollisesti symbolin, joka kirjoitetaan kauppaan. Siinä tapauksessa, että on automaatiosäännön oikeassa osassa, kauppaan ei lisätä mitään ja ylhäältä oleva elementti poistetaan. Jos myymälä on tyhjä, vasemmalla puolella olevat säännöt c aktivoituvat.
Push-down-automaattien tunnistama kieliluokka on sama kuin yhteydettömien kielten luokka .
Puhtaassa muodossaan push-pull-automaatteja käytetään harvoin. Tyypillisesti tätä mallia käytetään visualisoimaan ero tavallisten äärellisten automaattien ja syntaktisten kielioppien välillä . Pushdown-automaattien toteutus eroaa äärellisistä automaateista siinä, että automaatin nykyinen tila riippuu voimakkaasti mistä tahansa aikaisemmasta.
Esimerkki työntöautomaatin käytöstä
toista X : = huippukaupan symboli ; jos X = pääte tai $ niin jos X = InSym poista X kaupasta ; _ _ InSym := seuraava symboli ; else error () end else /* X = ei -pääte */ jos M [ X , InSym ] = X - > Y1Y2 ... Yk niin poista X varastosta ; laita Yk , Yk - 1 , ... , Y1 varastoon ( Y1 päälle ) ; _ tulossääntö X - > Y1Y2 ... Yk else error () /* taulukkomerkintä M on tyhjä */ lopeta kunnes X = $ / * varasto on tyhjä */Push-pull-automaattien tyypit
On olemassa deterministisiä ja ei -deterministisiä pushdown- automaatteja.
Ei-deterministisille automaateille (toisin kuin deterministisille) on kaksi vastaavaa lopetusehtoa:
- tyhjä kauppa,
- saavuttaa lopputilan.
Deterministinen automaatti päättyy vasta kun se saavuttaa lopullisen tilan.
Katso myös
- JFLAP on monialustainen automaattisimulaattori, Turingin kone, kielioppi, piirtää automaattikuvaajan.
Muistiinpanot
- ↑ Discrete Mathematics, 2006 , s. 630.
Kirjallisuus
- John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Johdatus automaatioteoriaan, kieliin ja laskemiseen. - M .: "Williams" , 2002. - S. 528. - ISBN 0-201-44124-1 .
- Belousov A. I., Tkachev S. B. Diskreetti matematiikka. — M .: MGTU , 2006. — 743 s. — ISBN 5-7038-2886-4 .
| Muodolliset kielet ja viralliset kieliopit | |
|---|---|
| Yleiset käsitteet | |
| Tyyppi 0 | |
| Tyyppi 1 |
|
| Tyyppi 2 | |
| Tyyppi 3 |
|
| jäsentäminen | |