如何做好网站建设内容的策划,漳州 做网站,wordpress页面查询数据,科研实验室网站建设文章目录 一、正则语言预备知识确定性有穷自动机#xff08;DFA#xff09;设计DFA正则运算 非确定性有穷自动机#xff08;NFA#xff0c;含有 ε \varepsilon ε#xff0c;下一个状态可以有若干种选择#xff08;包括0种#xff09;#xff09;正则表达式定义计算优… 文章目录 一、正则语言预备知识确定性有穷自动机DFA设计DFA正则运算 非确定性有穷自动机NFA含有 ε \varepsilon ε下一个状态可以有若干种选择包括0种正则表达式定义计算优先级定理 GNFA广义非确定自动机,NFA的推广CONVERT(G)过程函数转化方法 泵引理一个正则语言一定存在泵长度 二、上下文无关文法CFGCFG生成合并正则语言生成 语法分析树文法歧义性乔姆斯基范式(CNF)生成CNF 下推自动机PDA通常指的是非确定性下推自动机上下文无关语言CFLCFL的泵引理一个CFL必定有泵 三、图灵机单带图灵机TM图灵机的等价变形多带图灵机同时多个纸带非确定性图灵机NTM 图灵机算法递归定理图灵机接受性问题图灵机极小性问题不动点(xf(x)) 四、可计算问题/不可计算问题对于正则语言的可判定问题关于上下文无关语言CFL的可判定问题不可计算问题用对角化方法证明不可计算问题非图灵可识别语言归约法 一、正则语言
预备知识
字母表任意非空有穷集合 字符串用字母表中的字母组成的序列比如 Σ { 0 , 1 } , x 01001 \Sigma\{0,1\},x01001 Σ{0,1},x01001 连接首尾连接如 x 01001 , w a b c d e , x w 01001 a b c d e x01001,wabcde,xw01001abcde x01001,wabcde,xw01001abcde 特别地 x . . . x x n x...xx^n x...xxn表示n个x首尾连接 串长度 x 01001 , ∣ x ∣ 5 x01001,|x|5 x01001,∣x∣5 空串 ε , ∣ ε ∣ 0 , x 0 ε \varepsilon,|\varepsilon|0,x^0\varepsilon ε,∣ε∣0,x0ε。 空串 ≠ \neq 空格 子串子序列略 串的标准序并非字典序而是先比较长度再逐位比较大小 语言由字符串组成的集合,令字母表为 Σ \Sigma Σ里面的串要根据标准序排列 Σ ∗ \Sigma^* Σ∗ Σ \Sigma Σ上有穷长度的串包括 ε \varepsilon ε Σ \Sigma^ Σ Σ \Sigma Σ上正有穷长度的串不包括 ε \varepsilon ε Σ ’ \Sigma^’ Σ’ Σ \Sigma Σ上无穷长度的串 Φ \varPhi Φ:空语言 与空串语言 { ε } \{\varepsilon\} {ε}不同空串语言 { ε } \{\varepsilon\} {ε}也与空串 ε \varepsilon ε不同 语言连接类似于笛卡尔积两两搭配。 A B { x y ∣ x ∈ a , y ∈ b } AB\{xy|x\in a,y\in b\} AB{xy∣x∈a,y∈b} 特殊地 { ε } A A { ε } A \{\varepsilon\}AA\{\varepsilon\}A {ε}AA{ε}A, Φ A A Φ Φ \varPhi AA\varPhi \varPhi ΦAAΦΦ
确定性有穷自动机DFA M ( Q , Σ , δ , q 0 , F ) M(Q,\Sigma,\delta,q_0,F) M(Q,Σ,δ,q0,F) Q Q Q有穷状态集 Σ \Sigma Σ输入字母表 δ : Q × Σ → Q \delta:Q \times \Sigma \rightarrow Q δ:Q×Σ→Q转移函数也就是映射关系 特殊地 Q × Σ ∗ → Q Q \times \Sigma^* \rightarrow Q Q×Σ∗→Q多了个空串为扩展转移函数 q 0 q_0 q0初始状态 F F F接受状态/终止状态 语言能够被自动机接受的串集合 L ( M ) { w ∈ Σ ∗ ∣ δ ( q 0 , w ) ∈ F } L(M)\{w\in \Sigma^*|\delta(q_0,w)\in F\} L(M){w∈Σ∗∣δ(q0,w)∈F} 正则语言可以被有穷自动机接受的语言/可以用正则表达式描述的语言
设计DFA
确定状态集确定转移函数标注初始状态终结状态
正则运算
正则语言对正则计算封闭 正则语言的**交并补、差、对称差、连接、*星号**封闭 A ∪ B { x ∣ x ∈ A 或 x ∈ B } A\cup B\{x|x\in A或x\in B\} A∪B{x∣x∈A或x∈B} A B { x y ∣ x ∈ A 且 y ∈ B } AB\{xy|x\in A且y\in B\} AB{xy∣x∈A且y∈B} A ∗ A 0 ∪ A 1 ∪ A 2 ∪ . . . A^*A^0\cup A^1\cup A^2\cup... A∗A0∪A1∪A2∪...见前包括 ε \varepsilon ε
非确定性有穷自动机NFA含有 ε \varepsilon ε下一个状态可以有若干种选择包括0种
筹码集字符集中只有 ε \varepsilon ε与一种字符的语言 M ( Q , Σ ε , δ , q 0 , F ) M(Q,\Sigma_{\varepsilon},\delta,q_0,F) M(Q,Σε,δ,q0,F) Q Q Q有穷状态集 Σ \Sigma Σ输入字母表 Σ ε Σ ∪ { ε } \Sigma_{\varepsilon}\Sigma\cup\{\varepsilon\} ΣεΣ∪{ε} δ : Q × Σ ε → P ( Q ) \delta:Q \times \Sigma_{\varepsilon} \rightarrow P(Q) δ:Q×Σε→P(Q)转移函数 q 0 q_0 q0初始状态 F F F接受状态/终止状态
任何一个NFA都有等价的DFA 一个语言是正则语言当且仅当只有一个NFA可以识别 具体转换见其他
正则表达式
定义
对于 R R R有 a a a表示语言 { a } \{a\} {a}其中 a ∈ Σ a\in\Sigma a∈Σ包括 ε \varepsilon ε Φ \varPhi Φ表示空语言 R ( R 1 ∪ R 2 ) R(R_1\cup R_2) R(R1∪R2)是正则表达式 R ( R 1 ∘ R 2 ) R(R_1\circ R_2) R(R1∘R2)是正则表达式 R ( R 1 ∗ ) R(R_1^*) R(R1∗)是正则表达式
则 R R R是正则表达式
eg:数值常量 { , − , ε } ( D D ∗ ∪ D D ∗ . D ∗ ∪ D ∗ . D D ∗ ) , D { 0 , 1 , 2 , . . . , 9 } \{,-,\varepsilon\}(DD^*\cup DD^*.D^*\cup D^*.DD^*),D\{0,1,2,...,9\} {,−,ε}(DD∗∪DD∗.D∗∪D∗.DD∗),D{0,1,2,...,9} eg:72、3.14159、7.、-.01
计算优先级
星号 ∗ * ∗连接 并 ∪ \cup ∪
定理 Φ ∗ { ε } \varPhi^*\{\varepsilon\} Φ∗{ε} R ∪ Φ R R\cup\varPhiR R∪ΦR R ε R R\varepsilonR RεR R ∪ ε R ∪ { ε } ≠ R R\cup \varepsilonR\cup \{\varepsilon\}\neq R R∪εR∪{ε}R R Φ Φ ≠ R R\varPhi\varPhi\neq R RΦΦR
正则表达式与一个确定自动机等价
GNFA广义非确定自动机,NFA的推广
与NFA不同的是转移用的并非是单个字符而是一个正则表达式 G ( Q , Σ , δ , q s t a r t , q a c c e p t ) G(Q,\Sigma,\delta,q_{start},q_{accept}) G(Q,Σ,δ,qstart,qaccept) Q Q Q有穷状态集 Σ \Sigma Σ输入字母表 Σ ε Σ ∪ { ε } \Sigma_{\varepsilon}\Sigma\cup\{\varepsilon\} ΣεΣ∪{ε} δ : ( Q − { q a c c e p t } ) × ( Q − { q s t a r t } ) → R \delta:(Q-\{q_{accept}\}) \times (Q-\{q_{start}\}) \rightarrow R δ:(Q−{qaccept})×(Q−{qstart})→R 与NFA不同的是转移状态用的并非是单个字符而是一个正则表达式 q s t a r t q_{start} qstart初始状态 q a c c e p t q_{accept} qaccept接受状态/终止状态
CONVERT(G)过程函数
对于任意GNFA G C O N V E R T ( G ) CONVERT(G) CONVERT(G)与 G G G等价 对于 G G G的状态数 k k k k 2 k2 k2时 C O N V E R T ( G ) δ ( q s t a r t , q a c c e p t ) CONVERT(G)\delta(q_{start},q_{accept}) CONVERT(G)δ(qstart,qaccept)。 当 k 2 k2 k2时令 q r i p ∈ Q − { q s t a r t } − { q a c c e p t } , Q ′ Q − q r i p q_{rip}\in Q-\{q_{start}\}-\{q_{accept}\},QQ-{q_{rip}} qrip∈Q−{qstart}−{qaccept},Q′Q−qrip。 构造 G ′ ( Q ′ , Σ ε , δ ′ , q s t a r t , q a c c e p t ) G(Q,\Sigma_{\varepsilon},\delta,q_{start},q_{accept}) G′(Q′,Σε,δ′,qstart,qaccept)如此循环直到 k 2 k2 k2。 其中对于每个非起始态 q i q_i qi与每个非终结态 q j q_j qj δ ′ ( q i , q j ) ( R 1 ) ( R 2 ) ∗ ( R 3 ) ∪ ( R 4 ) \delta(q_i,q_j)(R_1)(R_2)*(R_3)\cup(R_4) δ′(qi,qj)(R1)(R2)∗(R3)∪(R4) 其中 R 1 δ ( q i , q r i p ) , R 2 δ ( q r i p , q r i p ) , R 3 δ ( q r i p , q j ) , R 4 δ ( q i , q j ) R_1\delta(q_i,q_{rip}),R_2\delta(q_{rip},q_{rip}),R_3\delta(q_{rip},q_{j}),R_4\delta(q_i,q_j) R1δ(qi,qrip),R2δ(qrip,qrip),R3δ(qrip,qj),R4δ(qi,qj) 选择 i → j i\rightarrow j i→j和 i → ( r i p ) ∗ → j i\rightarrow (rip)^*\rightarrow j i→(rip)∗→j的并集来转移状态不断递归
转化方法
增加新的起始点与终结点并将其与原来的起始点/终结点用 ε \varepsilon ε连接 类似最大流的源点与汇点使得起始点没有入度终结点没有出度合并平行边 去除中心点使得点减少更精简 以下图为例。 1.添加新起始点s与新终结点a用 ε \varepsilon ε连接。 2.将状态2去消除中心点变为 b ( a ∪ b ) ∗ b(a\cup b)^* b(a∪b)∗后删除状态2 3.将状态1去消除中心点变为 a ∗ b ( a ∪ b ) ∗ a^*b(a\cup b)^* a∗b(a∪b)∗结束。 合并的时候如果有不含 ε \varepsilon ε的部分则消去所有 ε \varepsilon ε否则不消去 以下图为例。 1.添加新起始点s与新终结点a用 ε \varepsilon ε连接。 2.将状态1去消除中心点。 消除路径经过1的、且不是回路的 1把 2 → a 1 → b 3 2\xrightarrow{a}1\xrightarrow{b}3 2a 1b 3变为 2 → a b 3 2\xrightarrow{ab}3 2ab 3 2把 3 → b 1 → a 2 3\xrightarrow{b}1\xrightarrow{a}2 3b 1a 2与 3 → a 2 3\xrightarrow{a}2 3a 2变为 3 → b a ∪ a 2 3\xrightarrow {ba\cup a}2 3ba∪a 2 消除新起始点/新终结点相关的 3把 s → ε 1 → a 2 s\xrightarrow{\varepsilon}1\xrightarrow{a}2 sε 1a 2变为 s → a 2 s\xrightarrow{a}2 sa 2 4把 s → ε 1 → b 3 s\xrightarrow{\varepsilon}1\xrightarrow{b}3 sε 1b 3变为 s → b 3 s\xrightarrow{b}3 sb 3 消除路径经过1的、且是回路的 5把 2 → a 1 → a 2 2\xrightarrow{a}1\xrightarrow{a}2 2a 1a 2与 2 → b 2 2\xrightarrow{b}2 2b 2变为 2 → a a ∪ b 2 2\xrightarrow {aa\cup b}2 2aa∪b 2 6把 3 → b 1 → b 3 3\xrightarrow{b}1\xrightarrow{b}3 3b 1b 3变为 3 → b b 3 3\xrightarrow{bb}3 3bb 3 3.将状态2去消除中心点。 1将 s → a 2 → ε a s\xrightarrow{a}2\xrightarrow{\varepsilon}a sa 2ε a与 2 → a a ∪ b 2 2\xrightarrow{aa\cup b}2 2aa∪b 2变为 s → a ( a a ∪ b ) ∗ a s\xrightarrow{a(aa\cup b)^*}a sa(aa∪b)∗ a 2将 s → b 3 s\xrightarrow{b}3 sb 3与 s → a 2 → a a ∪ b 2 → a b 3 s\xrightarrow{a}2\xrightarrow{aa\cup b}2\xrightarrow{ab}3 sa 2aa∪b 2ab 3变为 s → a ( a a ∪ b ) ∗ a b ∪ b 3 s\xrightarrow{a(aa\cup b)^*ab\cup b}3 sa(aa∪b)∗ab∪b 3 因为 3 → ε a 3\xrightarrow{\varepsilon}a 3ε a所以状态3也是终结状态 3将 3 → b b 3 3\xrightarrow{bb}3 3bb 3与 3 → b a ∪ a 2 → a a ∪ b 2 → a b 3 3\xrightarrow{ba\cup a}2\xrightarrow{aa\cup b}2\xrightarrow{ab}3 3ba∪a 2aa∪b 2ab 3变为 3 → ( b a ∪ a ) ( a a ∪ b ) ∗ a b ∪ b b 3 3\xrightarrow{(ba\cup a)(aa\cup b)^*ab\cup bb}3 3(ba∪a)(aa∪b)∗ab∪bb 3 4将 3 → ε a 3\xrightarrow{\varepsilon}a 3ε a与 3 → b a ∪ a 2 → a a ∪ b 2 → ε a 3\xrightarrow{ba\cup a}2\xrightarrow{aa\cup b}2\xrightarrow{\varepsilon}a 3ba∪a 2aa∪b 2ε a变为 3 → b a ∪ a ( a a ∪ b ) ∗ ∪ ε a 3\xrightarrow{ba\cup a(aa\cup b)^*\cup\varepsilon}a 3ba∪a(aa∪b)∗∪ε a 4.将状态3去消除中心点。 将 s → a ( a a ∪ b ) ∗ a b ∪ b 3 s\xrightarrow{a(aa\cup b)^*ab\cup b}3 sa(aa∪b)∗ab∪b 3、 3 → ( b a ∪ a ) ( a a ∪ b ) ∗ a b ∪ b b 3 3\xrightarrow{(ba\cup a)(aa\cup b)^*ab\cup bb}3 3(ba∪a)(aa∪b)∗ab∪bb 3、 3 → b a ∪ a ( a a ∪ b ) ∗ ∪ ε a 3\xrightarrow{ba\cup a(aa\cup b)^*\cup\varepsilon}a 3ba∪a(aa∪b)∗∪ε a 与 s → a ( a a ∪ b ) ∗ a s\xrightarrow{a(aa\cup b)^*}a sa(aa∪b)∗ a变为 s → ( a ( a a ∪ b ) ∗ a b ∪ b ) ( ( b a ∪ a ) ( a a ∪ b ) ∗ a b ∪ b b ) ∗ ( b a ∪ a ( a a ∪ b ) ∗ ∪ ε ) ∪ ( a ( a a ∪ b ) ∗ ) a s\xrightarrow{(a(aa\cup b)^*ab\cup b)((ba\cup a)(aa\cup b)^*ab\cup bb)^*(ba\cup a(aa\cup b)^*\cup\varepsilon)\cup(a(aa\cup b)^*)}a s(a(aa∪b)∗ab∪b)((ba∪a)(aa∪b)∗ab∪bb)∗(ba∪a(aa∪b)∗∪ε)∪(a(aa∪b)∗) a
泵引理一个正则语言一定存在泵长度
若 A A A是正则语言则存在常数 p p p p p p为泵长度类似最大循环节长度若 s ∈ A s\in A s∈A ∣ s ∣ ≥ p |s|\geq p ∣s∣≥p 则 s x y z sxyz sxyz并且满足 1 ∀ i ≥ 0 x y i z ∈ A \forall i\geq0xy^iz\in A ∀i≥0xyiz∈A。 2 ∣ y ∣ 0 |y|0 ∣y∣0 3 ∣ x y ∣ ≤ p |xy|\leq p ∣xy∣≤p 如果要证明一个语言不是正则的则用反证法 。找一个反例即可。 二、上下文无关文法CFG G ( V , Σ , R , S ) G(V,\Sigma,R,S) G(V,Σ,R,S) V V V有穷变元集 Σ \Sigma Σ有穷终结符集 R R R有穷规则集形如 A → w , w ∈ ( V ∪ Σ ) ∗ A\rightarrow w,w\in(V\cup\Sigma)^* A→w,w∈(V∪Σ)∗ S ∈ V S\in V S∈V初始变元 一个上下文无关语言(CFL)与上下文无关文法等价
CFG生成
合并
对于原本的初始变元 S 1 , S 2 , . . . S k S_1,S_2,...S_k S1,S2,...Sk新增规则 S → S 1 ∣ S 2 ∣ . . . S k S\rightarrow S_1|S_2|...S_k S→S1∣S2∣...Sk
正则语言生成
用DFA转化为等价的CFG正则语言都是上下文无关语言 对于原DFA中 δ ( q i , a ) q j \delta(q_i,a)q_j δ(qi,a)qj即 q i → a q j q_i\xrightarrow{a}q_j qia qj则令 R i → a R j R_i\rightarrow aR_j Ri→aRj 对于原DFA中 q i ∈ F q_i\in F qi∈F即 q i q_i qi为终止状态则令 R i → ε R_i\rightarrow \varepsilon Ri→ε
语法分析树 文法歧义性
最左派生每一步都优先替换最左边的变元 eg1: E X P R EXPR EXPR ⇒ E X P R E X P R \Rightarrow EXPREXPR ⇒EXPREXPR ⇒ a E X P R \Rightarrow aEXPR ⇒aEXPR ⇒ a E X P R × E X P R \Rightarrow aEXPR\timesEXPR ⇒aEXPR×EXPR ⇒ a a × E X P R \Rightarrow aa\timesEXPR ⇒aa×EXPR ⇒ a a × a \Rightarrow aa\times a ⇒aa×a eg2: E X P R EXPR EXPR ⇒ E X P R × E X P R \Rightarrow EXPR\timesEXPR ⇒EXPR×EXPR ⇒ E X P R E X P R × E X P R \Rightarrow EXPREXPR\timesEXPR ⇒EXPREXPR×EXPR ⇒ a E X P R × E X P R \Rightarrow aEXPR\timesEXPR ⇒aEXPR×EXPR ⇒ a a × E X P R \Rightarrow aa\timesEXPR ⇒aa×EXPR ⇒ a a × a \Rightarrow aa\times a ⇒aa×a 注意到最左派生产生歧义性因此这是歧义文法。
乔姆斯基范式(CNF)
初始变元不能在式子右方出现 只允许如下形式规则 S → ε S\rightarrow \varepsilon S→ε A → B C A\rightarrow BC A→BC A → a A\rightarrow a A→a任意终结符
生成CNF
任何的CFG都有等价的CNF
添加新初始变元 S 0 S_0 S0与新规则 S 0 → S S_0\rightarrow S S0→S旧初始变元处理所有的 ε \varepsilon ε规则 若有非初始变元 A → ε A\rightarrow\varepsilon A→ε则删除之并修改所有等式右边与 A A A相关的内容。 B → u A v B\rightarrow uAv B→uAv变为 B → u v B\rightarrow uv B→uv。 B → u A v A w B\rightarrow uAvAw B→uAvAw变为 B → u v A w ∣ u A v w ∣ u v w B\rightarrow uvAw|uAvw|uvw B→uvAw∣uAvw∣uvw三种不同的可能情况 B → A B\rightarrow A B→A变为 B → ε B\rightarrow\varepsilon B→ε。 重复以上知道删除所有 ε \varepsilon ε相关规则为止 S 0 → ε S_0\rightarrow\varepsilon S0→ε除外处理所有的单一规则左边单个对应右边单个 删除 A → B A\rightarrow B A→B并修改所有相关的内容。 若有 B → u B\rightarrow u B→u则添加 A → u A\rightarrow u A→u。 重复以上直到删除所有单一规则为止。处理 A → u 1 u 2 . . . u k A\rightarrow u_1u_2...u_k A→u1u2...uk长规则 将其换成 A → u 1 A 1 , A 1 → u 2 A 2 , . . . . . . , A k u k − 1 u k A\rightarrow u_1A_1,A_1\rightarrow u_2A_2,......,A_{k}u_{k-1}u_k A→u1A1,A1→u2A2,......,Akuk−1uk。处理终结符 引入新变元 U i U_i Ui与新规则 U i → a i U_i\rightarrow a_i Ui→ai。 A → a i a j A\rightarrow a_ia_j A→aiaj换成 A → U i U j A\rightarrow U_iU_j A→UiUj A → a i B A\rightarrow a_iB A→aiB换成 A → U i B A\rightarrow U_iB A→UiB A → B a i A\rightarrow Ba_i A→Bai换成 A → B u i A\rightarrow Bu_i A→Bui G : S → A S A ∣ a B G:S\rightarrow ASA|aB G:S→ASA∣aB A → B ∣ S A\rightarrow B|S A→B∣S B → b ∣ ε B\rightarrow b|\varepsilon B→b∣ε 求等价CNF。 1添加新初始变元 S 0 S_0 S0 S 0 → S S_0\rightarrow S S0→S S → A S A ∣ a B S\rightarrow ASA|aB S→ASA∣aB A → B ∣ S A\rightarrow B|S A→B∣S B → b ∣ ε B\rightarrow b|\varepsilon B→b∣ε 2处理B的 ε \varepsilon ε规则 S 0 → S S_0\rightarrow S S0→S S → A S A ∣ a B ∣ a S\rightarrow ASA|aB|a S→ASA∣aB∣a A → B ∣ S ∣ ε A\rightarrow B|S|\varepsilon A→B∣S∣ε B → b B\rightarrow b B→b 3处理A的 ε \varepsilon ε规则 S 0 → S S_0\rightarrow S S0→S S → A S A ∣ a B ∣ a ∣ S A ∣ A S S\rightarrow ASA|aB|a|SA|AS S→ASA∣aB∣a∣SA∣AS S → S S\rightarrow S S→S没有用可以删去 A → B ∣ S A\rightarrow B|S A→B∣S B → b B\rightarrow b B→b 4处理单一规则 S 0 → S S_0\rightarrow S S0→S S 0 → A S A ∣ a B ∣ a ∣ S A ∣ A S S_0\rightarrow ASA|aB|a|SA|AS S0→ASA∣aB∣a∣SA∣AS S → A S A ∣ a B ∣ a ∣ S A ∣ A S S\rightarrow ASA|aB|a|SA|AS S→ASA∣aB∣a∣SA∣AS A → B ∣ S A\rightarrow B|S A→B∣S B → b B\rightarrow b B→b 5处理单一规则 A → B A\rightarrow B A→B S 0 → A S A ∣ a B ∣ a ∣ S A ∣ A S S_0\rightarrow ASA|aB|a|SA|AS S0→ASA∣aB∣a∣SA∣AS S → A S A ∣ a B ∣ a ∣ S A ∣ A S S\rightarrow ASA|aB|a|SA|AS S→ASA∣aB∣a∣SA∣AS A → S ∣ b A\rightarrow S|b A→S∣b B → b B\rightarrow b B→b 6处理单一规则 A → S A\rightarrow S A→S S 0 → A S A ∣ a B ∣ a ∣ S A ∣ A S S_0\rightarrow ASA|aB|a|SA|AS S0→ASA∣aB∣a∣SA∣AS S → A S A ∣ a B ∣ a ∣ S A ∣ A S S\rightarrow ASA|aB|a|SA|AS S→ASA∣aB∣a∣SA∣AS A → A S A ∣ a B ∣ S A ∣ A S ∣ a ∣ b A\rightarrow ASA|aB|SA|AS|a|b A→ASA∣aB∣SA∣AS∣a∣b B → b B\rightarrow b B→b 7处理长规则 A S A ASA ASA S 0 → A A 1 ∣ a B ∣ a ∣ S A ∣ A S S_0\rightarrow AA_1|aB|a|SA|AS S0→AA1∣aB∣a∣SA∣AS S → A A 1 ∣ a B ∣ a ∣ S A ∣ A S S\rightarrow AA_1|aB|a|SA|AS S→AA1∣aB∣a∣SA∣AS A → A A 1 ∣ a B ∣ S A ∣ A S ∣ a ∣ b A\rightarrow AA_1|aB|SA|AS|a|b A→AA1∣aB∣SA∣AS∣a∣b B → b B\rightarrow b B→b A 1 → S A A_1\rightarrow SA A1→SA 8处理终结符 a a a S 0 → A A 1 ∣ U B ∣ U ∣ S A ∣ A S S_0\rightarrow AA_1|UB|U|SA|AS S0→AA1∣UB∣U∣SA∣AS S → A A 1 ∣ U B ∣ U ∣ S A ∣ A S S\rightarrow AA_1|UB|U|SA|AS S→AA1∣UB∣U∣SA∣AS A → A A 1 ∣ U B ∣ S A ∣ A S ∣ U ∣ B A\rightarrow AA_1|UB|SA|AS|U|B A→AA1∣UB∣SA∣AS∣U∣B A 1 → S A A_1\rightarrow SA A1→SA B → b B\rightarrow b B→b U → a U\rightarrow a U→a 于是得到 G G G对应的乔姆斯基范式。
下推自动机PDA通常指的是非确定性下推自动机
由栈组成每次读入字符后选择与栈顶字符匹配或压入栈。 M ( Q , Σ , Γ , δ , q 0 , F ) M(Q,\Sigma,\Gamma,\delta,q_0,F) M(Q,Σ,Γ,δ,q0,F) Q Q Q有穷状态集 Σ \Sigma Σ输入字母表 Σ ε Σ ∪ { ε } \Sigma_\varepsilon\Sigma\cup\{\varepsilon\} ΣεΣ∪{ε} Γ \Gamma Γ栈字母表 Γ ε Γ ∪ { ε } \Gamma_\varepsilon\Gamma\cup\{\varepsilon\} ΓεΓ∪{ε} δ : Q × Σ ε × Γ ε → P ( Q × Γ ε ) \delta:Q\times\Sigma_{\varepsilon}\times\Gamma_{\varepsilon}\rightarrow P(Q\times\Gamma_{\varepsilon}) δ:Q×Σε×Γε→P(Q×Γε)转移函数 q 0 q_0 q0初始状态 q 0 ∈ Q q_0 \in Q q0∈Q F F F终结状态集 F ⊆ Q F\subseteq Q F⊆Q 以此图为例可以绘制出此自动机。 在栈的初始插入一个 $符号用于判断是否为空栈。
上下文无关语言CFL
如果一个语言是上下文无关语言CFL ⟺ \Longleftrightarrow ⟺有下推自动机PDA识别这个语言。 CFL对正则运算封闭 CFL对交 ∩ \cap ∩不封闭语言 A , B A,B A,B是CFL A ∩ B A\cap B A∩B不一定是CFL CFL对补运算不封闭语言 A A A是CFL A c A^c Ac不一定是CFL
CFL的泵引理一个CFL必定有泵
假设 A A A为上下文无关语言则存在常数 p p p泵长度类似循环节最大长度若 s ∈ A s\in A s∈A且 ∣ s ∣ ≥ p |s|\geq p ∣s∣≥p 则 s u v x y z suvxyz suvxyz其中 1 ∀ i ≥ 0 , u v i x y i z ∈ A \forall i\geq 0,uv^ixy^iz\in A ∀i≥0,uvixyiz∈A 2 ∣ v y ∣ 0 |vy|0 ∣vy∣0 3 ∣ v x y ∣ ≤ p |vxy|\leq p ∣vxy∣≤p
同正则文法一样找出一个反例证明不是CFL即可
eg1证明 C { a i b j c k ∣ 0 ≤ i ≤ j ≤ k } C\{a^ib^jc^k|0\leq i\leq j\leq k\} C{aibjck∣0≤i≤j≤k}不是CFL。 prove假设 C C C为上下文无关语言设 p p p为泵长度不妨令 s a p b p c p sa^pb^pc^p sapbpcp。 则 s u v x y z suvxyz suvxyz其中 1 ∀ i ≥ 0 , u v i x y i z ∈ C \forall i\geq 0,uv^ixy^iz\in C ∀i≥0,uvixyiz∈C 2 ∣ v y ∣ 0 |vy|0 ∣vy∣0即 v v v与 y y y至少含一种符号 3 ∣ v x y ∣ ≤ p |vxy|\leq p ∣vxy∣≤p即 v v v与 y y y至多含两种符号理由同上
1 v v v与 y y y仅含一种符号 ① a a a不在 v v v与 y y y之中此时只可能是 a . . . a ⏟ p 个 ∣ ∅ ∣ b . . . b ⏟ p 个 ∣ ∅ ∣ c . . . c ⏟ p 个 \underbrace{a...a}_{p个}|\emptyset|\underbrace{b...b}_{p个}|\emptyset|\underbrace{c...c}_{p个} p个 a...a∣∅∣p个 b...b∣∅∣p个 c...c违背了 ∣ v y ∣ 0 |vy|0 ∣vy∣0矛盾。 ② b b b不在 v v v与 y y y之中此时只可能是 a . . . a ⏟ p − i 个 ∣ a . . . a ⏟ i 个 ∣ b . . . b ⏟ p 个 ∣ c . . . c ⏟ i 个 ∣ c . . . c ⏟ p − i 个 \underbrace{a...a}_{p-i个}|\underbrace{a...a}_{i个}|\underbrace{b...b}_{p个}|\underbrace{c...c}_{i个}|\underbrace{c...c}_{p-i个} p−i个 a...a∣i个 a...a∣p个 b...b∣i个 c...c∣p−i个 c...c违背了 ∣ v x y ∣ ≤ q |vxy|\leq q ∣vxy∣≤q矛盾。 ③ c c c不在 v v v与 y y y之中同①矛盾。 2 v v v与 y y y含两种符号 此时易知当 i 1 i1 i1时就不具有 a p b p c p a^pb^pc^p apbpcp的形式即 i 0 i0 i0或 i 1 i1 i1矛盾。 ∀ i ≥ 0 \forall i\geq 0 ∀i≥0才算成立 综上 C C C不是CFL证毕。
eg2证明 D { w w ∣ w ∈ { 0 , 1 } ∗ } D\{ww|w\in\{0,1\}^*\} D{ww∣w∈{0,1}∗}不是CFL。 prove假设 C C C为上下文无关语言设 p p p为泵长度不妨令 s 0 p 1 p 0 p 1 p s0^p1^p0^p1^p s0p1p0p1p。 则 s u v x y z suvxyz suvxyz其中 1 ∀ i ≥ 0 , u v i x y i z ∈ C \forall i\geq 0,uv^ixy^iz\in C ∀i≥0,uvixyiz∈C 2 ∣ v y ∣ 0 |vy|0 ∣vy∣0即 v v v与 y y y至少含一种符号 3 ∣ v x y ∣ ≤ p |vxy|\leq p ∣vxy∣≤p即 v v v与 y y y至多含两种符号 注意这里一定要挑一个合适的反例例如 0 p 1 0 p 1 0^p10^p1 0p10p1可以拆分为 0...0 ⏟ p − 1 个 ∣ 0 ∣ 1 ∣ 0 ∣ 0...0 ⏟ p − 1 个 1 \underbrace{0...0}_{p-1个}|0|1|0|\underbrace{0...0}_{p-1个}1 p−1个 0...0∣0∣1∣0∣p−1个 0...01是合法的。
1 v x y vxy vxy在前半部分里即 v x y vxy vxy在第一个 0 p 1 p 0^p1^p 0p1p内。此时随着 i i i的变化后半个 0 p 1 p 0^p1^p 0p1p的数量会与前半个不同不匹配矛盾。 2 v x y vxy vxy在后半部分里同上矛盾。 3 v x y vxy vxy横跨中间则 v v v与 y y y不可以含两种符号故 v v v为 1 i 1^i 1i y y y为 1 i 1^i 1i同理 i i i的变化会让头尾的两个 0 p 0^p 0p与 1 p 1^p 1p数量与内部的两个不同不匹配矛盾。 综上 D D D不是CFL证毕。
三、图灵机
单带图灵机TM
有一个纸带序列与一个可以左右双向移动的读写头 M ( Q , Σ , Γ , δ , q 0 , q a c c , q r e j ) M(Q,\Sigma,\Gamma,\delta,q_0,q_{acc},q_{rej}) M(Q,Σ,Γ,δ,q0,qacc,qrej) Q Q Q有穷状态集 Σ \Sigma Σ输入字母表注意空格符 B ∉ Σ B\notin\Sigma B∈/Σ Γ \Gamma Γ带字母表 Σ ∪ { B } ⊆ Γ \Sigma\cup\{B\}\subseteq\Gamma Σ∪{B}⊆Γ δ \delta δ Q × Γ → Q × Γ × { L , R } Q\times\Gamma\rightarrow Q\times\Gamma\times\{L,R\} Q×Γ→Q×Γ×{L,R}转移函数L/R表示左移/右移 q 0 ∈ Q q_0\in Q q0∈Q初始状态 q a c c ∈ Q q_{acc}\in Q qacc∈Q停机接受状态 q r e q ∈ Q q_{req}\in Q qreq∈Q停机拒绝状态 q a c c ≠ q r e j q_{acc}\neq q_{rej} qaccqrej 单带图灵机的格局序列的当前状态 u q a v uqav uqav q q q当前状态 u a v uav uav当前带上的内容 a a a当前的扫描符号 即之前的序列 u u u|当前的状态 q q q|当前的扫描符号 a a a|后面的序列 v v v eg:对于带 101101111 101101111 101101111,状态 q 7 q_7 q7正在扫描第五个字符 0 0 0其格局为 1011 q 7 01111 1011q_701111 1011q701111 初始格局 q 0 w q_0w q0ww为输入串 接受格局 u q a c c a v uq_{acc}av uqaccav 拒绝格局 u q r e j a v uq_{rej}av uqrejav 停机格局 u q a c c a v / u q r e j a v uq_{acc}av/uq_{rej}av uqaccav/uqrejav 图灵机的计算结果只能是停机接受、停机拒绝、不停机 若 δ ( q i , b ) ( q j , c , L ) \delta(q_i,b)(q_j,c,L) δ(qi,b)(qj,c,L)L表示左移则 u a q i b v uaq_ibv uaqibv产生 u q j a c v uq_jacv uqjacv将 b b b变为 c c c q i q_i qi变为 q j q_j qj后左移 q i b v q_ibv qibv产生 q j c v q_jcv qjcv已经在带最左端不可再左移 若 δ ( q i , b ) ( q j , c , R ) \delta(q_i,b)(q_j,c,R) δ(qi,b)(qj,c,R)R表示右移则 u a q i b v uaq_ibv uaqibv产生 u a c q j v uacq_jv uacqjv因为带一定可以继续右移所以不需要分情况 如何判断当前状态已经在带最左端在当前位置写下某个特殊符号让带头向左移动若仍然检测到该符号则说明在最左端否则恢复原来的符号。
图灵可识别递归可枚举计算可枚举半可判定半可计算 图灵可判定递归可解能行可判定可计算
图灵可识别 ≠ \neq 图灵可判定
图灵机的等价变形
多带图灵机同时多个纸带 δ : Q × Γ k → Q × Γ k × { L , R } k \delta:Q\times\Gamma^k\rightarrow Q\times\Gamma^k\times\{L,R\}^k δ:Q×Γk→Q×Γk×{L,R}k δ : ( q i , a 1 , . . . , a k ) ( q j , b 1 , . . . , b k , L / R , L / R , . . . , L / R ⏟ k 个 ) \delta:(q_i,a_1,...,a_k)(q_j,b_1,...,b_k,\underbrace{L/R,L/R,...,L/R}_{k个}) δ:(qi,a1,...,ak)(qj,b1,...,bk,k个 L/R,L/R,...,L/R) 多带图灵机可转换为等价的单带图灵机 图灵可识别 ⇔ \Leftrightarrow ⇔可用多带图灵机识别
非确定性图灵机NTM
在左移/右移的基础上增加了“停止”状态 S S S d e l t a : Q × Γ → P ( Q × Γ × { L , R , S } ) delta:Q\times\Gamma\rightarrow P(Q\times\Gamma\times\{L,R,S\}) delta:Q×Γ→P(Q×Γ×{L,R,S}) 因此计算NTM格局的方式变为了计算树拥有多个非确定性分支 每个非确定性图灵机NTM都有等价的确定性图灵机DTM 图灵可识别 ⇔ \Leftrightarrow ⇔可用非确定性图灵机识别 图灵可判定 ⇔ \Leftrightarrow ⇔可用非确定性图灵机判定
识别器输入 x x x输出 0 / 1 / ? 0/1/? 0/1/?停机拒绝/停机接受/不停机 判定器输入 x x x输出 0 / 1 0/1 0/1停机拒绝/停机接受没有不停机 转换器输入 x x x输出 y y y输出一个串而非一位通常用于计算函数 产生器输入 0 n 0^n 0n输出 x n x_n xn生成序列 枚举器输入 ε \varepsilon ε输出 x 1 , x 2 , x 3 , . . . x_1,x_2,x_3,... x1,x2,x3,...无输入无遗漏无多余无顺序可重复
图灵可识别 ⇔ \Leftrightarrow ⇔图灵可枚举
图灵机算法
对象编码写作 O 1 , O 2 , . . . , O k O_1,O_2,...,O_k O1,O2,...,Ok表示对串 O 1 O 2 . . . O k O_1O_2...O_k O1O2...Ok进行一种编码转换。 eg:设定一种对 01 01 01串编码的方式将所有的字符重复出现1次多个串拼接时用两个不同的字符作为间隔符拼接。 x 010 , y 11 , x010,y11, x010,y11, x , y x,y x,y 001100101111 001100101111 001100101111 001100 ∣ 10 ∣ 1111 001100|10|1111 001100∣10∣1111
递归定理
存在可计算函数 q : Σ ∗ → Σ ∗ q:\Sigma^*\rightarrow\Sigma^* q:Σ∗→Σ∗ ∀ w \forall w ∀w q ( w ) q(w) q(w)是图灵机 P w P_w Pw的描述单带图灵机 P w P_w Pw打印出 w w w然后停机。一个函数如果可计算则和图灵机等价
自我复制机自己打印自己的图灵机。 ∀ x , S E L F ( x ) S E L F \forall x,SELF(x)SELF ∀x,SELF(x)SELF不断地进行自我复制 递归定理假设单带图灵机 T T T有计算函数 t : Σ ∗ × Σ ∗ → Σ ∗ t:\Sigma^*\times\Sigma^*\rightarrow\Sigma^* t:Σ∗×Σ∗→Σ∗则存在单带自动机 R R R其计算函数 r : Σ ∗ × Σ ∗ → Σ ∗ r:\Sigma^*\times\Sigma^*\rightarrow\Sigma^* r:Σ∗×Σ∗→Σ∗ ∀ w , r ( w ) t ( \forall w,r(w)t( ∀w,r(w)t( R R R , w ) ,w) ,w) T T T可以用 R R R来代替从而实现递归运算将问题转化
图灵机接受性问题
定义 A T M { M , w ∣ 图灵机 M 能接受串 w } A_{TM}\{M,w|图灵机M能接受串w\} ATM{M,w∣图灵机M能接受串w} 一个图灵机能接受某些给定的串构成的语言 是图灵可识别的是不可判定的 通用机存在一个固定的图灵机 U U U对于任意图灵机 M M M与输入 w w w U ( M , w ) M ( w ) U(M,w)M(w) U(M,w)M(w)
图灵机极小性问题
极小图灵机对于图灵机 M M M其描述的字符 M M M是最短的。 因为图灵机有无穷多种每种都有等价的极小图灵机因此 M I N T M MIN_{TM} MINTM是无穷语言。 M I N T M MIN_{TM} MINTM不是图灵可识别
不动点(xf(x))
递归定理的不动点形式对于 ∀ \forall ∀可计算函数 t : Σ ∗ → Σ ∗ t:\Sigma^*\rightarrow\Sigma^* t:Σ∗→Σ∗存在一个图灵机 F F F使得 t ( F ) t(F) t(F)描述一个与 F F F等价的图灵机。
四、可计算问题/不可计算问题
算法可解存在处处停机的等价图灵机。
对于正则语言的可判定问题 A D F A { B , w ∣ D F A B 接受串 w } A_{DFA}\{B,w|DFA\ B接受串w\} ADFA{B,w∣DFA B接受串w}是可判定语言。 同理 A N F A A_{NFA} ANFA是可判定语言。 A R E X { R , w ∣ 正则表达式 R 派生串 w } A_{REX}\{R,w|正则表达式\ R派生串w\} AREX{R,w∣正则表达式 R派生串w}是可判定语言。 因为DFA、NFA、REX提供给图灵机的都是等价的图灵机能在这三种之间进行转换 DFA空性 E D F A { A ∣ A 是 D F A 且 L ( A ) ∅ } E_{DFA}\{A|A是DFA且L(A)\empty\} EDFA{A∣A是DFA且L(A)∅}是可判定语言 DFA等价性 E Q D F A { A , B ∣ A 与 B 都是 D F A 且 L ( A ) L ( B ) } EQ_{DFA}\{A,B|A与B都是DFA且L(A)L(B)\} EQDFA{A,B∣A与B都是DFA且L(A)L(B)}是可判定语言。
关于上下文无关语言CFL的可判定问题
每一个CFL是可判定的 A C F G { G , w ∣ C F G G 派生串 w } A_{CFG}\{G,w|CFG\ G派生串w\} ACFG{G,w∣CFG G派生串w}是可判定语言。 CFG空性 E C F G { G ∣ C F G G L ( G ) ∅ } E_{CFG}\{G|CFG\ GL(G)\emptyset\} ECFG{G∣CFG GL(G)∅}是可判定语言。 CFG等价性 E Q C F G { G , H ∣ C F G G , H L ( G ) L ( H ) } EQ_{CFG}\{G,H|CFG\ G,HL(G)L(H)\} EQCFG{G,H∣CFG G,HL(G)L(H)}是不可判定语言
不可计算问题
有理数集可数实数集不可数
用对角化方法证明不可计算问题
对角化方法在判定结果图上构造一个非图灵机后观察对角线上的判定结果。 eg定义 A T M { M , w ∣ 图灵机 M 能接受串 w } A_{TM}\{M,w|图灵机M能接受串w\} ATM{M,w∣图灵机M能接受串w} 证明 A T M A_{TM} ATM不可判定。
证 那只需用对角化法证明 D T M D_{TM} DTM不可判定。 假设存在图灵机 H H H可判定 A T M A_{TM} ATM即 H ( M , w ) { 接受 M 接受 w 拒绝 M 不接受 w H(M,w)\left\{\begin{array}{ll} 接受 M接受w \\ 拒绝 M不接受w\end{array}\right. H(M,w){接受拒绝M接受wM不接受w 构造 D D D“对于输入 M M M M M M是图灵机” 在输入 M , M M,M M,M上运行 H H H如果 H H H接受则拒绝 D D D反之接受即 D ( M ) { 接受 M 不接受 M 拒绝 M 接受 M D(M)\left\{\begin{array}{ll} 接受 M不接受M \\ 拒绝 M接受M\end{array}\right. D(M){接受拒绝M不接受MM接受M M串是图灵机自己的编码即所有w中的一部分即 D T M D_{TM} DTM是 A T M A_{TM} ATM的特例。 不妨令 M D MD MD即 D ( D ) { 接受 D 不接受 D 拒绝 D 接受 D D(D)\left\{\begin{array}{ll} 接受 D不接受D \\ 拒绝 D接受D\end{array}\right. D(D){接受拒绝D不接受DD接受D 显然矛盾故原命题得证。 如图所示对于 H ( M , M ) H(M,M) H(M,M) D D D的结果是反过来的而 D D DD DD上的结果却并不是全部接受。
非图灵可识别语言
对于 A A A和 A A A的补集 A c / A ‾ Σ ∗ − A A^c/\overline{A}\Sigma^*-A Ac/AΣ∗−AA可判定 ⇔ \Leftrightarrow ⇔A与 A c A^c Ac图灵可识别。可判定语言对布尔运算封闭
归约法
图灵机的停机问题 H A L T T M { M , w ∣ 图灵机 M 在输入 w 上停机 } HALT_{TM}\{M,w|图灵机M在输入w上停机\} HALTTM{M,w∣图灵机M在输入w上停机}是不可判定的。 图灵机空性问题 E T M { M ∣ M 是图灵机且 L ( M ) ∅ } E_{TM}\{M|M是图灵机且L(M)\emptyset \} ETM{M∣M是图灵机且L(M)∅}是不可判定的。 图灵机正则性问题 R E G U L A R T M { M ∣ M 为图灵机且 L ( M ) 正则 } REGULAR_{TM}\{M|M为图灵机且L(M)正则\} REGULARTM{M∣M为图灵机且L(M)正则}是不可判定的。 图灵机等价性问题 E Q T M { M 1 , M 2 ∣ M 1 和 M 2 是图灵机且 L ( M 1 ) L ( M 2 ) } EQ_{TM}\{M_1,M_2|M_1和M_2是图灵机且L(M_1)L(M_2)\} EQTM{M1,M2∣M1和M2是图灵机且L(M1)L(M2)}是不可判定的。
