Detail publikace
Final sentential forms
Křivka Zbyněk, Ing., Ph.D. (UIFS FIT VUT)
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT)
Nechť G je bezkontextová gramatika s totální abecedou V, a nechť F je finální jazyk nad abecedou W, jež je podmnožinou V. Finální větná forma je libovolná větná forma gramatiky G takové, že po vynechání symbolů z podabecedy V-W patří do jazyka F. Takový řetězec vzniklý eliminací všech neterminálů z W a patřící do F je v jazyce gramatiky G finalizovaném pomocí F když a jen když je složen pouze z terminálů.
Jazyk generovaný bezkontextovou gramatikou finalizovaný regulárním jazykem je vždy bezkontextový. Na druhou stranu je dokázáno, že každý rekurzivně spočetný jazyk L lze popsat nevymazávající bezkontextovou gramatikou G takovou, že L je jazyk gramatiky G finalizovaný pomocí jazyka {w#rev(w):řetězec w nad abecedou {0,1}}, kde rev(w) je reverzace řetězce w.
@INPROCEEDINGS{FITPUB13008,
author = "Tom\'{a}\v{s} Ko\v{z}\'{a}r and Zbyn\v{e}k K\v{r}ivka and Alexander Meduna",
title = "Final sentential forms",
pages = "38--47",
booktitle = "Proceedings 13th International Workshop on Non-Classical Models of Automata and Applications",
journal = "Electronic Proceedings in Theoretical Computer Science",
volume = 388,
number = 9,
year = 2023,
location = "Famagusta, TR",
publisher = "School of Computer Science and Engineering, University of New South Wales",
ISSN = "2075-2180",
doi = "10.4204/EPTCS.388.6",
language = "english",
url = "https://www.fit.vut.cz/research/publication/13008"
}