Tree valence controlled grammars
Beyond a shadow of a doubt, the studying of context-free grammars with restricted derivation trees known as tree controlled grammars have achieved plentiful remarkable results within formal language theory as demonstrated in a number of publications on this subject for the past forty five years. In...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IIUM Press, International Islamic University Malaysia
2017
|
| Subjects: | |
| Online Access: | http://irep.iium.edu.my/58701/ http://irep.iium.edu.my/58701/ http://irep.iium.edu.my/58701/1/58701_Tree%20Valence%20Controlled%20Grammars.pdf |
| Summary: | Beyond a shadow of a doubt, the studying of context-free grammars with restricted derivation trees known as tree controlled grammars have achieved plentiful remarkable results within formal language theory as demonstrated in a number of publications on this subject for the past forty five years. In principle, these grammars generate their languages as an ordinary context-free grammar except their derivation trees need to be satisfied by certain prescribed conditions. Our paper is a continuing of studying of this kind of grammars, where we introduce a new variant of tree controlled grammar called a tree valence controlled grammar, which replaces regular sets with valences where every main production with certain integer value will be derived into sub-productions with the value of combination of zero and one or zero and minus represented in matrices form with the permutations of each matrix row yield a zero value (at every level of tree derivation, the summation of valence value is zero). We also investigate the generative capacity and structural properties of these grammars. |
|---|