自动机理论研究输入序列的计算系统，分为四类：有限自动机（FA）识别正则语言；下推自动机（PDA）通过栈识别上下文无关语言；线性有界自动机（LBA）识别上下文相关语言；图灵机（TM）是最强大的，能识别递归可枚举语言，构成现代计算的理论基础。