Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science . The word automata (the plural of automaton) comes from the Greek word αὐτόματα, which means “self-making”.

Automata theory is closely related to formal language theory. An automaton is a finite representation of a formal language that may be an infinite set. Automata are often classified by the class of formal languages they can recognize, typically illustrated by the chomsky hierarchy, which describes the relations between various languages and kinds of formalized logics.

# Chomsky Hierarchy

Chomsky–Schützenberger hierarchy This hierarchy of grammars was described by Noam Chomsky in 1956. It is also named after Marcel-Paul Schützenberger, who played a crucial role in the development of the theory of formal languages.

FORMAL GRAMMAR

A formal grammar provides an axiom schema for (or generates) a *formal language*, which is a (usually infinite) set of finite length of symbols that may be constructed by applying production rules to another sequence of symbols (which initially contains just the start symbol). A rule may be applied by replacing an occurrence of the symbols on its left-hand side with those that appear on its right-hand side. A sequence of rule applications is called a derivation. Such a grammar defines the formal language: all words consisting solely of terminal symbols which can be reached by a derivation from the start symbol.

A formal grammar of this type consists of a finite set of production rules (left-hand side → right-hand side), where each side consists of a finite sequence of the following symbols:

a finite set of nonterminal symbols (indicating that some production rule can yet be applied)

a finite set of terminal symbol (indicating that no production rule can be applied)

a *start symbol* (a distinguished nonterminal symbol.

Nonterminals are often represented by uppercase letters, terminals by lowercase letters, and the start symbol by *S*. For example, the grammar with terminals {*a, b*}, nonterminals {*S, A, B*}, production rules

*S* → *AB*

*S* → *ε* (where *ε* is the empty string)

*A* → *aS*

*B* → *b*

and start symbol *S*, defines the language of all words of the form

Type-0 grammars include all formal grammars. They generate exactly all languages that can be recognized by a turing machine.. These languages are also known as the recursively enumerable or Turing-recognizable languages.^{ }Note that this is different from the recursive language. Type-1 grammars generate context-n sensitive languages each of these grammars has a rule of linear bounded non- deterministic Turing machine with non-terminal strings of terminal. Type-2 grammars generate context-free languages which are defined rules by a form of non-deterministic pushdown. While Type-3 grammars generate the regular language, such a grammar restricts its rules to a single nonterminal on the left-hand side and a right-hand side consisting of a single terminal, possibly followed by a single nonterminal (right regular).

**Note that: **Every regular language is context-free, every context-free language is context-sensitive, every context-sensitive language is recursive and every recursive language is recursively enumerable. These are all proper inclusions, meaning that there exist recursively enumerable languages that are not context-sensitive, context-sensitive languages that are not context-free and context-free languages that are not regular.

## Turing Machine

A Turing machine is a mathematical model of a hypothetical computer machine which can use a predefined set of rules to determine a result from a set of input variables. A turing machine is a system of rules, states and transition rather than a real machine, it is used mainly for deciding formal languages and solving mathematical functions, it’s one of the most important formal models in the study of computer science.

## Application

Each model in automata theory plays important roles in several applied arrears, finite automata are used in processing compilers and hardware designs, these automata are responsible for compiler flagging error when code syntax is wrong. Ms Word, excel and other word processors also use them to check if a sentence is correct or wrong. Context-free grammars (CFGs) are used in programming language and artificial intelligence. But then, it was used originally to study human languages. Cellular automata are used in the field of biology. Going further, a study suggesting that the whole universe is computed by some sort of a discrete automaton, is advocated by some scientists. The idea originated in the work of Konard zuse, and was popularized in America by Edward Franklin.