Publication Details

Final sentential forms

KOŽÁR, T.; MEDUNA, A.; KŘIVKA, Z. Final sentential forms. In Proceedings 13th International Workshop on Non-Classical Models of Automata and Applications. Electronic Proceedings in Theoretical Computer Science, EPTCS. Famagusta: School of Computer Science and Engineering, University of New South Wales, 2023. p. 38-47. ISSN: 2075-2180.
Czech title
Finální větné formy
Type
conference paper
Language
English
Authors
URL
Keywords

sentential form, Turing power, recursively enumerable language, propagating
context-free grammar, palindromial language, queue grammar

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.

Published
2023
Pages
38–47
Journal
Electronic Proceedings in Theoretical Computer Science, EPTCS, vol. 388, no. 9, ISSN 2075-2180
Proceedings
Proceedings 13th International Workshop on Non-Classical Models of Automata and Applications
Conference
13th International Workshop on Non-Classical Models of Automata and Applications, Famagusta, Cyprus, CY
Publisher
School of Computer Science and Engineering, University of New South Wales
Place
Famagusta
DOI
EID Scopus
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"
}
Files
Back to top