Simplification process of static Watson-Crick context-free grammars.

In formal language theory, a grammar is a set of production rules that describes the possible strings in a given language. Context-free grammars, the most applicable type of the grammars, may contain production rules that do not generate any string of the language or affect the string generation processes using several unnecessary steps. Thus, the elimination of such undesirable productions is important for the optimization of the string generation processes. The "cleaning" of context-free grammars is done through the simplification process consisting of a useful substitution rule, removal of useless productions, removal of λ − productions, and removal of unit-productions. This paper presents the simplification of static Watson-Crick context-free grammars; the grammatical counterparts of sticker systems that generate double-stranded strings using context-free rules, several transformations, and substitutions. The simplification process of static Watson-Crick context-free grammars is similar to the simplification process of arbitrary context-free grammars and Watson-Crick context-free grammars. This research shows that for every static Watson-Crick context-free language, there exists an equivalent static Watson-Crick context-free grammar without useless productions, λ − productions, and unit-productions. [ABSTRACT FROM AUTHOR]