Grammars With Truth Values In Lattice-ordered Monoid And Their Languages

In this article ,we mainly studied lattice-valued grammars(LG) and their languages. In [19], Li has studied fuzzy automata theory with truth values in the more general structure: lattice-ordered monoid, and set the formal models of computing with words on the lattice-valued fuzzy automata. It's shown that LA can recongnize more languages than regular languages from the poit of view of level structure, and thus have the more power to recongnize fuzzy languages than classical fuzzy automata . As well-known in the theory of classical automata and general fuzzy automata, it's an important conclusion that regular grammars and finite automata are equivalent when it comes to the recognitions of languages. Now that DLA and LA are not equivalent in the recognizing fuzzy languages, naturally we shall consider how to characterize the languages recongnized by DLA and LA with lattice-valued grammars, respectively. Concerning with this problem, we study the structure of lattice-valued regular grammars(LRG)and the equivalence between LA and LRG, some properties of lattice-valued regular languages(LRL),lattice-valued (L-valued) context-free grammar(LCFG), the properties of L-valued context-free languages (LCFL) are also considerded.We divide the article into five chapters. The first chapter is preliminarlies, in which the classical automata theory and formal grammar theory are reviewed.In the second chapter, L-valued automata and L-valued grammars are introduced. A special kind of grammar which to charaterize the languages generated by DLA are given, and the equivalence between LA and LRG, DLA and deterministic L-valued regular grammars(DLRG) are also shown. The main results are as following,(1)LA and LRG are equivalent in the recognizing fuzzy languages;(2) DLA and DLRG are equivalent in the recognizing fuzzy languages.In the third chapter, from the viewpoint of grammar, we studied the property of L-valued regular languages(LRL). The closeness of family of LRL and dererministic L-valued regular languages (DLRL) under regular operations are respectively discussed. In the end , some sufficient and necessary conditions to guarantee the LRG and DLRG being equivalent are given. The main results are as following,(1)The family of LRL is closed under the operations of join, concatenation, the Kleene...