词义说明
automata theory 指研究抽象计算装置(自动机)及其所能识别的语言、所能完成的计算的数学理论。其本义中的 automata 是 automaton 的复数,指按预定规则逐步改变状态的抽象机器;theory 指系统的理论体系。该词组的核心义项包括:一、形式语言与自动机的研究,即有限自动机、下推自动机、图灵机等模型及其对应的正则语言、上下文无关语言等;二、计算能力的层次划分,即不同自动机模型在识别能力上的强弱关系;三、作为理论计算机科学的基础分支,为编译原理、算法设计、可计算性理论提供形式化工具。由本义到引申义,其重心从具体的机械装置转向抽象的数学结构,再扩展到对计算本质的普遍刻画。