Study Of Several Issues Of Formal Language And Automata Theory

Computation theory is the mathematic theory for solving computational problems with computers. The three main research areas of the theory are: formal language and automata theory, computability theory and the computing complexity theory. The core issue of the computability theory is to establish mathematic model of the computation and then decide its computability. The computing complexity theory discusses the time complexity and the space complexity of the algorithms. The objective of the complexity theory is to group the computable problems into simple problems and complex ones.Formal language and automata theory discusses the definition and properties of the computational models. These models play a significant role in many fields of computer science and the range of application has been extended to multiple fields like bioengineering, automatic control system, image processing and pattern recognition.The dissertation discusses formal language theory, automata theory and the equivalency of formal language and automata. Research area includes:(1)Issues regarding blank stringεof formal language and automata theory.(2)The effective closer issue of four types of languages by join, linkage and Kleene closure operations.(3)The method of creating a specific type of finite state automata by equivalence class.(4)The universal reasonable coding system for Turing machines.(5)A new technique to create Turing machines: substring scan technique.(6)The Turing computable issue of k-variable functions of non-negative integers by relational operations and arithmetic operations.(7)The Turing computable issue of non-negative binary integers by relational operations and arithmetic operations.