Detail publikace

Controlled Pure Grammar Systems

MEDUNA Alexander a ZEMEK Petr. Controlled Pure Grammar Systems. Journal of Universal Computer Science, roč. 18, č. 14, 2012, 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
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT)
Zemek Petr, Ing. (UIFS FIT VUT)
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
UT WoS
000310430600007
EID Scopus
2-s2.0-84868281022
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