Detail publikace

Finitely Expandable Deep PDAs

MEDUNA Alexander. Finitely Expandable Deep PDAs. Automata, Formal Languages and Algebraic Systems. Hong Kong: Hong Kong University of Scinece and Technology, 2010, s. 113-123. ISBN 981-4317-60-8.
Název česky
Hluboké zásobníkové automaty s konečnými expanzemi
Typ
kapitola v knize
Jazyk
angličtina
Autoři
Klíčová slova

hluboké zásobníkové automaty

Abstrakt

Tato kapitolase zabývá zásobníkovými automaty doplněnými řízením, které předepisuje aplikovatelnost pravidel při generování jazyků. Takto obohacené bezkontextové gramatiky jsou souhrnně označovány jako řízené gramatiky. Mezi diskutované případy patří gramatiky řízené regulárním jazykem, maticové gramatiky, programované gramatiky, gramatiky s nahodilým kontextem, gramatiky s rozptýleným kontextem a stavové gramatiky. Ústředním tématem práce jsou transformace těchto gramatik jak na gramatiky stejného typu splňující různá dodatečná omezení, tak na jiné ekvivalentní formální modely. Mezi prezentované transformace patří například převod gramatik do normálních forem, odstraňování zkracujících pravidel, redukce počtu jejich komponent či generování jazyků rozšířených o dodatečné informace. Důraz je kladen na algoritmická provedení těchto transformací, která jsou v praxi snadno implementovatelná. Definice a výsledky jsou doplněny názornými příklady. Kromě řízených gramatik jsou diskutovány i další příbuzné řízené formální modely, jako multigenerativní gramatické systémy či řízené zásobníkové automaty. V závěru jsou nastíněna praktická využití dosažených výsledků, možnosti budoucího výzkumu z hlediska moderních trendů a historické poznámky k literatuře, z níž kniha vychází.

Rok
2010
Strany
113-123
Kniha
Automata, Formal Languages and Algebraic Systems
ISBN
981-4317-60-8
Vydavatel
Hong Kong University of Scinece and Technology
Místo
Hong Kong, CN
BibTeX
@INBOOK{FITPUB9522,
   author = "Alexander Meduna",
   title = "Finitely Expandable Deep PDAs",
   pages = "113--123",
   booktitle = "Automata, Formal Languages and Algebraic Systems",
   year = 2010,
   location = "Hong Kong, CN",
   publisher = "Hong Kong University of Scinece and Technology",
   ISBN = "981-4317-60-8",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9522"
}
Nahoru