Publication detail
Final sentential forms
KOŽÁR, T. MEDUNA, A. KŘIVKA, Z.
Original Title
Final sentential forms
Type
conference paper
Language
English
Original Abstract
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.
Keywords
sentential form, Turing power, recursively enumerable language, propagating context-free grammar, palindromial language, queue grammar
Authors
KOŽÁR, T.; MEDUNA, A.; KŘIVKA, Z.
Released
15. 9. 2023
Publisher
School of Computer Science and Engineering, University of New South Wales
Location
Famagusta
ISBN
2075-2180
Periodical
Electronic Proceedings in Theoretical Computer Science, EPTCS
Year of study
388
Number
9
State
unknown
Pages from
38
Pages to
47
Pages count
9
URL
BibTex
@inproceedings{BUT185173,
author="Tomáš {Kožár} and Alexandr {Meduna} and Zbyněk {Křivka}",
title="Final sentential forms",
booktitle="Proceedings 13th International Workshop on Non-Classical Models of Automata and Applications",
year="2023",
journal="Electronic Proceedings in Theoretical Computer Science, EPTCS",
volume="388",
number="9",
pages="38--47",
publisher="School of Computer Science and Engineering, University of New South Wales",
address="Famagusta",
doi="10.4204/EPTCS.388.6",
issn="2075-2180",
url="https://arxiv.org/abs/2309.08719v1"
}Responsibility: Ing. Marek Strakoš