形式语言与自动机ch3.4-3.6剖析.ppt

* * College of Computer Science Technology, BUPT ?构造G＝（N，T，P，S） 其中N＝N1 U N2，S＝S1， 生成式P为: 若A-αB ∈P1，则它也属于P 若A-α∈P1，则A-αS2∈P P2 ? P 先证 L(G1). L(G2) ? L(G) 若有任意S1 ＝* ω1 与 S2 ＝* ω2 分别属于G1和G2定义的语言中， 那么有 S1 ＝α1A ＝α2B ＝α3C ＝… ＝ ω1 和 S2 ＝ β1A1 ＝ β2B2 ＝ β3C3 ＝… ＝ ω2 ， ∴ S ＝ S1 ＝ α1A ＝α2B ＝α3C ＝… ＝ ω1.S2 ＝ * ω1. ω2 ∴ L(G1). L(G2) ? L(G) (b). 求证L1L2是右线性语言 * * College of Computer Science Technology, BUPT ??再证 L(G) ? L(G1). L(G2) 若有S ＝ S1 ＝ α1A ＝α2B ＝α3C ＝… ＝ ω1.S2 ＝ * ω1. ω2 那么则必然在G1和G2中同时有 S1 ＝α1A ＝α2B ＝α3C ＝… ＝ ω1 和 S2 ＝ β1A1 ＝ β2B2 ＝ β3C3 ＝… ＝ ω2 ∴ L(G) ? L(G1). L(G2) 命题得证＃ (b). 求证L1.L2是右线性语言 * * College of Computer Science Technology, BUPT 证明: 构造G＝（N，T，P，S） 其中； N＝N1 U S， S?N1，S是一个新的非终结符， 生成式P为: 如果A - αB ∈ P1 ，则A - αB∈P。 如果A - α∈ P1 ，则A - αS∈P S-S1，S-ε∈P。 先证 L(G) ? L(G1)* 若有S ＝ S1 ＝ ω1 S ＝ * ω1 ω2 S ＝… ＝* ω1 ω2 …ωi.S ＝ ω1 ω2 …ωi 则在G1中必然有 S1 ＝* ω1 ； S1 ＝* ω2 ； 。。。；S1 ＝* ωi ∴ L(G) ? L(G1)* (c). 求证L1*是右线性语言 * * College of Computer Science Technology, BUPT 再证 L(G1)* ? L(G) 若G1中有 S1 ＝* ω1 ； S1 ＝* ω2 ； 。。。；S1 ＝* ωi 则在G中必然有 S ＝ S1 ＝ ω1 S ＝ * ω1 ω2 S ＝… ＝* ω1 ω2 …ωi.S ＝ ω1 ω2 …ωi ∴ L(G1)* ? L(G) 因此 L* 可以用右线性文法描述。 证毕＃ (c). 求证L1*是右线性语言(续) * * College of Computer Science Technology, BUPT 思路： 由给定的右线性文法可找出正则式，而正则式表示的语言即为正则集。 方法： 对右线性文法构造标准形式的正规表达式方程组， 应用规则x＝αx+β ＝ x＝α*β进行消元， 求解方程组，即可得出正规表达式。 由 (一) 和 (二)即可得出下定理: 定理: 一个语言是正则集，当且仅当该语言为右线性语言。 (二). 证明由右线性文法产生的语言是正则集 * * College of Computer Science Technology, BUPT 课堂练习 Exercise 对于以上自动机，已经求出其语言的一个正规表 达式如下 (0+1)*1(0+1)+(0+1)*1(0+1)(0+1) 使用分配律求出两种不同的更简单的与之等价的表达式. 参考结果 （1）(0+1)*1(?+0+1)(0+1) （2) (0+1)*1(0+1)(?+0+1) * * College of Computer Science Technology, BUPT 课后练习 chap3 习题 习题4，习题15 College of Computer Science Technology, BUPT * * College of Computer Science Technology, BUPT 第四节 有? 转换的NFA 一、定义 概念：当输入空串ε (无输入) 时，也能引起状态的转移。 例： 输入“002”时的转移格局： q0 q1 q2 0 1 2 ε ε * * College of Computer Science Technology