The Study On Computing With Words

In this thesis, we mainly deal with computing with words via finitestate automata and grammars. The ideal of computing with words was proposedand advocated by Zadeh in a series of papers, and he pointed out that the primarycontribution of fuzzy sets is essentially the machinery of granular computing whichserves as a basis for the methodology of computing with words. Recently, Ying pro-posed a different understanding of "computing with words" within the frameworkof computing theory. He imagined"computing with words"as a computational pro-cedure as fuzzy sets of input alphabets, considered computing with words via fuzzyfinite state automata and fuzzy pushdown automata and established an extensionpriciple from computing with values to computing with word. Li has studied fuzzyautomata theory with truth values in the more general structure: lattice-orderedmonoid, and set the formal models of computing with words on the lattice-valuedfuzzy automata. It's shown that lattice-valued finite automata can recognise morelanguages than regular languages from the point of view of level structure, and thushave the more power to recognise fuzzy languages than classical fuzzy automata. Aswe all-known in the theory of classical automata and general fuzzy automata, it'san important conclusion that regular grammars and finite automata are equivalentin the recognitions of languages. Concerning with these problems, whether is theidea of computing with words via grammars also the same ways?The aim of this thesis is to point out that computing with words may be treatedfrom a different point of view and it may be interpreted as a computational proceduewith vague and imprecise input date. based on the understanding of"computing withwords". We establish a formal model for it in setting of automata theory. We discusscomputing with words for two most important and simplest kinds of automata andtwo most important of grammars. Namely, finite automata, pushdown automata,regular grammars and context-free grammars. We show that computing with wordscan be implement with computing with valudes with the price of big amout of extracomputations.We divide this thesis into four chapters. The first chapter is the preliminaries,wegive some basic concepts to be used within this thesis, in which the fuzzy sets theory and the notions of lattice-order monoid are reviewed. In the second chapter,we propose the notion of the degree to which a string of words are accepted byfinite automata and show that they can be derived from the acceptance degree ofa family of string of values. Computing with words via regular grammars are dealtwith in third chapter. The equivalence between lattice-valued finite state antomataand lattice-valued regular grammar are demonstrated,too. In the forth chapter,we demonstrate some equivalences between fuzzy pushdown automata, computingwith words via pushdown automata are dealt with in this chapter, we investigatecomputing with words via context-free grammars and the extension principles forcomputing with words via these grammars have been set up, too.