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  . 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. This thesis also proposes the deterministic models of deep pushdown automata, deep pushdown transducer and their parallel versions named as parallel deep pushdown automata, and parallel deep pushdown transducer. The proposed deterministic models are strictly deterministic and deterministic with respect to depth. Furthermore, based on the deterministic version of these proposed automata and transducer, an infinite hierarchy of languages is explored. Further comparison between proposed deterministic models and existing non-deterministic models has been also done.

In the various existing approaches in the literature, Deoxyribonucleic Acid (DNA) and Ribonucleic Acid (RNA) structure sequences are represented using context-sensitive grammar or mildly context-sensitive grammar with higher time complexities. In this thesis, we have also represented DNA and RNA structure sequences using state grammar and deep pushdown automata. We have represented three commonly found structures in DNA and RNA using state grammar namely: Tandem Repeat, Inverted Repeat, and Pseudoknot. These biological sequences are depicted using formal model deep pushdown automata. Furthermore, we have designed top-down extended LL (1) parser for state grammar. Further, we have extended our work for various biomolecular structures of DNA and RNA using state grammar. Various structures represented are attenuator, extended pseudoknot, kissing hairpin, simple h-type, recursive pseudoknot, and threeknot. Motivated by the prior work of recognition of imperfect strings in context-free grammar and context-sensitive grammar, this thesis also proposes an algorithm for error tolerance in recognition of faulty strings in a regulated grammar using fuzzy sets. The time complexity of the proposed algorithm is 2 3 O G w (| |.| | ), where | | G represents the number of production rules and | | w is the length of the input string w. We applied the algorithm to regularly controlled and matrix grammar