Algebraic Properties And The Application Research Of Fuzzy Automata And Fuzzy Languages

Automata and formal languages have shown their importance for the devel-opment of computer science and its programming languages as well as softwares,moreover, they become extensively applied to the field such as life sciences, bio-chemistry, psychology and linguistics. As to the uncertainty or unprecise impactingon our complex systems, the research for computation theory on uncertain envi-ronment has become a hot topic since the1960. Characterizing formal languagesor even sorting them in some hierarchy was an important issue. To reduce the gapbetween formal and natural languages, fuzzy automata theory has been proposedand applied to solve meaningful issues rapidly. At present, fuzzy automata theorybased on lattice-ordered monoids and lattices, proposed by professor YongmingLi in2005and2011respectively, is the main direction for the research of fuzzyfinite automata. On the basis of the work introduced by Li, this thesis presentsfuzzy finite automata based on a po-monoid and investigate it from the view ofalgebra. Moreover, fuzzy grammar theory based on lattices is established on thebasis of breadth-first and depth-first ways. Taking intuitionistic fuzzy sets andstrong bimonoids as truth value domains respectively, fuzzy pushdown automataand context-free languages are then investigated in detail, which provide suitablemathematical models for natural languages in computation theory. The specificstructure and the main results of this thesis are as follows:(1) Algebraic properties of fuzzy finite automata based on po-monoids.Dropping the distributive laws, fuzzy finite automata (L-FFAs for short) basedon a more generalized structure L, named a po-monoid, are presented and inves-tigated from the perspective of algebra. The notions of (strong) successor andsource operators, fuzzy successor and source operators which are shown to be clo-sure operators on certain conditions are introduced and discussed in detail. Usingthe weak primary submachines, a unique decomposition theorem of a fuzzy finiteautomaton based on a lattice-ordered monoid is obtained. Taking L as a quantale,fuzzy subsystems are proved to be the same as fuzzy submachines of an L-FFA. Inparticular, intrinsic connections between algebraic properties of L and propertiesof some operators of an L-FFA are discovered. It is shown that the join-preservingproperty of fuzzy successor and source operators can be fully characterized by theright and left distributive laws respectively, and the idempotence of successor op-erator can be characterized equivalently by the nonexistence of zero divisors when L is a lattice-ordered monoid.(2) Fuzzy grammar theory based on lattices.On the basis of breadth-first and depth-first ways, we establish a fundamentalframework of fuzzy grammars based on lattices, which provides a necessary toolfor the analysis of fuzzy automata. We investigate the relationship among finiteautomata with membership values in lattices (l-VFAs), lattice-valued regular gram-mars (l-RGs) and lattice-valued deterministic regular grammars (l-DRGs). It isdemonstrated that, based on each semantic way, l-VFAs and l-RGs are equivalentin the sense that they accept or generate the same classes of fuzzy languages. Fur-thermore, it is proved that l-VFAs, l-valued deterministic finite automata, l-RGsand l-DRGs are equivalent based on the depth-first way. For any l-RG, the lan-guage based on the breadth-first way coincides with that based on the depth-firstway if and only if the truth-valued domain l is a distributive lattice.(3) On intuitionistic fuzzy context-free languages.Taking intuitionistic fuzzy sets as the structures of truth values, we proposethe notions of intuitionistic fuzzy context-free grammars (IFCFGs, for short) andpushdown automata with final states (IFPDAs). Then we investigate algebraiccharacterization of intuitionistic fuzzy recognizable languages including decompo-sition form and representation theorem. By introducing the generalized subsetconstruction method, we show that IFPDAs are equivalent to their simple form,called intuitionistic fuzzy simple pushdown automata (IFSPDAs), and then provethat intuitionistic fuzzy recognizable step functions are the same as those acceptedby IFPDAs. It then follows that intuitionistic fuzzy pushdown automata withempty stack and IFPDAs are equivalent. Additionally, we introduce the conceptsof Chomsky normal form grammar (IFCNF) and Greibach normal form grammar(IFGNF) based on intuitionistic fuzzy sets. The results of our study indicate thatintuitionistic fuzzy context-free languages generated by IFCFGs are equivalent tothose generated by IFGNFs and IFCNFs respectively, and they are also equiv-alent to intuitionistic fuzzy recognizable step functions. Then some operationson the family of intuitionistic fuzzy context-free languages are discussed. Finally,pumping lemma for intuitionistic fuzzy context-free languages is investigated.(4) Weighted pushdown automata and weighted context-free languages basedon strong bimonoids.On the basis of run semantics and breath-first algebraic semantics, weightedpushdown automata and weighted context-free grammars (WCFGs) over strong bimonoids are investigated. It is shown that weighted pushdown automata aremore powerful than weighted finite automata, and weighted pushdown automatawith final states (WPDAs) and empty stack (WPDAs) are equivalent based on runsemantics. Next the simple characterizations of the underlying strong bimonoidsare provided when for every weighted pushdown automaton, its run semanticsand breadth-first algebraic semantics coincide. For every WPDA, the image setof the recognizable series is finite if and only if the strong bimonoids is bi-locallyfinite. Moreover, it is demonstrated that for every WPDA, there is an equivalentcrisp-simple weighted pushdown automaton with final states by run semantics ifthe underlying strong bimonoids satisfies multiplicatively local finiteness condition.Finally, it is proved that, based on each semantics, WCFGs on the basis of theleftmost derivations and WPDAs are equivalent in the sense that they generatethe same classes of formal power series.