形式语言和自动机.PPT

形式语言和自动机 自动机的概念在1936年首先由图灵（A．M．Turing）提出，他设计的自动机称为图灵机。 以后，丘奇（Church）提出了一个假设：图灵机的计算能力代表着可实现的计算装置的基本范围。 可以证明，任何能在电子计算机上实现的计算都能用图灵机进行描述。 形式语言大约于 1956年问世， N·乔姆斯基（Noam Chomsky）给出一种文法的数学模型。 到了1959年，乔姆斯基又将文法分为四类，即0型（无限止）文法、1型（上下文有关）文法、2型（上下文无关）文法和3型（正则）文法。 现在已可以证明，它们分别和图灵机、不确定的线性界限自动机、不确定的下推自动机和有限自动机等价。 随着计算机高级语言的发展，人们发现 ALGOL语言可由上下文无关语言定义。因此，形式语言与编译理论有着密切的联系。 此外，形式语言作为一个广泛的数学模型，它描述了科学技术和各种工程中的变化过程。 从此之后，研究工作相当活跃，形式语言和自动机理论相互渗透，紧密结合，使它成为计算机科学的一个重要分支。 这些理论在编译程序理论、人工智能、可计算性和时序电路设计等领域中有着广泛的应用。