ctchapt1.ppt

第一章正则语言 计算理论 图灵对计算的观察 图灵 计算通常是一个人拿着笔在纸上进行的 他根据 眼睛看到的纸上符号 脑中的若干法则 指示笔 在纸上擦掉或写上一些符号 再改变他所看到的范围 继续 直到他认为计算结束 脑 控制器纸 存储带眼睛和笔 读写头法则 转移函数 一个简单的有限自动机 q1 状态 M1有3个状态q1 q2 q3起始状态q1 用指向它的无出发点的箭头标示接受状态q2 用双圈标示转移 从一个状态指向另一个状态的箭头 运行 从起始状态开始根据输入和转移箭头进行 输出 输入读完处于接受状态则接受 否则拒绝 有限自动机的形式定义 定义 有限自动机是一个5元组 Q q0 F Q是有限集 称为状态集 是有限集 称为字母表 Q Q是转移函数 q0 Q是起始状态 F Q是接受状态集 状态图与形式定义包含相同信息 DFA识别的语言 设A是DFAM接受的全部字符串组成的集合 则称A是DFAM的语言 记作L M A 又称M识别A 注意 无论在哪个状态 读到1后一定会进入状态q2 L M1 w w是由0 1组成的字符串 至少含有一个1 并且最后一个1后面含有偶数个0 有限自动机的设计 读者即自动机需要记住的关键信息设计识别下列语言的DFA w w从1开始 以0结束 w w含有子串110 DFA计算的形式定义 设M Q q0 F 是一台DFA w w1w2 wn是字母表 上的一个字符串 若存在Q中的状态序列r0 r1 rn 满足r0 q0 ri wi 1 ri 1 rn F则M接受w 事实上 对于任意输入 DFA有且仅有唯一路径 若rn F 则接受 正则语言与正则运算 如果语言A被一DFA识别 则称A是正则语言算术中 对象是数 操作是运算 如 计算理论中 对象是语言 操作是语言的运算 定义 设A和B是两个语言 定义正则运算并 连接 星号如下 并 A B x x A或x B 连接 A B xy x A且y B 星号 A x1x2 xk k 0且每个xi A 正则运算举例 设字母表 由标准的26个字母组成A good bad B boy girl 则A B good bad boy girl A B goodboy goodgirl badboy badgirl A good bad goodgood goodbad 问题 如何描述一个自动机所识别的语言如何判断一个语言是正则语言正则运算对于正则语言是否封闭 正则运算的封闭性 定理 正则语言对并运算封闭 证明 构造转移函数 定理 正则语言对连接运算封闭 定理 正则语言对星号运算封闭 非确定性 DFA在计算的每步以唯一的方式进入下一个状态因为 Q Q是一个函数所以有限自动机又称为确定型有限自动机 DFA 现在来引入非确定型的有限自动机 NFA NFA的特点 一个输入可对应0至多个输出转移箭头上的符号可以是空串 NFA的计算方式 Step1 设读到符号s 对 每个备份 机器状态q 若q有多个射出s箭头 则机器分裂成多个备份 状态相同的备份视为同一备份 Step2 对每个备份的状态 若其上有射出的 箭头 则不读任何输入 机器分裂出相应备份 Step3 读下一个输入符号 转step1 若无输入符号 计算结束 并且 若此时有一个备份处于接受状态 则接受 否则拒绝 NFA的计算实例 输入01011 注 若q0有射出的 箭头 则q0先分裂成相应备份 NFA的计算实例 输入01011 注 若q0有射出的 箭头 则q0先分裂成相应备份 NFA的形式定义 定义 NFA是一个5元组 Q q0 F Q是状态集 是字母表 Q P Q 是转移函数 q0 Q是起始状态 F Q是接受状态集 状态图与形式定义包含相同信息 NFA计算的形式定义 设N Q q0 F 是一台NFA w是 上字符串若w能写作w w1w2 wn wi 且存在Q中的状态序列r0 r1 rn 满足r0 q0 ri 1 ri wi 1 rn F则M接受w 对于任一输入 NFA计算的路径可能不唯一 NFA的设计 读者即自动机需要记住的关键信息设计识别下列语言的NFA w w从1开始 以0结束 w w含有子串0101 NFA与DFA等价 定理 每个NFA都有一台等价的DFA 证明 构造转移函数 正则运算的封闭性 定理 正则语言对并运算封闭 定理 正则语言对连接运算封闭 定理 正则语言对星号运算封闭 证明 画状态图 正则表达式 定义 称R是一个正则表达式 若R是1 a a R 2 3 4 R1 R2 这里R1和R2是正则表达式 5 R1 R2 这里R1和R2是正则表达式 6 R1 这里R1是正则表达式 每个正则表达式R表示一个语言 记为L R 例 0 10 01 10 1 正则表达式与DFA等价 定理 一个语言正则当且仅当可以用正则表达式描述它 非正则语言 B 0n1n n 0 C w w中0和1的个数相等 D w w中01和10的个数相等 泵引理 定理 泵引理 设A是正则语言 则存在p 0使得