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

韩曙亮

发布于 2023-03-28 20:19:14

9150

发布于 2023-03-28 20:19:14

文章被收录于专栏：韩曙亮的移动开发专栏

文章目录

参考博客 :

一、乔姆斯基范式

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

① 单个变元到

2

个变元

\rm A \to BC

:

A

是变元 ,

\rm B,C

也是变元 ;

② 单个变元到常元

\rm A \to a

:

\rm A

是变元 ,

\rm a

是常元 ,

\rm A

可以被终端字符替换 ;

③

\rm B ,C

变元要求 :

\rm B, C

变元一定不能是开始变元 ;

④

\rm S \to \varepsilon

:

\rm S

开始变元可以为空 ;

⑤ 不能出现

\rm 变元 \to 变元

单个变元到单个变元不允许出现 ;

2 .

\rm S \to \varepsilon

规则说明 :

① 语言包含空字符串 : 如果上下文无关语法包含空字符串时 , 一定需要

\rm S \to \varepsilon

规则 ;

② 语言不包含空字符串 : 如果上下文无关语法不包含空字符串时 , 一定不需要

\rm S \to \varepsilon

规则 ;

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

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

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

1 . 添加开始变元及规则 : 添加一个新的开始变元

\rm S_0

, 以及配套的规则

\rm S_0 \to S

,

\rm S

是旧的开始变元 ;

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

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

③ 对应 Chomsky 范式规则 :

\rm A \to BC

规则 ,

\rm A

是变元 ,

\rm B,C

也是变元 , 并且

\rm B,C

不允许是开始变元 ;

2 . 消除所有的

\varepsilon

规则 : 消除所有从变元到空字符的规则 ;

3 . 消除所有的

\rm A \to B

规则 : 消除所有从单个变元到单个变元的单条规则 , 允许从单个变元到多个变元或常元 ; 如 :

\rm A \to B

是需要删除的 ,

\rm A \to BS

可以保留 ;

4 . 添加变元 : 将

\rm A \to BCD

规则 , 转为

\rm A \to ED

规则 , 添加变元

\rm E \to BC

;

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

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

\rm S \to ASA | aB

\rm A \to B|S

\rm B \to b|\varepsilon

1 . 添加新的开始变元 :

\rm S_0

;

\rm S_0 \to S

\rm S \to ASA | aB

\rm A \to B|S

\rm B \to b|\varepsilon

2 . 消除

\rm B \to \varepsilon

规则 : 根据消除前后等价原则 , 重新构造含有

\rm B

的规则 ; 消除

\rm B \to \varepsilon

, 即在对应的含有

\rm B

的规则中添加

\rm B

为空的情况 ,

\rm aB

如果

\rm B

为空就是

\rm a

,

\rm B

如果

\rm B

为空就是

\rm \varepsilon

;

\rm S_0 \to S

\rm S \to ASA | aB | a

\rm A \to B| \varepsilon |S

\rm B \to b

3 . 消除

\rm A \to \varepsilon

规则 : 根据消除前后等价原则 , 重新构造含有

\rm A

的规则 ; 消除

\rm A \to \varepsilon

, 即在对应的含有

\rm A

的规则中添加

\rm A

为空的情况 ,

\rm ASA

如果

\rm A

为空就产生

\rm S , AS, SA

三种 ( 考虑不同

\rm A

为空的情况 ) ;

\rm S_0 \to S

\rm S \to ASA | AS | SA | aB | a

\rm A \to B| S

\rm B \to b

4 . 消除

\rm A \to B

规则 : 找

\rm B

出现在左边的情况 , 发现有

\rm B \to b

规则 , 直接使用

\rm A \to b

替换

\rm A \to B

规则 ; ( 注意 :

\rm B \to b

规则不变 )

\rm S_0 \to S

\rm S \to ASA | AS | SA | S | aB | a

\rm A \to b | S

\rm B \to b

5 . 消除

\rm S_0 \to S

规则 : 找

\rm S

出现在左边的情况 , 发现有

\rm S \to ASA | AS | SA | S | aB | a

, 使用

\rm S_0 \to ASA | AS | SA | S | aB | a

, 替换

\rm S_0 \to S

; ( 注意 :

\rm S \to ASA | AS | SA | S | aB | a

规则不变 )

\rm S_0 \to ASA | AS | SA | S | aB | a

\rm S \to ASA | AS | SA | aB | a

\rm A \to b | ASA | AS | SA | aB | a

\rm B \to b

6 . 添加变元 : 添加新规则

\rm R \to SA

;

\rm S_0 \to AR | AS | SA | S | aB | a

\rm S \to AR | AS | SA | aB | a

\rm A \to b | AR | AS | SA | aB | a

\rm R \to SA

\rm B \to b

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

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

\rm A \to BAB | B | \varepsilon

\rm B \to 00 | \varepsilon

1 . 添加新的开始变元 :

\rm S_0

;

\rm S_0 \to A

\rm A \to BAB | B | \varepsilon

\rm B \to 00 | \varepsilon

2 . 消除

\rm B \to \varepsilon

规则 : 根据消除前后等价原则 , 重新构造含有

\rm B

的规则 , 即添加使用

\varepsilon

替换

\rm B

的各种情况 , 如 :

\rm BAB

, 替换

1

个

\rm B

两种情况 , 替换

2

个

\rm B

一种情况 ;

\rm S_0 \to A

\rm A \to BAB | BA | AB | A | B | \varepsilon

\rm B \to 00

3 . 消除

\rm A \to \varepsilon

规则 : 根据消除前后等价原则 , 重新构造含有

\rm A

的规则 , 如 :

\rm BAB

如果

\rm A

为空就是

\rm BB

,

\rm AB

如果

\rm A

为空 , 多出一个

\rm B

;

\rm S_0 \to A

\rm A \to BAB | BA | AB | A | B | BB

\rm B \to 00

4 . 消除

\rm A \to B

规则 : 找

\rm B

出现在左边的情况 , 发现有

\rm B \to 00

规则 , 直接使用

\rm A \to 00

规则替换

\rm A \to B

规则 ; ( 注意 :

\rm B \to 00

规则不变 )

\rm S_0 \to A

\rm A \to BAB | BA | AB | A | 00 | BB

\rm B \to 00

5 . 消除

\rm S_0 \to A

规则 : 找

\rm A

出现在左边的情况 , 发现有

\rm A \to BAB | BA | AB | A | 00 | BB

规则 , 直接使用

\rm S_0 \to BAB | BA | AB | A | 00 | BB

规则替换

\rm S_0 \to A

规则 ; ( 注意

\rm A \to BAB | BA | AB | A | 00 | BB

规则规则不变 )

\rm S_0 \to BAB | BA | AB | A | 00 | BB

\rm A \to BAB | BA | AB | A | 00 | BB

\rm B \to 00

6 . 添加变元 : 添加新规则

\rm R \to BA

; 目的是使用

2

个变元的规则替换

3

个变元的规则 ;

\rm S_0 \to RB | BA | AB | A | 00 | BB

\rm A \to RB | BA | AB | A | 00 | BB

\rm B \to 00

\rm R \to BA

7 . 添加变元 : 添加新规则

\rm C \to 0

; 目的是将

\rm B \to 00

中的

2

个终端字符转为两个变元 ;

\rm S_0 \to RB | BA | AB | A | CC | BB

\rm A \to RB | BA | AB | A | CC | BB

\rm B \to CC

\rm R \to BA

\rm C \to 0

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-12-20，如有侵权请联系 cloudcommunity@tencent.com 删除

博客

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度