【计算理论】计算理论总结 ( 上下文无关文法 | 乔姆斯基范式 | 乔姆斯基范式转化步骤 | 示例 ) ★★

参考博客 :

• 【计算理论】上下文无关语法 ( 语法组成 | 规则 | 语法 | 语法示例 | 约定的简写形式 | 语法分析树 )
• 【计算理论】上下文无关语法 ( 代数表达式 | 代数表达式示例 | 确定性有限自动机 DFA 转为 上下文无关语法 )
• 【计算理论】上下文无关语法 CFG ( CFG 设计示例 | CFG 歧义性 | Chomsky 范式 | 上下文无关语法 转为 Chomsky 范式 )

一、乔姆斯基范式

1 . Chomsky 范式 : 上下文无关语法中的任何规则都是如下 格式 ;

① 单个变元到 2 2 2 个变元 A → B C \rm A \to BC A→BC : A A A 是 变元 , B , C \rm B,C B,C 也是变元 ;

② 单个变元到常元 A → a \rm A \to a A→a : A \rm A A 是 变元 , a \rm a a 是常元 , A \rm A A 可以被终端字符替换 ;

③ B , C \rm B ,C B,C 变元要求 : B , C \rm B, C B,C 变元一定不能是开始变元 ;

④ S → ε \rm S \to \varepsilon S→ε : S \rm S S 开始变元可以为空 ;

⑤ 不能出现 变 元 → 变 元 \rm 变元 \to 变元 变元→变元 单个变元 到 单个变元不允许出现 ;

2 . S → ε \rm S \to \varepsilon S→ε 规则 说明 :

① 语言包含空字符串 : 如果上下文无关语法包含空字符串时 , 一定 需要 S → ε \rm S \to \varepsilon S→ε 规则 ;

② 语言不包含空字符串 : 如果上下文无关语法不包含空字符串时 , 一定 不需要 S → ε \rm S \to \varepsilon S→ε 规则 ;

③ 规则总结 : 该规则决定 上下文无关语法 所生成的语言 是否包含 空字符串 ; 如果包含 , 必须要这个规则 ; 如果不包含 , 空字符串一定不要这个规则 ;

二、上下文无关语法转为乔姆斯基范式步骤

上下文无关语法转为乔姆斯基范式步骤 :

1 . 添加开始变元及规则 : 添加一个新的 开始变元 S 0 \rm S_0 S0​ , 以及配套的规则 S 0 → S \rm S_0 \to S S0​→S , S \rm S S 是旧的开始变元 ;

① 目的 : 添加开始变元的目的是 开始变元 永远出现在左边 ;

② Chomsky 范式 中 , 开始变元始终在规则的左边 , 不允许开始变元在规则的右侧 ;

③ 对应 Chomsky 范式 规则 : A → B C \rm A \to BC A→BC 规则 , A \rm A A 是 变元 , B , C \rm B,C B,C 也是变元 , 并且 B , C \rm B,C B,C 不允许是开始变元 ;

2 . 消除所有的 ε \varepsilon ε 规则 : 消除所有 从 变元 到 空字符 的规则 ;

3 . 消除所有的 A → B \rm A \to B A→B 规则 : 消除所有 从 单个变元 到 单个变元的 单条规则 , 允许从 单个变元 到 多个变元或常元 ; 如 : A → B \rm A \to B A→B 是需要删除的 , A → B S \rm A \to BS A→BS 可以保留 ;

4 . 添加变元 : 将 A → B C D \rm A \to BCD A→BCD 规则 , 转为 A → E D \rm A \to ED A→ED 规则 , 添加变元 E → B C \rm E \to BC E→BC ;

三、上下文无关语法转为乔姆斯基范式示例1

将 上下文无关语法 转为 Chomsky 范式 :

• S → A S A ∣ a B \rm S \to ASA | aB S→ASA∣aB
• A → B ∣ S \rm A \to B|S A→B∣S
• B → b ∣ ε \rm B \to b|\varepsilon B→b∣ε

1 . 添加新的开始变元 : S 0 \rm S_0 S0​ ;

• S 0 → S \rm S_0 \to S S0​→S
• S → A S A ∣ a B \rm S \to ASA | aB S→ASA∣aB
• A → B ∣ S \rm A \to B|S A→B∣S
• B → b ∣ ε \rm B \to b|\varepsilon B→b∣ε

2 . 消除 B → ε \rm B \to \varepsilon B→ε 规则 : 根据消除前后等价原则 , 重新构造含有 B \rm B B 的规则 ; 消除 B → ε \rm B \to \varepsilon B→ε , 即在对应的含有 B \rm B B 的规则中添加 B \rm B B 为空的情况 , a B \rm aB aB 如果 B \rm B B 为空就是 a \rm a a , B \rm B B 如果 B \rm B B 为空就是 ε \rm \varepsilon ε ;

• S 0 → S \rm S_0 \to S S0​→S
• S → A S A ∣ a B ∣ a \rm S \to ASA | aB | a S→ASA∣aB∣a
• A → B ∣ ε ∣ S \rm A \to B| \varepsilon |S A→B∣ε∣S
• B → b \rm B \to b B→b

3 . 消除 A → ε \rm A \to \varepsilon A→ε 规则 : 根据消除前后等价原则 , 重新构造含有 A \rm A A 的规则 ; 消除 A → ε \rm A \to \varepsilon A→ε , 即在对应的含有 A \rm A A 的规则中添加 A \rm A A 为空的情况 , A S A \rm ASA ASA 如果 A \rm A A 为空就产生 S , A S , S A \rm S , AS, SA S,AS,SA 三种 ( 考虑不同 A \rm A A 为空的情况 ) ;

• S 0 → S \rm S_0 \to S S0​→S
• S → A S A ∣ A S ∣ S A ∣ a B ∣ a \rm S \to ASA | AS | SA | aB | a S→ASA∣AS∣SA∣aB∣a
• A → B ∣ S \rm A \to B| S A→B∣S
• B → b \rm B \to b B→b

4 . 消除 A → B \rm A \to B A→B 规则 : 找 B \rm B B 出现在左边的情况 , 发现有 B → b \rm B \to b B→b 规则 , 直接使用 A → b \rm A \to b A→b 替换 A → B \rm A \to B A→B 规则 ; ( 注意 : B → b \rm B \to b B→b 规则 不变 )

• S 0 → S \rm S_0 \to S S0​→S
• S → A S A ∣ A S ∣ S A ∣ S ∣ a B ∣ a \rm S \to ASA | AS | SA | S | aB | a S→ASA∣AS∣SA∣S∣aB∣a
• A → b ∣ S \rm A \to b | S A→b∣S
• B → b \rm B \to b B→b

5 . 消除 S 0 → S \rm S_0 \to S S0​→S 规则 : 找 S \rm S S 出现在左边的情况 , 发现有 S → A S A ∣ A S ∣ S A ∣ S ∣ a B ∣ a \rm S \to ASA | AS | SA | S | aB | a S→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 | a S0​→ASA∣AS∣SA∣S∣aB∣a , 替换 S 0 → S \rm S_0 \to S S0​→S ; ( 注意 : S → A S A ∣ A S ∣ S A ∣ S ∣ a B ∣ a \rm S \to ASA | AS | SA | S | aB | a S→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 | a S0​→ASA∣AS∣SA∣S∣aB∣a
• S → A S A ∣ A S ∣ S A ∣ a B ∣ a \rm S \to ASA | AS | SA | aB | a S→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 | a A→b∣ASA∣AS∣SA∣aB∣a
• B → b \rm B \to b B→b

6 . 添加变元 : 添加新规则 R → S A \rm R \to SA R→SA ;

• S 0 → A R ∣ A S ∣ S A ∣ S ∣ a B ∣ a \rm S_0 \to AR | AS | SA | S | aB | a S0​→AR∣AS∣SA∣S∣aB∣a
• S → A R ∣ A S ∣ S A ∣ a B ∣ a \rm S \to AR | AS | SA | aB | a S→AR∣AS∣SA∣aB∣a
• A → b ∣ A R ∣ A S ∣ S A ∣ a B ∣ a \rm A \to b | AR | AS | SA | aB | a A→b∣AR∣AS∣SA∣aB∣a
• R → S A \rm R \to SA R→SA
• B → b \rm B \to b B→b

四、上下文无关语法转为乔姆斯基范式示例 2

将 上下文无关语法转为 Chomsky 范式 :

• A → B A B ∣ B ∣ ε \rm A \to BAB | B | \varepsilon A→BAB∣B∣ε
• B → 00 ∣ ε \rm B \to 00 | \varepsilon B→00∣ε

1 . 添加新的开始变元 : S 0 \rm S_0 S0​ ;

• S 0 → A \rm S_0 \to A S0​→A
• A → B A B ∣ B ∣ ε \rm A \to BAB | B | \varepsilon A→BAB∣B∣ε
• B → 00 ∣ ε \rm B \to 00 | \varepsilon B→00∣ε

2 . 消除 B → ε \rm B \to \varepsilon B→ε 规则 : 根据消除前后等价原则 , 重新构造含有 B \rm B B 的规则 , 即添加使用 ε \varepsilon ε 替换 B \rm B B 的各种情况 , 如 : B A B \rm BAB BAB , 替换 1 1 1 个 B \rm B B 两种情况 , 替换 2 2 2 个 B \rm B B 一种情况 ;

• S 0 → A \rm S_0 \to A S0​→A
• A → B A B ∣ B A ∣ A B ∣ A ∣ B ∣ ε \rm A \to BAB | BA | AB | A | B | \varepsilon A→BAB∣BA∣AB∣A∣B∣ε
• B → 00 \rm B \to 00 B→00

3 . 消除 A → ε \rm A \to \varepsilon A→ε 规则 : 根据消除前后等价原则 , 重新构造含有 A \rm A A 的规则 , 如 : B A B \rm BAB BAB 如果 A \rm A A 为空 就是 B B \rm BB BB , A B \rm AB AB 如果 A \rm A A 为空 , 多出一个 B \rm B B ;

• S 0 → A \rm S_0 \to A S0​→A
• A → B A B ∣ B A ∣ A B ∣ A ∣ B ∣ B B \rm A \to BAB | BA | AB | A | B | BB A→BAB∣BA∣AB∣A∣B∣BB
• B → 00 \rm B \to 00 B→00

4 . 消除 A → B \rm A \to B A→B 规则 : 找 B \rm B B 出现在左边的情况 , 发现有 B → 00 \rm B \to 00 B→00 规则 , 直接使用 A → 00 \rm A \to 00 A→00 规则 替换 A → B \rm A \to B A→B 规则 ; ( 注意 : B → 00 \rm B \to 00 B→00 规则 不变 )

• S 0 → A \rm S_0 \to A S0​→A
• A → B A B ∣ B A ∣ A B ∣ A ∣ 00 ∣ B B \rm A \to BAB | BA | AB | A | 00 | BB A→BAB∣BA∣AB∣A∣00∣BB
• B → 00 \rm B \to 00 B→00

5 . 消除 S 0 → A \rm S_0 \to A S0​→A 规则 : 找 A \rm A A 出现在左边的情况 , 发现有 A → B A B ∣ B A ∣ A B ∣ A ∣ 00 ∣ B B \rm A \to BAB | BA | AB | A | 00 | BB A→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 | BB S0​→BAB∣BA∣AB∣A∣00∣BB 规则 替换 S 0 → A \rm S_0 \to A S0​→A 规则 ; ( 注意 A → B A B ∣ B A ∣ A B ∣ A ∣ 00 ∣ B B \rm A \to BAB | BA | AB | A | 00 | BB A→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 | BB S0​→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 | BB A→BAB∣BA∣AB∣A∣00∣BB
• B → 00 \rm B \to 00 B→00

6 . 添加变元 : 添加新规则 R → B A \rm R \to BA R→BA ; 目的是使用 2 2 2 个变元的规则替换 3 3 3 个变元的规则 ;

• S 0 → R B ∣ B A ∣ A B ∣ A ∣ 00 ∣ B B \rm S_0 \to RB | BA | AB | A | 00 | BB S0​→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 | BB A→RB∣BA∣AB∣A∣00∣BB
• B → 00 \rm B \to 00 B→00
• R → B A \rm R \to BA R→BA

7 . 添加变元 : 添加新规则 C → 0 \rm C \to 0 C→0 ; 目的是将 B → 00 \rm B \to 00 B→00 中的 2 2 2 个终端字符转为两个变元 ;

• S 0 → R B ∣ B A ∣ A B ∣ A ∣ C C ∣ B B \rm S_0 \to RB | BA | AB | A | CC | BB S0​→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 | BB A→RB∣BA∣AB∣A∣CC∣BB
• B → C C \rm B \to CC B→CC
• R → B A \rm R \to BA R→BA
• C → 0 \rm C \to 0 C→0