本文中用P_n表示P[1..n]，用P[n]表示P中的第n个字符，用P_i\sqsupset P_q代表P_i是P_q的后缀，用P …

Minsky’s Theorem A two-pushdown stack machine, abbr. 2PDA, is a P ̷

Three-address code The compilers do not treat the part of the pro …

Post Machines   A particular “universal computing machine” is int

Language Processors A compiler is a program that read a program i …

Turing Machine   We’re about to introduce a new kind of machine t ̷

Decidability   Some of the problems are decidable and some others …

Context-Free Languages Closure Properties Union Context-Free Lang …

Non-Context-Free Languages Self-Embeddedness Theorem 1 Let G be a …

CFG=PDA There is a PDA that accepts the same language for every C …