New balanced grammars using multiset, valence and tree based controls

Abstract

Grammars with regulated rewriting (regulated or controlled grammars for short) have been an active research area in the field of formal language theory. They have been applied in a great variety of scientific disciplines ranging from linguistics through DNA computing up to the informatics and recently come to big data analytics. However, all of those existed grammars have not yet to be completed since each of them is either complicated, not computationally complete or having too many unsolvable decision problems. Thus, more variants of controlled grammars can be further investigated through different approaches to address these issues. The main aim of this thesis is to introduce a new variant of controlled grammars called Balanced Grammars (BG) using four simple variables such as multiset, valence, weight and tree structure as the control mechanisms. We have established Multiset Controlled Grammars (MCG) which are based on terminal multisets. Another type is a modified version of tree controlled grammars consisting three types of the grammars called Tree Multiset Controlled Grammars (TMCG) that use multiset, Tree Valence Controlled Grammars (TVCG) that apply valence and Tree Regularly Controlled Grammars (TRCG) that implement regular sets. We also establish Balanced Two-steps Controlled Grammars (BTCG) that use weight pairs. The computational power and closure properties of each type of the grammars were studied. Based on the results, it can be proven that MCG are more powerful than Chomsky grammars as multiset controlled regular grammars (mREG) can generate non-regular languages, multiset controlled linear grammars (mLIN) can generate non-linear languages as well as multiset controlled context-free grammars (mCF) which can generate non-context-free grammars. In addition, a simplification of processes for multiset controlled context-free grammars were studied and resulted in a Chomsky normal form. Using this normal form, a membership algorithm based on Cocke-Younger-Kasami (CYK) algorithm which can be used as a parsing was designed. As for TMCG, TVCG, TRCG and BTCG, we demonstrated that all of these grammars which in context-free form can generate non-context-free languages. Besides, we also proved that all introduced grammars have at least as powerful as additive valence grammars, and they are at most powerful as matrix grammars. Then, in term of closure properties, most of them are closed under union, Kleene-star, homomorphism and mirror image.