形式语言学ch3.pdfVIP

第3章有穷自动机 主要内容 确定的有穷状态自动机(DFA) 作为对实际问题的抽象、直观物理模型、形式定义， DFA接受的句子、语言，状态转移图。 不确定的有穷状态自动机(NFA) 定义； NFA与DFA的等价性； 第3章有穷状态自动机 带空移动的有穷状态自动机(ε-NFA) 定义。 ε-NFA与DFA的等价性。 FA是正则语言的识别器 正则文法(RG)与FA的等价性。 相互转换方法。 带输出的有穷状态自动机。 双向有穷状态自动机。 1 第3章有穷状态自动机 重点：DFA的概念，DFA、NFA、ε-NFA 、RG之间的等 价转换思路与方法。 难点：对DFA概念的理解，DFA、RG的构造方法， RG 与FA的等价性证明。 3.1 语言的识别 推导和归约中的回溯问题将对系统的效率产生极大的影响 S→aA|aB A→aA|c B→aB|d 分析句子aaac 的过程中可能需要回溯。 S⇒aA ⇒aaA ⇒aaaA ⇒aaaA ⇒aaaaA ⇒aaac 2 3.1 语言的识别 n n 系统识别语言{a c|n≥1}∪{a d|n≥1}的字符串过程 中状态的变化图示如下： 3.1 语言的识别 识别系统(模型) ⑴ 系统具有有穷个状态，不同的状态代表不同的意义。 按照实际的需要，系统可以在不同的状态下完成规定的 任务。 ⑵ 我们可以将输入字符串中出现的字符汇集在一起构成 一个字母表。系统处理的所有字符串都是这个字母表上 的字符串。 3 3.1 语言的识别 ⑶ 系统在任何一个状态(当前状态)下，从输入字符串中 读入一个字符，根据当前状态和读入的这个字符转到新 的状态。当前状态和新的状态可以是同一个状态，也可 以是不同的状态；当系统从输入字符串中读入一个字符 后，它下一次再读时，会读入下一个字符。这就是说， 相当于系统维持有一个读写指针，该指针在系统读入一 个字符后指向输入串的下一个字符。 3.1 语言的识别 ⑷ 系统中有一个状态，它是系统的开始状态，系统在这 个状态下开始进行某个给定句子的处理。 ⑸ 系统中还有一些状态表示它到目前为止所读入的字符 构成的字符串是语言的一个句子，把所有将系统从开始 状态引导到这种状态的字符串放在一起构成一个语言， 该语言就是系统所能识别的语言。 4 3.1 语言的识别 相应的物理模型 一个右端无穷的输入带。 一个有穷状态控制器(finite state control,FSC) 。 一个读头。 系统的每一个动作由三个节拍构成：读入读头正注视的 字符；根据当前状态和读入的字符改变有穷控制器的状 态；将读头向右移动一格。 3.1 语言的识别 有穷状态自动机的物理模型 有穷控制器处于有穷状态中的第一个，带头注视到 一个字母a 时，可以发生状态的转变，且带头右移 i 一格。 带头 有穷控制器 5 3.2有穷状态自动机 有穷状态自动机(finite automaton,FA)