第八部分形式语言与自动机.PPT

《第八部分形式语言与自动机.PPT》由会员分享，可在线阅读，更多相关《第八部分形式语言与自动机.PPT（56页珍藏版）》请在三一办公上搜索。

1、第八章 形式语言与自动机,自动机的概念在1936年首先由图灵（AMTuring）提出，他设计的自动机称为图灵机。,以后，丘奇（Church）提出了一个假设：图灵机的计算能力代表着可实现的计算装置的基本范围。,可以证明，任何能在电子计算机上实现的计算都能用图灵机进行描述。,形式语言大约于 1956年问世，N乔姆斯基（Noam Chomsky）给出一种文法的数学模型。,到了1959年，乔姆斯基又将文法分为四类，即0型（无限止）文法、1型（上下文有关）文法、2型（上下文无关）文法和3型（正则）文法。,现在已可以证明，它们分别和图灵机、不确定的线性界限自动机、不确定的下推自动机和有限自动机等价。,随着

2、计算机高级语言的发展，人们发现 ALGOL语言可由上下文无关语言定义。因此，形式语言与编译理论有着密切的联系。,此外，形式语言作为一个广泛的数学模型，它描述了科学技术和各种工程中的变化过程。,从此之后，研究工作相当活跃，形式语言和自动机理论相互渗透，紧密结合，使它成为计算机科学的一个重要分支。,这些理论在编译程序理论、人工智能、可计算性和时序电路设计等领域中有着广泛的应用。,第九章 纠错码初步,纠错编码技术是五十年代提出，六十年代发展起来的。,近来，由于数字通讯，特别是卫星通讯的发展，以及在数字计算机和数据处理等新兴科学技术中广泛应用，给纠错码开拓了新的发展前景。,9-1 通讯模型和纠错的基本

3、概念,通讯方法：写一封信，通一次电话，发一份电报，通过广播等多种手段。,一般通讯手段都要经过三个必要步骤：1在发送端将所要传送的信息转换成电信号。2通过可靠的信道，传输电信号。3在接收端将接收到的电信号还原成原来的信息。,电信号可分为模拟信号和数字信号两种。,例如电话机话筒输出的电压，其幅值随说话人的语有连续变化，它与信息直接对应，且可取无限多个值，这种信号称为模拟信号。,又如电报，是以四个数字代表一个汉字，且代表每个数字的脉冲信号，其高度只取两个值分别表示空号和传号，,（通常用0和1表示）这种信号不仅在取值上有限和离散，而且在时间上也是离散的，它称为离散信号或数字信号。,在现代数字通讯系统和计算机中，信号都采用二进制，即用一个由“0”或“1”组成的符号串来表示传输的信息。,