Final Sentential Forms
| Autor: | Kožár, Tomáš, Křivka, Zbyněk, Meduna, Alexander |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Zdroj: | EPTCS 388, 2023, pp. 38-47 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.4204/EPTCS.388.6 |
| Popis: | Let G be a context-free grammar with a total alphabet V, and let F be a final language over an alphabet W such that W is 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#w^R | w is a string over a binary alphabet}, where w^R is the reversal of w. Comment: In Proceedings NCMA 2023, arXiv:2309.07333 |
| Databáze: | arXiv |
| Externí odkaz: |
|