Článek ve sborníku konference| ZEMEK Petr. k-Limited Erasing Performed by Regular-Controlled Context-Free Grammars. In: Proceedings of the 16th Conference and Competition STUDENT EEICT 2010. Brno: Fakulta informačních technologií VUT v Brně, 2010, s. 42-44. ISBN 978-80-214-4078-4. | | Jazyk publikace: | angličtina |
|---|
| Název publikace: | k-Limited Erasing Performed by Regular-Controlled Context-Free Grammars |
|---|
| Název (cs): | k-limitované vymazávání prováděné bezkontextovými gramatikami řízenými regulárním jazykem |
|---|
| Strany: | 42-44 |
|---|
| Sborník: | Proceedings of the 16th Conference and Competition STUDENT EEICT 2010 |
|---|
| Konference: | Student EEICT 2010 |
|---|
| Řada knih: | Volume 3 |
|---|
| Místo vydání: | Brno, CZ |
|---|
| Rok: | 2010 |
|---|
| ISBN: | 978-80-214-4078-4 |
|---|
| Vydavatel: | Fakulta informačních technologií VUT v Brně |
|---|
| URL: | http://www.feec.vutbr.cz/EEICT/2010/sbornik/02-Magisterske_projekty/07-Informacni_systemy/11-xzemek02.pdf [PDF] |
|---|
| Klíčová slova |
|---|
| bezkontextová gramatika řízená regulárním jazykem, odstraňování vymazávacích pravidel |
| Anotace |
|---|
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ě.
|
| BibTeX: |
|---|
@INPROCEEDINGS{
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 = {http://www.fit.vutbr.cz/research/view_pub.php.cs?id=9259}
} |
|
Fakulta informačních technologií