Detail publikace
k-Limited Erasing Performed by Scattered Context Grammars
TECHET Jiří. k-Limited Erasing Performed by Scattered Context Grammars. In: Proceedings of the 13th Conference STUDENT EEICT 2007, Volume 4. Brno: Fakulta elektrotechniky a komunikačních technologií VUT v Brně, 2007, s. 419-423. ISBN 978-80214-3410-3.
Název česky
k-limitované vymazávání prováděné gramatikami s rozptýleným kontextem
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
Techet Jiří, Ing., Ph.D. (UIFS FIT VUT)
Klíčová slova
gramatiky s rozptýleným kontextem, vymazávání nonterminálů
Abstrakt
Gramatika s rozptýleným kontextem G vymazává nonterminály k-limitovaným způsobem, kde k je kladné celé číslo, jestliže pro každou větu náležející do jazyka G existuje taková derivace, že v každé větné formě je mezi každými dvěma symboly, ze kterých G derivuje neprázdné řetězce, řetězec obsahující maximálně k nonterminálů, ze kterých se generují prázdné řetězce. V této práci je dokázáno, že libovolná gramatika s rozptýleným kontextem, která vymazává nonterminály k-limitovaným způsobem může být převedena na ekvivalentní gramatiku s rozptýleným kontextem bez vymazávacích pravidel, což v obecném případě není možné.
Rok
2007
Strany
419-423
Sborník
Proceedings of the 13th Conference STUDENT EEICT 2007, Volume 4
Konference
Student EEICT 2007, Brno, CZ
ISBN
978-80214-3410-3
Vydavatel
Fakulta elektrotechniky a komunikačních technologií VUT v Brně
Místo
Brno, CZ
BibTeX
@INPROCEEDINGS{FITPUB8320, author = "Ji\v{r}\'{i} Techet", title = "k-Limited Erasing Performed by Scattered Context Grammars", pages = "419--423", booktitle = "Proceedings of the 13th Conference STUDENT EEICT 2007, Volume 4", year = 2007, location = "Brno, CZ", publisher = "Faculty of Electrical Engineering and Communication BUT", ISBN = "978-80214-3410-3", language = "english", url = "https://www.fit.vut.cz/research/publication/8320" }