Detail publikace

k-Limited Erasing Performed by Regular-Controlled Context-Free Grammars

ZEMEK Petr. k-Limited Erasing Performed by Regular-Controlled Context-Free Grammars. In: Proceedings of the 16th Conference and Competition STUDENT EEICT 2010. Volume 3. Brno: Fakulta informačních technologií VUT v Brně, 2010, s. 42-44. ISBN 978-80-214-4078-4.
Název česky
k-limitované vymazávání prováděné bezkontextovými gramatikami řízenými regulárním jazykem
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
Zemek Petr, Ing. (UIFS FIT VUT)
URL
Klíčová slova

bezkontextová gramatika řízená regulárním jazykem, odstraňování vymazávacích pravidel

Abstrakt

Bezkontextová gramatika řízená regulárním jazykem vymazává své nonterminály k-limitovaným způsobem, kde k >= 0, jestliže v každé větné formě x v libovolné úspěšné derivaci je nejvýše k|x|/(k+1) nonterminálů, ze kterých je derivován prázdný řetězec, kde |x| označuje délku x. Tento článek demonstruje, že lze každou bezkontextovou gramatiku řízenou regulárním jazykem, která vymazává své nonterminály tímto způsobem, transformovat na ekvivalentní bezkontextovou gramatiku řízenou regulárním jazykem bez vymazávacích pravidel, přičemž není známo, zda lze tento převod provést v libovolném případě.

Rok
2010
Strany
42-44
Sborník
Proceedings of the 16th Conference and Competition STUDENT EEICT 2010
Řada
Volume 3
Konference
Student EEICT 2010, Brno, CZ
ISBN
978-80-214-4078-4
Vydavatel
Fakulta informačních technologií VUT v Brně
Místo
Brno, CZ
BibTeX 
@INPROCEEDINGS{FITPUB9259,
   author = "Petr Zemek",
   title = "k-Limited Erasing Performed by Regular-Controlled Context-Free Grammars",
   pages = "42--44",
   booktitle = "Proceedings of the 16th Conference and Competition STUDENT EEICT 2010",
   series = "Volume 3",
   year = 2010,
   location = "Brno, CZ",
   publisher = "Faculty of Information Technology BUT",
   ISBN = "978-80-214-4078-4",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9259"
}
Nahoru