文章目录
一、乔姆斯基范式
二、上下文无关语法转为乔姆斯基范式步骤
三、上下文无关语法转为乔姆斯基范式示例1
四、上下文无关语法转为乔姆斯基范式示例 2
参考博客 :
【计算理论】上下文无关语法 ( 语法组成 | 规则 | 语法 | 语法示例 | 约定的简写形式 | 语法分析树 )
【计算理论】上下文无关语法 ( 代数表达式 | 代数表达式示例 | 确定性有限自动机 DFA 转为 上下文无关语法 )
【计算理论】上下文无关语法 CFG ( CFG 设计示例 | CFG 歧义性 | Chomsky 范式 | 上下文无关语法 转为 Chomsky 范式 )
一、乔姆斯基范式
1 . Chomsky 范式 : 上下文无关语法中的任何规则都是如下 格式 ;
① 单个变元到 2 22 个变元 A → B C \rm A \to BCA→BC : A AA 是 变元 , B , C \rm B,CB,C 也是变元 ;
② 单个变元到常元 A → a \rm A \to aA→a : A \rm AA 是 变元 , a \rm aa 是常元 , A \rm AA 可以被终端字符替换 ;
③ B , C \rm B ,CB,C 变元要求 : B , C \rm B, CB,C 变元一定不能是开始变元 ;
④ S → ε \rm S \to \varepsilonS→ε : S \rm SS 开始变元可以为空 ;
⑤ 不能出现 变 元 → 变 元 \rm 变元 \to 变元变元→变元 单个变元 到 单个变元不允许出现 ;
2 . S → ε \rm S \to \varepsilonS→ε 规则 说明 :
① 语言包含空字符串 : 如果上下文无关语法包含空字符串时 , 一定 需要 S → ε \rm S \to \varepsilonS→ε 规则 ;
② 语言不包含空字符串 : 如果上下文无关语法不包含空字符串时 , 一定 不需要 S → ε \rm S \to \varepsilonS→ε 规则 ;
③ 规则总结 : 该规则决定 上下文无关语法 所生成的语言 是否包含 空字符串 ; 如果包含 , 必须要这个规则 ; 如果不包含 , 空字符串一定不要这个规则 ;
二、上下文无关语法转为乔姆斯基范式步骤
上下文无关语法转为乔姆斯基范式步骤 :
1 . 添加开始变元及规则 : 添加一个新的 开始变元 S 0 \rm S_0S
0
, 以及配套的规则 S 0 → S \rm S_0 \to SS
0
→S , S \rm SS 是旧的开始变元 ;
① 目的 : 添加开始变元的目的是 开始变元 永远出现在左边 ;
② Chomsky 范式 中 , 开始变元始终在规则的左边 , 不允许开始变元在规则的右侧 ;
③ 对应 Chomsky 范式 规则 : A → B C \rm A \to BCA→BC 规则 , A \rm AA 是 变元 , B , C \rm B,CB,C 也是变元 , 并且 B , C \rm B,CB,C 不允许是开始变元 ;
2 . 消除所有的 ε \varepsilonε 规则 : 消除所有 从 变元 到 空字符 的规则 ;
3 . 消除所有的 A → B \rm A \to BA→B 规则 : 消除所有 从 单个变元 到 单个变元的 单条规则 , 允许从 单个变元 到 多个变元或常元 ; 如 : A → B \rm A \to BA→B 是需要删除的 , A → B S \rm A \to BSA→BS 可以保留 ;
4 . 添加变元 : 将 A → B C D \rm A \to BCDA→BCD 规则 , 转为 A → E D \rm A \to EDA→ED 规则 , 添加变元 E → B C \rm E \to BCE→BC ;
三、上下文无关语法转为乔姆斯基范式示例1
将 上下文无关语法 转为 Chomsky 范式 :
S → A S A ∣ a B \rm S \to ASA | aBS→ASA∣aB
A → B ∣ S \rm A \to B|SA→B∣S
B → b ∣ ε \rm B \to b|\varepsilonB→b∣ε
1 . 添加新的开始变元 : S 0 \rm S_0S
0
;
S 0 → S \rm S_0 \to SS
0
→S
S → A S A ∣ a B \rm S \to ASA | aBS→ASA∣aB
A → B ∣ S \rm A \to B|SA→B∣S
B → b ∣ ε \rm B \to b|\varepsilonB→b∣ε
2 . 消除 B → ε \rm B \to \varepsilonB→ε 规则 : 根据消除前后等价原则 , 重新构造含有 B \rm BB 的规则 ; 消除 B → ε \rm B \to \varepsilonB→ε , 即在对应的含有 B \rm BB 的规则中添加 B \rm BB 为空的情况 , a B \rm aBaB 如果 B \rm BB 为空就是 a \rm aa , B \rm BB 如果 B \rm BB 为空就是 ε \rm \varepsilonε ;
S 0 → S \rm S_0 \to SS
0
→S
S → A S A ∣ a B ∣ a \rm S \to ASA | aB | aS→ASA∣aB∣a
A → B ∣ ε ∣ S \rm A \to B| \varepsilon |SA→B∣ε∣S
B → b \rm B \to bB→b
3 . 消除 A → ε \rm A \to \varepsilonA→ε 规则 : 根据消除前后等价原则 , 重新构造含有 A \rm AA 的规则 ; 消除 A → ε \rm A \to \varepsilonA→ε , 即在对应的含有 A \rm AA 的规则中添加 A \rm AA 为空的情况 , A S A \rm ASAASA 如果 A \rm AA 为空就产生 S , A S , S A \rm S , AS, SAS,AS,SA 三种 ( 考虑不同 A \rm AA 为空的情况 ) ;
S 0 → S \rm S_0 \to SS
0
→S
S → A S A ∣ A S ∣ S A ∣ a B ∣ a \rm S \to ASA | AS | SA | aB | aS→ASA∣AS∣SA∣aB∣a
A → B ∣ S \rm A \to B| SA→B∣S
B → b \rm B \to bB→b
4 . 消除 A → B \rm A \to BA→B 规则 : 找 B \rm BB 出现在左边的情况 , 发现有 B → b \rm B \to bB→b 规则 , 直接使用 A → b \rm A \to bA→b 替换 A → B \rm A \to BA→B 规则 ; ( 注意 : B → b \rm B \to bB→b 规则 不变 )
S 0 → S \rm S_0 \to SS
0
→S
S → A S A ∣ A S ∣ S A ∣ S ∣ a B ∣ a \rm S \to ASA | AS | SA | S | aB | aS→ASA∣AS∣SA∣S∣aB∣a
A → b ∣ S \rm A \to b | SA→b∣S
B → b \rm B \to bB→b
5 . 消除 S 0 → S \rm S_0 \to SS
0
→S 规则 : 找 S \rm SS 出现在左边的情况 , 发现有 S → A S A ∣ A S ∣ S A ∣ S ∣ a B ∣ a \rm S \to ASA | AS | SA | S | aB | aS→ASA∣AS∣SA∣S∣aB∣a , 使用 S 0 → A S A ∣ A S ∣ S A ∣ S ∣ a B ∣ a \rm S_0 \to ASA | AS | SA | S | aB | aS
0
→ASA∣AS∣SA∣S∣aB∣a , 替换 S 0 → S \rm S_0 \to SS
0
→S ; ( 注意 : S → A S A ∣ A S ∣ S A ∣ S ∣ a B ∣ a \rm S \to ASA | AS | SA | S | aB | aS→ASA∣AS∣SA∣S∣aB∣a 规则不变 )
S 0 → A S A ∣ A S ∣ S A ∣ S ∣ a B ∣ a \rm S_0 \to ASA | AS | SA | S | aB | aS
0
→ASA∣AS∣SA∣S∣aB∣a
S → A S A ∣ A S ∣ S A ∣ a B ∣ a \rm S \to ASA | AS | SA | aB | aS→ASA∣AS∣SA∣aB∣a
A → b ∣ A S A ∣ A S ∣ S A ∣ a B ∣ a \rm A \to b | ASA | AS | SA | aB | aA→b∣ASA∣AS∣SA∣aB∣a
B → b \rm B \to bB→b
6 . 添加变元 : 添加新规则 R → S A \rm R \to SAR→SA ;
S 0 → A R ∣ A S ∣ S A ∣ S ∣ a B ∣ a \rm S_0 \to AR | AS | SA | S | aB | aS
0
→AR∣AS∣SA∣S∣aB∣a
S → A R ∣ A S ∣ S A ∣ a B ∣ a \rm S \to AR | AS | SA | aB | aS→AR∣AS∣SA∣aB∣a
A → b ∣ A R ∣ A S ∣ S A ∣ a B ∣ a \rm A \to b | AR | AS | SA | aB | aA→b∣AR∣AS∣SA∣aB∣a
R → S A \rm R \to SAR→SA
B → b \rm B \to bB→b
四、上下文无关语法转为乔姆斯基范式示例 2
将 上下文无关语法转为 Chomsky 范式 :
A → B A B ∣ B ∣ ε \rm A \to BAB | B | \varepsilonA→BAB∣B∣ε
B → 00 ∣ ε \rm B \to 00 | \varepsilonB→00∣ε
1 . 添加新的开始变元 : S 0 \rm S_0S
0
;
S 0 → A \rm S_0 \to AS
0
→A
A → B A B ∣ B ∣ ε \rm A \to BAB | B | \varepsilonA→BAB∣B∣ε
B → 00 ∣ ε \rm B \to 00 | \varepsilonB→00∣ε
2 . 消除 B → ε \rm B \to \varepsilonB→ε 规则 : 根据消除前后等价原则 , 重新构造含有 B \rm BB 的规则 , 即添加使用 ε \varepsilonε 替换 B \rm BB 的各种情况 , 如 : B A B \rm BABBAB , 替换 1 11 个 B \rm BB 两种情况 , 替换 2 22 个 B \rm BB 一种情况 ;
S 0 → A \rm S_0 \to AS
0
→A
A → B A B ∣ B A ∣ A B ∣ A ∣ B ∣ ε \rm A \to BAB | BA | AB | A | B | \varepsilonA→BAB∣BA∣AB∣A∣B∣ε
B → 00 \rm B \to 00B→00
3 . 消除 A → ε \rm A \to \varepsilonA→ε 规则 : 根据消除前后等价原则 , 重新构造含有 A \rm AA 的规则 , 如 : B A B \rm BABBAB 如果 A \rm AA 为空 就是 B B \rm BBBB , A B \rm ABAB 如果 A \rm AA 为空 , 多出一个 B \rm BB ;
S 0 → A \rm S_0 \to AS
0
→A
A → B A B ∣ B A ∣ A B ∣ A ∣ B ∣ B B \rm A \to BAB | BA | AB | A | B | BBA→BAB∣BA∣AB∣A∣B∣BB
B → 00 \rm B \to 00B→00
4 . 消除 A → B \rm A \to BA→B 规则 : 找 B \rm BB 出现在左边的情况 , 发现有 B → 00 \rm B \to 00B→00 规则 , 直接使用 A → 00 \rm A \to 00A→00 规则 替换 A → B \rm A \to BA→B 规则 ; ( 注意 : B → 00 \rm B \to 00B→00 规则 不变 )
S 0 → A \rm S_0 \to AS
0
→A
A → B A B ∣ B A ∣ A B ∣ A ∣ 00 ∣ B B \rm A \to BAB | BA | AB | A | 00 | BBA→BAB∣BA∣AB∣A∣00∣BB
B → 00 \rm B \to 00B→00
5 . 消除 S 0 → A \rm S_0 \to AS
0
→A 规则 : 找 A \rm AA 出现在左边的情况 , 发现有 A → B A B ∣ B A ∣ A B ∣ A ∣ 00 ∣ B B \rm A \to BAB | BA | AB | A | 00 | BBA→BAB∣BA∣AB∣A∣00∣BB 规则 , 直接使用 S 0 → B A B ∣ B A ∣ A B ∣ A ∣ 00 ∣ B B \rm S_0 \to BAB | BA | AB | A | 00 | BBS
0
→BAB∣BA∣AB∣A∣00∣BB 规则 替换 S 0 → A \rm S_0 \to AS
0
→A 规则 ; ( 注意 A → B A B ∣ B A ∣ A B ∣ A ∣ 00 ∣ B B \rm A \to BAB | BA | AB | A | 00 | BBA→BAB∣BA∣AB∣A∣00∣BB 规则 规则不变 )
S 0 → B A B ∣ B A ∣ A B ∣ A ∣ 00 ∣ B B \rm S_0 \to BAB | BA | AB | A | 00 | BBS
0
→BAB∣BA∣AB∣A∣00∣BB
A → B A B ∣ B A ∣ A B ∣ A ∣ 00 ∣ B B \rm A \to BAB | BA | AB | A | 00 | BBA→BAB∣BA∣AB∣A∣00∣BB
B → 00 \rm B \to 00B→00
6 . 添加变元 : 添加新规则 R → B A \rm R \to BAR→BA ; 目的是使用 2 22 个变元的规则替换 3 33 个变元的规则 ;
S 0 → R B ∣ B A ∣ A B ∣ A ∣ 00 ∣ B B \rm S_0 \to RB | BA | AB | A | 00 | BBS
0
→RB∣BA∣AB∣A∣00∣BB
A → R B ∣ B A ∣ A B ∣ A ∣ 00 ∣ B B \rm A \to RB | BA | AB | A | 00 | BBA→RB∣BA∣AB∣A∣00∣BB
B → 00 \rm B \to 00B→00
R → B A \rm R \to BAR→BA
7 . 添加变元 : 添加新规则 C → 0 \rm C \to 0C→0 ; 目的是将 B → 00 \rm B \to 00B→00 中的 2 22 个终端字符转为两个变元 ;
S 0 → R B ∣ B A ∣ A B ∣ A ∣ C C ∣ B B \rm S_0 \to RB | BA | AB | A | CC | BBS
0
→RB∣BA∣AB∣A∣CC∣BB
A → R B ∣ B A ∣ A B ∣ A ∣ C C ∣ B B \rm A \to RB | BA | AB | A | CC | BBA→RB∣BA∣AB∣A∣CC∣BB
B → C C \rm B \to CCB→CC
R → B A \rm R \to BAR→BA
C → 0 \rm C \to 0C→0
