计算机数学基础第八九章.pptVIP

计算机科学的数学基础 第八章 短语结构语言与上下文有关语言  短语结构语言?图灵机 定理8.1：设G 为PSG，则有TM M使L(M) = L(G)。 证明：构造一个两带的不确定TM M识别L(G)。 一条带是输入带，另一条带用来存放G的句型?，最初的?为开始符号S，然后反复地执行： (1) 在?中不确定地选择一个位置i。 (2) 不确定地选择G的一个生成式? ? ?。 (3) 若?出现在?中，以位置i开始，用?替换?。 (4) M把产生的句型与输入相比较。若匹配，则M接受它并停机。若不匹配，则返回步骤(1)。 图灵机?短语结构语言 定理8.2：若L是被TM M接受的语言，则有PSG G，使得L(G) = L。 证明：令M = (Q, ?, ?, ?, B, F)。 构造文法G，对?*中的某个字的表示，G不确定地产生一个二元组序列，在其一个分量上面模拟M的动作。若M接受，则G由另一个分量转换成该字的终极符号串；否则永远不会产生终极符号串。 形式上，设G = (V, ?, P, A1)， 其中，V = ((? ? {?}) ? ?) ? {A1, A2, A3}，P为： 图灵机?短语结构语言 ⑴A1 ? q0A2； ⑵对?a? ?，A2 ? [a, a]A2 ；⑶A2 ? A3 ⑷A3 ? [?, B]A3 ；⑸A3 ? ? ⑹对?a? ??{?}，?q? Q，?X, Y? ?，若?(q, X) = (p, Y, R) ，有q[a, X] ? [a, Y]p； ⑺对?a???{?}，?q?Q，?X, Y, Z?? ，若?(q, X) = (p, Y, L) ，[b, Z]q[a, X] ? p[b, Z][a, Y]。 ⑻对?a???{?}，?q?F，?X??，有q[a, X]?qaq、[a, X]q ? qaq 和q ? ?。 图灵机?短语结构语言 依次使用规则(1)、(2)、(3)、(4)和(5)，有： A1 ?* q0[a1, a1][a2, a2]…[an, an] [?, B]m 上下文有关语言 上下文有关语言(CSL) 是由上下文有关文法(CSG)定义的。 CSG实际上是对PSG的生成式? ? ?加上一个限制，|?| ? |?|。 CSG在推导的过程中句型的长度是一个递增的序列。换句话说，如果w是CSG推导出来的句子，则|w|是其推导过程中句型的最大长度。 识别CSL的机器是线性有界自动机(LBA)。 线性有界自动机 一个LBA是满足下列条件的不确定的TM： (1)?有两个分别为左、右端标志的特殊符号￠和$。 (2)LBA从左端符号￠往左无动作，从右端符号$往右也无动作，且不允许在￠和$上面写任何符号。 LBA是这样一种TM，它没有无穷的计算带，而是被限制在带上含有左右端标志的的这一部分。 这个限制和限制TM的带单元数量以其输入长度的某一线性函数为界，所产生的计算能力一样，因而被称为“线性有界自动机”。 线性有界自动机 形式上，一个LBA M为 M = (Q, ?, ?, ?, q0, ￠, $, F)， 其中，Q、?、?、?、q0和F与非确定TM中的一样，￠和$在?中，分别表示左端和右端的标志。 M所接受的语言，L(M)，为 {w|w?(?–{￠, $})*??q?F: q0￠w$├*M?q?, ?, ???*} 注意￠和$不被看成为被接受或者被排斥的字的一部分。因为LBA不可能离开输入，所以没有必要有空白符号。 CSL ? LBA 定理8.3：如果L是一个CSL，则L被某个LBA M接受。 证明：和定理8.1的证明几乎是一样的。 M开始时将￠w$写在带上并在w的最左符号的第二道上写上开始符号S。 然后，M反复地猜测一个生成式和写在第二道上的句型中的一个位置，应用该生成式产生句型?。 若w ≠ ?，则M不停机也不接受。若w = ?，则M停机且接受。若|?| |w|，M则停机但不接受。 因在CSG中不可能有一个派生S ?* ? ?* w，其中|?| |w| 。所以，L(M) = L。 LBA ?CSL 定理8.4：对某个LBA M = (Q, ?, ?, ?, q0, ￠, $, F)，L = L(M)，则L – {?}是一个CSL。 证明：这个证明平行于定理8.2中从图灵机到短语结构文法的构造。不同的地方是在LBA的带上的左右端标志必须合并到相邻的带符号中去，而状态也必须相类似地合并到带磁头所扫描的符号中去。以保证所有规则式的右部长度不小于左部长度。 CSL是递归集 定理 8.5：若L为CSL，则L为递归集合。 证明 因为L为CSL，根据定理8.3，必有线性有界自动机M = (Q, ?, ?, ?, q0, ￠, $, F)，使L = L(M)。 设s = |Q|，t =