第八部分形式语言与自动机-精选.ppt

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