Detail publikace

A Two-Way PC Grammar Systems Based on Regular Grammars

KALÁB, P. A Two-Way PC Grammar Systems Based on Regular Grammars. Proceedings of 10th Conference and Competition STUDENT EEICT 2004. Volume 2. Brno: Faculty of Information Technology BUT, 2004. p. 252-256. ISBN: 80-214-2635-7.
Název česky
Dvousměrné PC gramatické systémy založené na regulárních gramatikách
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Kaláb Petr, Ing.
Klíčová slova

Bezkontextová gramatika, levě-rozšířená frontová gramatika, pravě-lineární gramatika, gramatické systémy, komunikační krok, dvousměrné PC gramatické systémy, derivace, pravidlo, větná forma, nonterminál, terminál

Abstrakt

Kromě derivačních a komunikačních kroků může dvousměrný PC gramatický systém vykonávat kroky redukční během nichž nahradí pravou stranu bezkontextového pravidla stranou levou. Článek dokazuje, že každý neunární rekurzivně spočetný jazyk je definován úsporným způsobem pomocí centralizovaného dvousměrného PC gramatického systému, Γ, který má tři komponenty. Hlavní komponenta obsahuje pouze tři nonterminály a jediné praviddlo obsahující komunikační symbol; dále všechny generované větné formy neobsahují více než dva výskyty nonterminálních symbolů. Během každého výpočtu provede Γ jediný komunikační krok. Na závěr článku jsou diskutovány některé varianty těchto systémů.

Rok
2004
Strany
252–256
Sborník
Proceedings of 10th Conference and Competition STUDENT EEICT 2004
Řada
Volume 2
ISBN
80-214-2635-7
Vydavatel
Faculty of Information Technology BUT
Místo
Brno
BibTeX 
@inproceedings{BUT16935,
  author="Petr {Kaláb}",
  title="A Two-Way PC Grammar Systems Based on Regular Grammars",
  booktitle="Proceedings of 10th Conference and Competition STUDENT EEICT 2004",
  year="2004",
  series="Volume 2",
  pages="252--256",
  publisher="Faculty of Information Technology BUT",
  address="Brno",
  isbn="80-214-2635-7"
}
Nahoru