How to Demonstrate Metalinearness and Regularity by Tree-Restricted General Grammars
| Autor: | Havel, Martin, Křivka, Zbyněk, Meduna, Alexander |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Zdroj: | EPTCS 407, 2024, pp. 86-99 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.4204/EPTCS.407.7 |
| Popis: | This paper introduces derivation trees for general grammars. Within these trees, it defines context-dependent pairs of nodes, corresponding to rewriting two neighboring symbols using a non context-free rule. It proves that the language generated by a linear core general grammar with a slow-branching derivation tree is k-linear if there is a constant u such that every sentence w in the generated language is the frontier of a derivation tree in which any pair of neighboring paths contains u or fewer context-dependent pairs of nodes. Next, it proves that the language generated by a general grammar with a regular core is regular if there is a constant u such that every sentence w in the generated language is the frontier of a derivation tree in which any pair of neighboring paths contains u or fewer context-dependent pairs of nodes. The paper explains that this result is a powerful tool for showing that certain languages are k-linear or regular. Comment: In Proceedings NCMA 2024, arXiv:2409.06120 |
| Databáze: | arXiv |
| Externí odkaz: |
|