Detail publikace

Controlled Pure Grammar Systems

MEDUNA Alexander a ZEMEK Petr. Controlled Pure Grammar Systems. Journal of Universal Computer Science, roč. 18, č. 14, s. 2024-2040. ISSN 0948-6968. Dostupné z: http://www.jucs.org/jucs_18_14/controlled_pure_grammar_systems
Název česky
Řízené čisté gramatické systémy
Typ
článek v časopise
Jazyk
angličtina
Autoři
URL
Klíčová slova
formální jazyky, čisté gramatické systémy, řízené derivace
Abstrakt
Tento článek diskutuje gramatické systémy mající pouze terminály, pracující nejlevějším způsobem a generující jejich jazyky za pomocí řízení kontrolními jazyky nad pravidly. Článek dokazuje tři výsledky týkající se jejich generativní síly. Za prvé, bez řídících jazyků, tyto systémy nejsou schopny vygenerovat ani všechny bezkontextové jazyky. Za druhé, pokud jsou řízeny regulárními jazyky, pak tyto systémy mající dvě komponenty definují třídu rekurzivně spočetných jazyků. Za třetí, s řídícími jazyky, které jsou generované regulárně řízenými bezkontextovými gramatika, tyto systémy nad jednoprvkovou abecedou generují pouze regulární jazyky. V úvodní sekci tento článek dává motivaci pro zavedení těchto systémů a v závěru formuluje několik otevřených problémů.
Rok
2012
Strany
2024-2040
Časopis
Journal of Universal Computer Science, roč. 18, č. 14, ISSN 0948-6968
Vydavatel
Springer Verlag
BibTeX
@ARTICLE{FITPUB9857,
   author = "Alexander Meduna and Petr Zemek",
   title = "Controlled Pure Grammar Systems",
   pages = "2024--2040",
   journal = "Journal of Universal Computer Science",
   volume = 18,
   number = 14,
   year = 2012,
   ISSN = "0948-6968",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9857"
}
Nahoru