Fuzzy Approximation Of The Grammar

Grammar theory is the basis of research of algorithm description and analysis, the theory of computation complexity, and computability, etc. It provides a reliable mathematical model of computation theory. Fuzzy grammar also serves a powerful tool as studying and treating natural languages with fuzziness, and will serve a suitable formal method as soft computing theory based on words.The main objective of current paper is to study fuzzy grammars and their languages. Inspired by the literature, we investigate fuzzy grammars under max-compositional inference for some t-norm, that is to say, we study fuzzy grammars theory in a more general structure, which includes fuzzy regular grammar under max-compositional inference (FRG₎ and fuzzy context-free grammar under max-compositional inference (FCFG₎ for some t-norm. However, fuzzy grammars under max-compositional inference using different kinds of t-normare not necessaryequivalent. It is necessary for us to investigate the condition under which they are equivalent, as well as whether we can always approximate the given fuzzy grammar G₁ under max-₁ compositional inference by a fuzzy grammar G₂ under max-₂ compositional inference. Considering this problems, we study the relationshipof fuzzy grammars under max-compositional inference using different kinds of t-norm, the approximation of FRG_and FCFG_, and the properties of fuzzy languages generated by the two kinds of fuzzy grammars.We divide the article into three chapters. In the first chapter, the fuzzy mathematicstheory and the formal grammar theory are reviewed, including the classificationand several main results of the formal grammar.In the second chapter, fuzzy regular grammars under max-compositional inferenceand their languages are introduced. Next, we use the regular languages to characterize the level of fuzzy regular languages, and present the classification of fuzzy regular grammars. The main results are as follows,(1) If t-normsatisfies Finite Generated Condition (FGC), then FRG_and FRG_Λ(Λis the minimum operation) are equivalent in the generating fuzzy languages; (2) If t-normdoes not satisfy FGC, then FRG_is not equivalent to FRG_Λin the generating fuzzy languages in general, but they are equivalent in the approximate sense.(3) We introduce the finite basis weakly fuzzy regular grammar, which is proved to be equivalent to FRG_and has the approximation property.In the third chapter, we continue to discuss the approximation property of FCFG_with max-composition for some t-norm, and some nice results are obtained.Mmore concretely,(1) The reduction forms of FCFG_are presented;(2) If t-normdoes not satisfy FGC, then FCFG_is not equivalent to FCFG_Λin the generating fuzzy languages in general, but they are equivalent in the approximatesense.(3) Based on the imprecision of match function for the FCFG_production, we present the sensitivity of FCFG_....