半图厄系统.PPT

现在考虑处理符号串的一种系统，这部分的内容和形式语言理论有密切联系。 每个半图厄（Semi-Thue）系统都定义在某字母表D＝｛a1,a2,…,an｝上。 D上的字是指字母表中符号的有穷序列。 定义6.1.1字母表D上的半图厄处理是下面的产生式集合：?i??i￣ (i=1,2,?,m) 其中?i和?i￣是D上的字，D上所有字的集合记为D*(?i， ?i￣?D*)。 定义6.1.2，设?是半图厄处理，若产生式???￣在?中，则产生式?￣??也定在?中，那么称半图厄处理?为图厄处理。 例如，下面是一个图厄处理 1 ab?aa 2 ba?bb 3 aa?ab 4 bb?ba 例如，当前的字为hS1S2S5q2S2S4h并且在M中没有以q2S2为头的四元组，则下面的推导过程如下： 由上述构造不难证明：对任意post字?，?(M)中最多有一产生式可用于?，于是，?(M)是单演的。 由?(M)产生式的逆组成的半图厄处理称为?(M)。M和?(M)及?(M)之间有下面关系。 6.3半图厄系统和半可计算集合 这一节研究半图厄系统和半可计算集之间的关系。设A是一个字母表，则通过编码可使A上的每个字对应一整数。因此，字母的集合可视为整数集。这样半可计算概念亦可用于字的集合。 给定Turnig机M，则可以构造半图厄处理?(M)和?(M)。下面再定义半图厄处理?(M)： 定义6.3.1 设M为任一图灵机，则用?(M)表示使M停机的所有X的集合。 定义6.3.2 设?=(P，A)为一半图厄系统，则用T(?)表示?的所有定理的集合。 定义6.3.3 用N(?)表示半图厄系统?所产生的x?整数X的集合，即N(?)={x| x??T(?)} ?=(?(M),hq?h),其中X是整数。 于是由前面的定理有X??(M)??T(?) ?X?N(?) 6.4判定问题 定义6.4.1 设给定一个“是/否”判定问题，则定义一特征谓词?，使得?取真值当且仅当问题的回答是“是”，我们称?为特征谓词。 前面几节介绍了一些半可计算理论，这一节将给出一些典型的不可判定问题。 具体研究Turing机(程序，P-T程序)的停机问题、半图厄系统的判定问题和字问题以及正则系统的判定问题和字问题。 (2)Turing机的停机问题II：对已给的Turing机M，判定对输入X ，Turing机M是否停机。(其算法与M有关，但其判定谓词只有一个变元X) (3)半图厄系统的字问题： 对已给的半图厄系统?，判定对任给的两个字?1和?2，是否有 ?1 ?2 (5)正则系统的判定问题：对给定的正则系统?，判定任给的一字?是不是?的定理，即有A ? (A－公理)  (6)post对应问题： 对给定对偶序列 (?1,?1),(?2,?2),?,(?n,?n) 判定是否存在有限序列i1,i2,…,ip使 ?i1?i2…?ip= 其中?ij和?ij是字，p?1,1?j?n,(j=1,?,p)。 定理6.4.1 Turing机的停机问题I是不可判定的。 定理6.4.6 由两个任意的cfg所产生语言是否相交是不可判定的。 * * 半图厄系统 李占山 计算机楼A338 zslizsli@163.com 6.1半图厄系统 例如：产生式集1 ab?aa2 ba?bb3 bb?ab组成一个半图厄处理。 半图厄处理给出了符号串的推导方法。例如对符号串aba 我们有 aba?1aaa aba?2abb?1aab?1aaa aba?2abb?3aab?1aaa 若有串?1,?2,?,?n(n?1)，使得 ?1??2????n 则记为?1?*?n（现在假定此式只对初始字成立） 定义6.1.3　（一半）图厄系统是（一半）图厄处理加上一个字A，A称为这个系统的公理或初始字。 （半）图厄系统可记做?＝（P，A） 其中P是（半）图厄处理，A是公理。由公理A可推出的符号W称之为定理。因为有A?A，因此公理是一个定理。 定义6.1.4　说半图厄系统是单演的，若对系统产生的每个字W最多有一字U使得W?U（当然可以没有一个字U） 一个半图厄系统?＝（P，A）也可能无穷地进行替换，例如 ?= ((a?aa),a) 6.2用半图厄系统模拟图灵机 我们已知四元组形式的图灵机有三种不同类型的四元组指令： 1 qiSjSKql 2 qiSjRql 3 qiSjLql 下面我们来用半图厄系统模拟给定图灵机M。即对给定图灵机M构造和M密切相关的半图厄系统*。 *的字母表是: 1 图灵机M的字母表{S0,S1,…,Sk} 2 图灵机M的状态符{q1,q2,…,qN} 3 再加三个新符{h,q,q?} 设有图灵机M有一状况 S1S2S0S1S2S3 q4  则可把它表示成如下的一个