Research On Related Properties Of General-Nondeterministic Lattice-Valued Pushdown Automata

To bridge the gap between the accuracy of formal languages and the vagueness of natural languages,fuzzy automata and fuzzy languages have been paid much attention by a host of scholars.So far,fuzzy automata have been applied in a wealth of areas including word-based computational model,model checking,pattern recognition,and automata theory,etc.Bucurescu and Pascu introduced the concept of fuzzy pushdown automata which are regarded as important mathematical models in computational theory.The ideas of quantum computing stemmed from the connection between physics and computing.In order to develop quantum computing models,Ying established automata theory based on quantum logic.In 2012,Cao and Ezawa introduced the concept of nondeterministic fuzzy automata from a new perspective.Based on this,the paper further investigates fuzzy pushdown automata and quantum pushdown automata,which enriches pushdown automata theory.The main results of this paper are as follows:1.Firstly,the definitions of general-nondeterministic fuzzy pushdown automata(for short,GN-FPDA)and two ways of accepting fuzzy languages in GN-FPDA are given.It is verified that the set of fuzzy languages accepted by final states is equivalent to that accepted by empty stack in GN-FPDAs.Then,we elaborate that GN-FPDAs accept more kinds of languages than common fuzzy pushdown automata(for short,FPDA).And the relationships among GNFPDA,FPDA and deterministic fuzzy pushdown automata(for short,DFPDA)are studied,i.e.,(?).Secondly,the concept of general-nondeterministic fuzzy contextfree grammar(GN-FCFG)is introduced.It is proved that the leftmost derivations are equivalent to the rightmost derivations in GN-FCFGs.By means of this equivalence,we obtain that GN-FPDA can be constructed from GN-FCFG and vice versa.At last,taking advantage of GN-FCFGs,the closure properties of operations,such as union,intersection,concatenation and Kleene closure,on the set of fuzzy languages accepted by GN-FPDAs are discussed in detail.2.Firstly,the definition of general-nondeterministic quantum pushdown automata(for short,GN-(?) VPDA)is given.Also,we show that two ways of accepting quantum languages in GN-(?) VPDAs have the same recognition ability.Secondly,we have that the set of quantum languages accepted by GN-(?) VPDAs strictly contains that accepted by common quantum pushdown automata.Finally,an hierarchy of the sets of quantum languages accepted by several kinds of quantum pushdown automata is presented,that is,(?).