オートマトン、文法、言語、複雑系理論

最近オートマタ理論に関する本を読んでいます。What has captured my interest the most is the dependency relationship between four fundamental concepts of computer science: automata, grammars, languages, and computational complexity. The three prominent automata types are: Finite automata (deterministic and nondeterministic), pushdown automata, and Turing machines. Each of these corresponds to a class of languages: finite automata to regular languages, pushdown automata to context-free languages, and Turing machines to recursively enumerable languages. Each automaton type above can be constructed to accept any string in a language of the type associated with it. Each language type can be associated with a set of rules for constructing grammars of such languages.
文法の種類は基本的に以下に書きます。
1. Regular Grammars - a form of context free grammar with productions of the form:
n->w where n is a nonterminal and w is either a blank or a string containing at most one nonterminal, and the nonterminal is at the end if there at all.
2. Context-Free Grammars - all productions are of the form:
A-> w
Thus, the evaluation of the nonterminal does not depend on the context in which it is found.
3. Context-Sensitive Grammars- productions are of the form:
aAb-> w, where A is the nonterminal. Context-sensitive languages can be decided by a deterministic Turing machine, it seems (they are a subset of recursively enumerable). In fact, it seems that these can be decided by a linear bounded automaton, which is a Turing machine with bounded tape size.

As for complexity theory, the most famous categories of problems are P and NP. In particular, these categories are used for decision problems (given some input, issue a yes/no decision). P problems can be decided by a deterministic Turing machine in polynomial time. NP problems can be decided by a nondeterministic Turing machine in polynomial time and verified by a deterministic Turing machine in polynomial time.