上下文无关文法与无限状态自动机

摘要

目前，在研究上下文无关语言时常用的形式系统是上下文无关文法和下推自动机，在研究正则语言时常用的形式系统是正则文法和有限状态自动机。正则文法中的符号和有限状态自动机的符号之间的对应关系比较明显，因此，两种系统之间的转换比较容易，并且在这两种系统中观察语言时，可以得到一致的解释。