文章目录
一、上下文无关文法 ( CFG )
二、上下文无关文法 ( CFG ) 示例
三、确定性有限自动机 DFA 转为 上下文无关语法 CFG
参考博客 :
【计算理论】上下文无关语法 ( 语法组成 | 规则 | 语法 | 语法示例 | 约定的简写形式 | 语法分析树 )
【计算理论】上下文无关语法 ( 代数表达式 | 代数表达式示例 | 确定性有限自动机 DFA 转为 上下文无关语法 )
【计算理论】上下文无关语法 CFG ( CFG 设计示例 | CFG 歧义性 | Chomsky 范式 | 上下文无关语法 转为 Chomsky 范式 )
一、上下文无关文法 ( CFG )
上下文无关语法 组成 : 由 { V , Σ , R , S } \{ \quad V , \Sigma , R , S \quad \}{V,Σ,R,S} 四部分组成 ;
变量集 V VV : 有限的变量集合 ;
终端字符集 Σ \SigmaΣ : 有限的终端字符组成的集合 ; 相当于常量的含义 , 与变量相对 ;
规则集 R RR : 有限的规则组成的集合 , 规则规定如何进行代换操作 , 规定 变量 , 终端字符 , 字符串变量 等 ;
开始变量 S SS : 该变量作为开始变量 ;
规则 :
① 已知条件 : 假设 u , v , w u, v , wu,v,w 是 变量 ( 变元 ) 或 终端字符集 ( 常量 / 常元 ) ;
② 规则描述 : 规则是一个箭头 , A → w A \to wA→w , A AA 是变元 , w ww 是 变元 和 常元 组成的终端字符 ;
③ 规则用法 : 在字符串中 , 根据 A → w A \to wA→w 规则进行替换 , 只需要将 A AA 变元替换成 w ww 字符串即可 ;
④ 规则示例 : u A v uAvuAv 中使用上述规则进行替换 , 将 A AA 替换成 w ww , 替换结果是得到新字符串 u w v uwvuwv ;
u A v ⇒ u w v uAv \Rightarrow uwv
uAv⇒uwv
二、上下文无关文法 ( CFG ) 示例
上下文无关文法 ( CFG ) : G 3 = ( { S } , { a , b } , R , S ) \rm G3 =( \; \{ S \}, \{ a, b \}, R , S \; )G3=({S},{a,b},R,S) 其组成如下 :
变量集 { S } \rm \{ S \}{S} ;
终端字符集 { a , b } \rm \{ a, b \}{a,b} ;
规则 R \rm RR ;
开始变量 S \rm SS ;
规则 R \rm RR 描述 : S → a S b ∣ S S ∣ ε \rm S \to aSb \; | \; SS \; | \; \varepsilonS→aSb∣SS∣ε
S \rm SS 变量 可以使用 a S b \rm aSbaSb 字符串替换 ;
S \rm SS 变量 可以使用 S S \rm SSSS 字符串替换 ;
S \rm SS 变量 可以使用 ε \rm \varepsilonε 字符串替换 ;
规则替换过程 : 下面的 ① ~ ⑦ 分别对应七次规则替换 ;
S ⇒ a S b ⇒ a a S b b ⇒ a a S S b b ⇒ a a a S b S b b ⇒ a a a b S b b ⇒ a a a b a S b b b ⇒ a a a b a b b b \rm S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aaSSbb \Rightarrow aaaSbSbb \Rightarrow aaabSbb \Rightarrow aaabaSbbb \Rightarrow aaababbbS⇒aSb⇒aaSbb⇒aaSSbb⇒aaaSbSbb⇒aaabSbb⇒aaabaSbbb⇒aaababbb
① S S \rm S SSS 是开始变量 , 可以使用 a S b \rm aSbaSb 替换 S \rm SS ; S ⇒ a S b \rm S \Rightarrow aSbS⇒aSb
② 使用 a S b \rm aSbaSb 替换 S \rm SS ; a S b ⇒ a a S b b \rm aSb \Rightarrow aaSbbaSb⇒aaSbb
③ 使用 S S \rm SSSS 替换 S \rm SS ; a a S b b ⇒ a a S S b b \rm aaSbb \Rightarrow aaSSbbaaSbb⇒aaSSbb
④ 使用 a S b \rm aSbaSb 替换第一个 S \rm SS ; a a S S b b ⇒ a a a S b S b b \rm aaSSbb \Rightarrow aaaSbSbbaaSSbb⇒aaaSbSbb
⑤ 使用 ε \rm \varepsilonε 替换第一个 S \rm SS ; a a a S b S b b ⇒ a a a b S b b \rm aaaSbSbb \Rightarrow aaabSbbaaaSbSbb⇒aaabSbb
⑥ 使用 a S b \rm aSbaSb 替换 S \rm SS ; a a a b S b b ⇒ a a a b a S b b b \rm aaabSbb \Rightarrow aaabaSbbbaaabSbb⇒aaabaSbbb
⑦ 使用 ε \rm \varepsilonε 替换 S \rm SS ; a a a b a S b b b ⇒ a a a b a b b b \rm aaabaSbbb \Rightarrow aaababbbaaabaSbbb⇒aaababbb
三、确定性有限自动机 DFA 转为 上下文无关语法 CFG
1 . 确定性有限自动机 ( DFA ) 转为 上下文无关语法 ( CFG ) : 将
确定性有限自动机 ( DFA ) 的指令 , 转为 对应的
上下文无关语法 ( CFG ) 规则 : δ ( q i , a ) = q j ⇒ R i → a R j \rm \delta ( q_i, a ) = q_j \Rightarrow R_i \to aR_jδ(q
i
,a)=q
j
⇒R
i
→aR
j
δ ( q i , a ) = q j \delta ( q_i, a ) = q_jδ(q
i
,a)=q
j
表示 q i q_iq
i
状态下 , 读取字符 a aa , 跳转到 q j q_jq
j
状态 ;
2 . 自动机的 状态跳转 转换成 规则 示例 : 下图中的 确定性有限自动机 , 开始状态 A AA 读取 1 11 字符 转化成 B BB 状态 , 表示成规则就是 R A → 1 R B R_A \to 1R_BR
A
→1R
B
3 . 自动机的状态 A AA 读取 字符 a aa 转换成另一个状态 B BB , 都可以转换成对应的规则 R A → a R B R_A \to aR_BR
A
→aR
B
;
4 . 计算能力对比 : 上下文无关语法 的计算能力 要大于等于 自动机的计算能力 ;
