摘要: 形式语言理论是计算机科学的一个重要分支，这一领域是在1956年前后形成的．那时，Noam Chomsky 在他的自然语言的研究中给出了文法的数学模型，并且采用对产生式加限制的办法将文法分成了四类．尽管这四类文法还不能够很好地描述自然语言，但却令人满意地描述了程序设计语言．1960年，人们利用上下文无关文法定义了算法语言 ALGOL 的语法，从而发现了文法的概念对于程序设计者的极大的重要性．这就很自然地引出了语法制导编译和编译程序的编译程序概念．此后，形式语言理论便得到很大的发展．特别是已经把形式语言与自动机理论紧密地联系起来，以致于想孤立地研究这两个领域是不可能了．