Sufficiency Conditions for Well-Formedness of Quantum Context-Free Grammars

Natural computing refers to computing inspired by nature. This includes research areas such as membrane computing, DNA computing [ 7 , 10 , 12 ] and quantum computing. These models of computing especially quantum computing have been of interest recently. Moore and Crutchfield [ 9 ], in the year 2000 introduced the concept of quantum grammars wherein a notion of amplitude of a word derived from an initial nonterminal and associated probability of the word are defined. This quantum version is interesting in the sense that several classical results related to grammars have analogs in the quantum case. In particular, these authors show that there are quantum context-free languages that are not context-free. But the final probability of the derived word in a quantum context-free grammar is not studied by these authors. In this paper we begin investigating the probability associated with the derived word, especially in a quantum context-free grammar. We introduce suitable conditions on these grammars in order to ensure that the derived word does not have associated probability exceeding one. We call the language generated by these quantum grammars with this probability requirement as a well-formed language. Moreover we discuss the conversion of a general well-formed quantum context-free grammar satisfying these conditions to the corresponding Chomsky and Greibach normal forms.