Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
context-free grammars; tree-controlled grammars; restricted derivation trees; paths; cuts; language families
context-free grammars; tree-controlled grammars; restricted derivation trees; paths; cuts; language families
Summary:
First, this paper discusses tree-controlled grammars with root-to-leaf derivation-tree paths restricted by control languages. It demonstrates that if the control languages are regular, these grammars generate the family of context-free languages. Then, in a similar way, the paper introduces tree-controlled grammars with derivation-tree cuts restricted by control languages. It proves that if the cuts are restricted by regular languages, these grammars generate the family of recursively enumerable languages. In addition, it places a binary-relation-based restriction upon these grammars and demonstrate that this additional restriction does not affect the generative power of these grammars.
References:
[1] A. V. Aho, J. D. Ullman: The theory of parsing, translation, and compiling. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1972. MR 0408321
[2] A. Bondy: Graph Theory. Springer, 2010.
[3] K. Čulik, H. A. Maurer: Tree controlled grammars. Computing 19 (1977), 129-139. DOI 10.1007/BF02252350 | MR 0464718 | Zbl 0363.68108
[4] J. Dassow, Gh. Păun: Regulated Rewriting in Formal Language Theory. Springer, Berlin 1989. MR 1067543
[5] J. Dassow, B. Truthe: Subregularly tree controlled grammars and languages. In: Automata and Formal Languages - 12th Int. Conference AFL 2008, Proceedings (E. Csuhaj-Varjú, Z. Ésik, eds.), Balatonfüred, Hungary 2008, pp. 158-169.
[6] S. Marcus, C. Martín-Vide, V. Mitrana, Gh. Păun: A new-old class of linguistically motivated regulated grammars. In: Computational Linguistics in the Netherlands 2000, Selected Papers from the Eleventh clin Meeting (W. Daelemans, K. Sima'an, J. Veenstra, J. Zavrel, eds.), Rodopi, Amsterdam 2001, pp. 111-125. MR 1869435
[7] C. Martín-Vide, V. Mitrana: Further properties of path-controlled grammars. In: Proceedings of FG-MoL 2005, The 10th Conference on Formal Grammar and The 9th Meeting on Mathematics of Language, Edinburgh 2005, pp. 221-232. MR 2153679
[8] A. Meduna: Automata and Languages: Theory and Applications. Springer Verlag, 2005. MR 1778364
[9] Gh. Păun: On the generative capacity of tree controlled grammars. Computing 21 (1979), 3, 213–220. DOI 10.1007/BF02253054 | MR 0620209 | Zbl 0392.68060
Search
Partner of
