CREATE OWN LIBRARY
Introduction to Automata Theory
Prerequisite: Basic concept of set theory (see it), Relation (see it), Knowledge of alphabet, string, substring, prefix, suffix.
Theory of Computation :
Purpose of Theory of Computation: Develop formal mathematical models of computation using an algorithm that reflects real-world computers.
The Theory of Computation can be divided into the following three areas: automata theory and languages, computability theory, and computational complexity theory.
Automata Theory :
Automata theory is an abstract machine which deals with the definition and properties of different types of "computational models". Examples of such models are:
• Finite Automata: - An abstract model with finite memory. These are used in text processing, compilers, and hardware design.
• Push Down Automata: An abstract machine with unlimited memory in form of stack. These are used in the syntax analysis phase of compiler, stack applications, arithmetic expression.
• Linear Bounded Automata: An abstract model with infinite memory in form of bounded tape. These are used in semantic analysis of compiler, genetic programming.
• Turing Machines: The most powerful abstract machine with unlimited tape memory with no restrictions. These form a simple abstract model of a “real” computer, such as your PC at home. These are also used in artificial intelligence, neural networks, etc.
Language Theory :
Language theory is a branch of mathematics concerned with describing languages as a set of operations. It is closely linked with automata theory, as automata are used to generates and recognize formal languages. There are several classes of formal languages like
1. Regular Language
2. Context Free language
3. Context Sensitive Language
4. Recursive Language
5. Recursive Enumerable Language.
Computability theory :
The theoretical models that were proposed in order to understand solvable and unsolvable problems led to the development of real computers. So, actually, it classifies problems as being solvable or unsolvable on a computer.
Complexity Theory :
Complexity says how efficiently the problem can be solved. We are working with two types of complexity: time complexity and space complexity. Time complexity considers how much time an algorithm takes to perform a computation and space complexity how much memory is required to perform that computation.
So, complexity theory classifies problems according to their degree of “difficulty”. Give rigorous proof that problems that seem to be “hard” are really “hard”.
See next topics:
Contributed by
