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

2023-03-28 20:11:36 浏览数 (1)

文章目录

  • 一、上下文无关文法 ( CFG )
  • 二、上下文无关文法 ( CFG ) 示例
  • 三、确定性有限自动机 DFA 转为 上下文无关语法 CFG

参考博客 :

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

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

上下文无关语法 组成 : 由

{ quad V , Sigma , R , S quad }

四部分组成 ;

变量集

V

: 有限的变量集合 ;

终端字符集

Sigma

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

规则集

R

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

开始变量

S

: 该变量作为开始变量 ;

规则 :

① 已知条件 : 假设

u, v , w

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

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

A to w

,

A

是变元 ,

w

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

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

A to w

规则进行替换 , 只需要将

A

变元替换成

w

字符串即可 ;

④ 规则示例 :

uAv

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

A

替换成

w

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

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

状态下 , 读取字符

a

, 跳转到

q_j

状态 ;

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

A

读取

1

字符 转化成

B

状态 , 表示成规则就是

R_A to 1R_B

3 . 自动机的状态

A

读取 字符

a

转换成另一个状态

B

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

R_A to aR_B

;

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

变量 集合 语法 终端 字符串

0 人点赞