On Variant of Regulated Grammar and Regulated Automaton

Abstract

Context-free grammar plays a vital role in the field of Automata Theory, but context-free grammars are not able to cover all linguistic phenomena. However, there are languages which cannot be represented by context-free grammars. Further, they have classified into context-sensitive and recursively enumerable languages. These languages suffer from a number of problems such as the emptiness problem is undecidable, and only exponential algorithms are known for the membership problem. To overcome the situation, the concept of regulated grammar and automata has been proposed. Regulated Grammar is the class of grammar which on the one hand only uses context-free production rules and on the same hand have a larger generative capacity by some additional mechanisms. Regulated automaton is the formal automaton counterpart of regulated grammars. This dissertation is devoted to designing and development of a variant of regulated grammar or regulated automata and to apply their concept in RNA and DNA biomolecular structures. Motivated by the similarities between fuzzy finite automata and fuzzy pushdown automata, in this thesis we proposed a novel concept of fuzzy state grammars and fuzzy deep pushdown automata. This concept represents a natural extension of contemporary state grammar and deep pushdown automaton, making them more robust in terms of imprecision, errors, and uncertainty. It has been proved that we can construct fuzzy deep pushdown automata M fd from fuzzy state grammars Gfs and vice-versa, and if the fuzzy deep pushdown automaton M fd is constructed from the fuzzy state grammar Gfs using the above construction method, then ( ) ( ) L M L G fd fs and#61501; . Most of the regulated automata and the regulated transducer which exist in literature such as deep pushdown automata, parallel deep pushdown automata, deep pushdown transducer and parallel deep pushdown transducer are deterministic with respect to depth but lacks in strict determinism.