1、第八章第八章 形式形式语言与自动机语言与自动机 自动机的概念在自动机的概念在19361936年首先由图灵年首先由图灵（A AM MTuringTuring）提）提出，他设计的自动机出，他设计的自动机称为称为图灵机图灵机。以后，丘奇（以后，丘奇（ChurchChurch）提出了一个提出了一个假设假设：图：图灵机的计算能力代表灵机的计算能力代表着可实现的计算装置着可实现的计算装置的基本范围。的基本范围。可以证明，任何能在可以证明，任何能在电子计算机上实现的电子计算机上实现的计算都能用图灵机进计算都能用图灵机进行行描述描述。形式语言大约于形式语言大约于 19561956年问世，年问世，NN乔乔姆斯基
2、姆斯基（Noam Noam ChomskyChomsky）给出一种文）给出一种文法的数学模型。法的数学模型。到了到了19591959年，乔姆斯年，乔姆斯基又将文法分为基又将文法分为四类四类，即即0 0型型（无限止无限止）文法文法、1 1型型（上下文有关上下文有关）文文法法、2 2型型（上下文无关上下文无关）文法文法和和3 3型型（正则正则）文文法法。现在已可以证明，它现在已可以证明，它们分别和们分别和图灵机图灵机、不不确定的线性界限自动确定的线性界限自动机机、不确定的下推自不确定的下推自动机动机和和有限自动机有限自动机等等价。价。随着计算机高级语言随着计算机高级语言的发展，人们发现的发展，人们
3、发现 ALGOLALGOL语言可由语言可由上下文上下文无关语言无关语言定义。因此，定义。因此，形式语言与编译理论形式语言与编译理论有着密切的联系。有着密切的联系。此外，形式语言作为此外，形式语言作为一个广泛的一个广泛的数学模型数学模型，它描述了科学技术和它描述了科学技术和各种工程中的变化过各种工程中的变化过程。程。从此之后，研究工作从此之后，研究工作相当活跃，形式语言相当活跃，形式语言和自动机理论相互渗和自动机理论相互渗透，紧密结合，使它透，紧密结合，使它成为计算机科学的一成为计算机科学的一个重要分支。个重要分支。这些理论在这些理论在编译程序编译程序理论理论、人工智能人工智能、可可计算性计算性
4、和和时序电路设时序电路设计计等领域中有着广泛等领域中有着广泛的应用。的应用。第九章第九章 纠错码纠错码初步初步 纠错编码纠错编码技术是技术是五十年代提出，六十五十年代提出，六十年代发展起来的。年代发展起来的。近来，由于近来，由于数字通讯数字通讯，特别是卫星通讯的发特别是卫星通讯的发展，以及在展，以及在数字计算数字计算机机和和数据处理数据处理等新兴等新兴科学技术中广泛应用，科学技术中广泛应用，给纠错码开拓了新的给纠错码开拓了新的发展前景。发展前景。9-1 9-1 通讯模型和纠错通讯模型和纠错的基本概念的基本概念 通讯方法：写一通讯方法：写一封封信信，通一次，通一次电话电话，发一份发一份电报电报，
5、通过，通过广广播播等多种手段。等多种手段。一般通讯手段都要经过一般通讯手段都要经过三个必要步骤：三个必要步骤：1 1在发送端将所要传送的在发送端将所要传送的信息信息转换成转换成电信号电信号。2 2通过可靠的信道，通过可靠的信道，传输传输电信号。电信号。3 3在接收端将在接收端将接收接收到的到的电电信号信号还原成还原成原来的信息原来的信息。电信号可分为电信号可分为模模拟信号拟信号和和数字信号数字信号两两种。种。例如例如电话机电话机话筒输出的话筒输出的电压电压，其幅值随说话人，其幅值随说话人的语有连续变化，它与的语有连续变化，它与信息直接对应，且可取信息直接对应，且可取无限多个值，这种信号无限多个
6、值，这种信号称为称为模拟信号模拟信号。又如又如电报电报，是以四个数字，是以四个数字代表一个汉字，且代表每代表一个汉字，且代表每个数字的个数字的脉冲信号脉冲信号，其高，其高度只取度只取两个值两个值分别表示分别表示空空号号和和传号传号，（通常用（通常用0 0和和1 1表示）表示）这种信号不仅在取值这种信号不仅在取值上有限和离散，而且上有限和离散，而且在时间上也是离散的，在时间上也是离散的，它称为它称为离散信号离散信号或或数数字信号字信号。在现代数字通讯系统在现代数字通讯系统和计算机中，信号都和计算机中，信号都采用采用二进制二进制，即用一，即用一个由个由“0”“0”或或“1”“1”组组成的成的符号串符号串来表示来表示传传输的信息输的信息。
