Detail publikace

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

ZEMEK, P. k-Limited Erasing Performed by Regular-Controlled Context-Free Grammars. Proceedings of the 16th Conference and Competition STUDENT EEICT 2010. Volume 3. Brno: Faculty of Information Technology BUT, 2010. p. 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
anglicky
Autoři
Zemek Petr, Ing., Ph.D.
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, FEKT VUT v Brně, CZ
ISBN
978-80-214-4078-4
Vydavatel
Faculty of Information Technology BUT
Místo
Brno
BibTeX 
@inproceedings{BUT91250,
  author="Petr {Zemek}",
  title="k-Limited Erasing Performed by Regular-Controlled Context-Free Grammars",
  booktitle="Proceedings of the 16th Conference and Competition STUDENT EEICT 2010",
  year="2010",
  series="Volume 3",
  pages="42--44",
  publisher="Faculty of Information Technology BUT",
  address="Brno",
  isbn="978-80-214-4078-4",
  url="http://www.feec.vutbr.cz/EEICT/2010/sbornik/02-Magisterske_projekty/07-Informacni_systemy/11-xzemek02.pdf"
}
Nahoru