【计算理论】计算理论总结 ( 上下文无关文法 ) ★★

韩曙亮

发布于 2023-03-28 12:11:36

8220

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

文章目录

参考博客 :

一、上下文无关文法 ( CFG )

上下文无关语法组成 : 由

\{ \quad V , \Sigma , R , S \quad \}

四部分组成 ;

变量集

: 有限的变量集合 ;

终端字符集

\Sigma

: 有限的终端字符组成的集合 ; 相当于常量的含义 , 与变量相对 ;

规则集

: 有限的规则组成的集合 , 规则规定如何进行代换操作 , 规定变量 , 终端字符 , 字符串变量等 ;

开始变量

: 该变量作为开始变量 ;

规则 :

① 已知条件 : 假设

u, v , w

是 变量 ( 变元 ) 或 终端字符集 ( 常量 / 常元 ) ;

② 规则描述 : 规则是一个箭头 ,

A \to w

是变元 ,

是变元和常元组成的终端字符 ;

③ 规则用法 : 在字符串中 , 根据

A \to w

规则进行替换 , 只需要将

变元替换成

字符串即可 ;

④ 规则示例 :

uAv

中使用上述规则进行替换 , 将

替换成

, 替换结果是得到新字符串

uwv

;

uAv \Rightarrow uwv

二、上下文无关文法 ( CFG ) 示例

上下文无关文法 ( CFG ) :

\rm G3 =( \; \{ S \}, \{ a, b \}, R , S \; )

其组成如下 :

变量集

\rm \{ S \}

;

终端字符集

\rm \{ a, b \}

;

规则

\rm R

;

开始变量

\rm S

;

规则

\rm R

描述 :

\rm S \to aSb \; | \; SS \; | \; \varepsilon

\rm S

变量可以使用

\rm aSb

字符串替换 ;

\rm S

变量可以使用

\rm SS

字符串替换 ;

\rm S

变量可以使用

\rm \varepsilon

字符串替换 ;

规则替换过程 : 下面的 ① ~ ⑦ 分别对应七次规则替换 ;

\rm S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aaSSbb \Rightarrow aaaSbSbb \Rightarrow aaabSbb \Rightarrow aaabaSbbb \Rightarrow aaababbb

\rm S S

是开始变量 , 可以使用

\rm aSb

替换

\rm S

;

\rm S \Rightarrow aSb

② 使用

\rm aSb

替换

\rm S

;

\rm aSb \Rightarrow aaSbb

③ 使用

\rm SS

替换

\rm S

;

\rm aaSbb \Rightarrow aaSSbb

④ 使用

\rm aSb

替换第一个

\rm S

;

\rm aaSSbb \Rightarrow aaaSbSbb

⑤ 使用

\rm \varepsilon

替换第一个

\rm S

;

\rm aaaSbSbb \Rightarrow aaabSbb

⑥ 使用

\rm aSb

替换

\rm S

;

\rm aaabSbb \Rightarrow aaabaSbbb

⑦ 使用

\rm \varepsilon

替换

\rm S

;

\rm aaabaSbbb \Rightarrow aaababbb

三、确定性有限自动机 DFA 转为上下文无关语法 CFG

1 . 确定性有限自动机 ( DFA ) 转为上下文无关语法 ( CFG ) : 将

确定性有限自动机 ( DFA ) 的指令 , 转为对应的

上下文无关语法 ( CFG ) 规则 :

\rm \delta ( q_i, a ) = q_j \Rightarrow R_i \to aR_j

\delta ( q_i, a ) = q_j

表示

q_i

状态下 , 读取字符

, 跳转到

q_j

状态 ;

2 . 自动机的状态跳转转换成规则示例 : 下图中的确定性有限自动机 , 开始状态

读取

字符转化成

状态 , 表示成规则就是

R_A \to 1R_B

3 . 自动机的状态

读取字符

转换成另一个状态

, 都可以转换成对应的规则

R_A \to aR_B

;

4 . 计算能力对比 : 上下文无关语法的计算能力要大于等于自动机的计算能力 ;

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

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

变量

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

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

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

登录后参与评论

暂无评论