形式语言4.ppt

1 刘晓华 形式语言与自动机 2 第四章正则语言的性质 1正则语言的封闭性性质1两个正则语言的并 连接 星号所得语言仍是正则语言 证 第三章第2节已证 性质2两个正则语言的交 差 补所得语言仍是正则语言 证 1 先证 若L是正则语言 则其补 L也是正则语言 设A1是接受L的一台DFA 则将A1的非接受状态改为接受状态 接受状态改为非接受状态 所得自动机即为A1的补A 3 2 交 L A L A1 L A2 L A L A1 L A2 3 差 L A L A1 L A2 L A L A1 L A2 定义1 语言L的反转 转置 为LR wR w L 性质3正则语言L的反转LR仍是正则语言 证 设接受L的DFA为A 将A的全部弧反向 将原初始状态改为接受状态 将原接受状态改为普通状态 引入一个新初始状态s 并分别从s引 边到原各接受状态 设所得DFA为A 则L A LR 故LR仍是正则的 4 定义2对于字母表 1和 2 函数h 1 2 称为 1上的一个同态 若w a1a2 an ai 1 则h w h a1 h a2 h an 例如 h 0 ab h 1 aa 则h 010 abaaab h 10 10 aaab aa ab 性质4若L是 上的正则语言 h为 上的一个同态 则L在h下的像h L 也是正则语言 证 因为L是正则语言 故有正则表达式R满足L R L 在R中出现的每个字母c用h c 替换 这样得到一个新正则表达式R 易知L h L L R 故h L 也是正则语言 5 定义3语言L1和L2的右商定义为L1 L2 x xy L1 y L2 例如 若L1 bbaab babab aaabb L2 ab aab 则L1 L2 bbaa bb bab 性质5若L1和L2是 上的正则语言 则L1 L2也是正则语言 证 设接受L1的DFA为A1 Q1 1 q10 F1 接受L2的DFA为A2 Q2 2 q20 F2 定义一个新的DFAB Q1 1 q10 F 注意B与A仅终态集合不同 其中F以下列方式定义 6 考察Q1的每一个状态q 将A1作一修改 初始状态由q10改为q 其余一切不变 所得的DFA记为Dq 记L L Dq L A2 则L仍为正则语言 若L 则让q作为B的非终态 即q F 若L 则让q作为B的终态 即q F 可以验证 这样定义的DFAB接受的语言就是L1 L2 故L1 L2是一个正则语言 7 2正则语言的基本问题1 正则语言的标准表示法 正则语言表示成有穷自动机 正则表达式或正则文法2 正则语言的基本问题问题1 对于任意正则语言L和任一字符串w 判断w是否属于L 定理1对于用标准表示法给出的正则语言L和任一字符串w 有算法可判断w是否属于L 证 标准表示法总可以归结为用DFA给出 而DFA是否接受w很容易判断 8 问题2正则语言是有穷的还是无穷的 定理2对于用标准表示法给出的正则语言L 有算法可判断L是否是空的 有穷的 还是无穷的 证 标准表示法总可以归结为用DFA给出 用图论的可达算法 Warshall算法 可知L是否为空 如果DFA中存在有向回路C 从C的结点可到某终态 则L是无穷的 如果DFA中所有的有向回路上的结点均不能到任何终态 则L是有穷的 9 问题3对于正则语言L1和L2 是否成立L1 L2 定理3对于用标准表示法给出的正则语言L1和L2 有算法可判断是否L1 L2 证 标准表示法总可以归结为用DFA给出 在第二章的补充内容中 可用填表算法判断两个DFA是否等价 10 3证明语言为非正则的方法用反证法 只需证明L不满足正则语言所需的下列必要条件 泵引理若L是一个正则语言 则必存在与L相关的正整数N 对任一w L 只要 w N 就有分解w xyz 满足 xy N y 且xyiz L i 0 1 2 3 这个定理的含义是 若将一个可接受的串等同于一条由初始状态到接受状态的路线 则这样长于N的任意一条路线必包含一个回路 11 证 因为L是正则的 故L为某确定型自动机A接受的语言 设A共有状态N个 若w L且 w N 则由初始状态到接受状态的路线所经节点个数 N 故其中必有两个节点q q 相同 记w中初始状态至q 这部分为x 由q 至q 的部分为y 由q 至接受状态的部分为z 则w xyz即为所求 xyiz L i 0 1 2 3 12 例1证明L 0i1i i 0 不是正则的 证 若L是正则的 则泵引理成立 设N为泵引理中的正整数 考虑w 0N1N L 则由w xyz xy N及y 知x 0k y 0k k 0 从而xz 0k 0N k k1N 0N k1N L 矛盾 使用泵引理时 选用合适的w是关键 选择得好 则证明过程较为简单 选择不合适 则讨论的情形可能比较复杂 甚至得不到需要的结果 13 例2证明L wwR w a b 不是正则的 证 若L是正则的 则泵引理成立 设N为泵引理中的正整数 考虑w aNbNbNaN L 则w满足泵引理中条件 于是由w xyz xy N及y 知x ak y ak k 0 从而xz ak aN k kbNbNaN aN kbNbNaN L 矛盾 14 例2证明L w a b na w 0 从而xz bk bN k kaN bN 1 kaN L 矛盾 所以 L不是正则的 15 例3证明L ab nak n k k 0 不是正则的 证 若L是正则的 则LR ak ba n n k k 0 也是正则的 从而对LR泵引理成立 设N为定理中的正整数 考虑w aN ba N 1 LR 则w满足泵引理中条件 于是由w xyz y 知x ak y ak k 0 从而xy2z ak a2kaN k k ba N 1 aN k ba N 1 L 矛盾 所以 L不是正则的 16 例4证明L an n 0 不是正则的 证 若L是正则的 则泵引理成立 设N为定理中的正整数 考虑w aN L 则w满足泵引理中条件 于是w xyz y 且对于k 0 有xykz L 设x ap y aq q 0 z ar 则xykz L 即p kq r nk k 0 1 2 易知nk 1 nk 由于nk 1和nk均为正整数 故由上式q nk 1 nk nk 1 nk nk 令k 得q 矛盾 所以 L不是正则的 17 例5证明L anbkcn k n 0 k 0 不是正则的 证 若L是正则的 则L的任一同态也是正则的 考虑下列同态h h a a