| 词条 | 语言识别器 |
| 释义 | § 语言识别器 形式语言中的四类基本语言，即字母表（有限符号集）中符号所组成的链的集合（见短语结构文法），分别对应着四类自动机。当某类自动机能接受、且只能接受某类形式语言（即相应类的输入信号符号串）时，就称该类自动机与相应类的形式语言等价。而该类自动机也就是相应形式语言的识别器。在模式识别中，当一类模式能用短语结构文法来描述时，相应的自动机可作为该类模式的识别器。这样可以把有关形式语言文法的性质和相应自动机的性质结合起来研究，互相补充。通过自动机极易获得相应形式语言文法的识别程序，识别程序乃是数字计算机编译程序的核心，可用于完成对语言句子的语法分析，最终可用于模式识别。 自动机是离散数字动态系统的数学模型。很多实际问题可以用自动机这样一种数学模型来进行分析。例如按顺时针方向或逆时针方向转动某个规定角度的操作可以用一些基本动作组成的链表示,设R代表顺时针方向转动30°,L代表逆时针方向转动30°,RLLRRR 就表示先顺时针方向转动30°，接着逆时针方向转动60°，然后再顺时针方向转动90°。把一个数字锁从初始的锁住状态转移到开启状态这样一个问题便可以用自动机的状态集合(这个集合中包含有初始状态和终止状态)、输入符号集合（上述例子中的{R、L}）以及状态转移函数这样一种数学模型进行分析。对自动机的研究，开始于20世纪30年代。1936年英国数学家A.M.图灵首先提出图灵机概念。这种数学模型在物理上可以用一个有限控制器和一个输入磁带来进行讨论。输入磁带上划分为方格，一个方格可容纳一个输入符号或空白。在每一离散时刻，有限控制器处于某有限状态集合中的一个状态。通过扫描输入磁带上的符号和作一系列状态转移，来实现计算的功能。 自动机按存储和状态转移特性分为四类。①有限自动机：它的状态转移，仅取决于当前输入符号和有限控制器的当前状态，当输入符号不为空白而使状态转移时，磁头便右移一个方格，对准下一个输入符号。②下推自动机：它比有限自动机多一个下推存储器，它的状态转移取决于输入符号、有限控制器的当前状态以及下推存储器顶端的符号。在状态转移时，不仅能向右移动输入磁头，而且能改变下推存储器的内容。③图灵机：它虽然没有下推存储器，但在状态转移时可改写输入磁带上的符号，并允许磁头或左或右双向移动。④线性有界自动机：它是图灵机的一种特殊形式，它的磁头移动时不会离开输入符号串在磁带上所占据区间。 如果一个自动机于初态时开始扫描一输入符号串 x，经过一系列状态转移，在扫描完x 时恰好进入一个终态，则输入符号串 x为该自动机所接受或识别。自动机理论的主要结果之一是上述各类自动机可以作为乔姆斯基层次中各类形式语言的识别器。具体地说，图灵机接受的语言为0型语言,即递归可数集；线性有界自动机接受的语言为1型语言,即上下文敏感语言；下推自动机接受的语言为2型语言,即上下文无关语言；有限自动机接受的语言为3型语言，即正规集。 除上述经常讨论的四种对应关系外，有些形式语言文法（如线性文法、顺序文法、界限语言等）所对应的自动机还没有专名，而有些自动机(如堆栈自动机等)所对应的文法也没有专名。这表明文法和自动机同中有异，有些问题从文法入手研究较容易，而有些问题则从自动机入手研究较容易。 参考书目 J.E.Hopcroft,J.D.Ullmann,Introduction to Automate Theory， Languages, and Computation, Addison-Wesley Publ.Co., Reading Mass., 1979. § 配图 § 相关连接 |
| 随便看 |
百科全书收录594082条中文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。