Detail publikace

A Two-Way PC Grammar Systems Based on Regular Grammars

KALÁB Petr. A Two-Way PC Grammar Systems Based on Regular Grammars. In: Proceedings of 10th Conference and Competition STUDENT EEICT 2004. Volume 2. Brno: Fakulta informačních technologií VUT v Brně, 2004, s. 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
angličtina
Autoři
Kaláb Petr, Ing. (UIFS FIT VUT)
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
Konference
Student EEICT 2004, Brno, CZ
ISBN
80-214-2635-7
Vydavatel
Fakulta informačních technologií VUT v Brně
Místo
Brno, CZ
BibTeX 
@INPROCEEDINGS{FITPUB7445,
   author = "Petr Kal\'{a}b",
   title = "A Two-Way PC Grammar Systems Based on Regular Grammars",
   pages = "252--256",
   booktitle = "Proceedings of 10th Conference and Competition STUDENT EEICT 2004",
   series = "Volume 2",
   year = 2004,
   location = "Brno, CZ",
   publisher = "Faculty of Information Technology BUT",
   ISBN = "80-214-2635-7",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/7445"
}
Nahoru