Publication Details
Final sentential forms
Křivka Zbyněk, Ing., Ph.D. (DIFS FIT BUT)
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
sentential form, Turing power, recursively enumerable language, propagating context-free grammar, palindromial language, queue grammar
Let G be a context-free grammar with a total alphabet V, and let F be a final language over an alphabet W as a subset of V. A final sentential form is any sentential form of G that, after omitting symbols from V-W, it belongs to F. The string resulting from the elimination of all nonterminals from W in a final sentential form is in the language of G finalized by F if and only if it contains only terminals.
The language of any context-free grammar finalized by a regular language is context-free. On the other hand, it is demonstrated that L is a recursively enumerable language if and only if there exists a propagating context-free grammar G such that L equals the language of G finalized by {w#rev(w):string w over alphabet {0,1}}, where rev(w) is the reversal of 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"
}