【计算理论】上下文无关语法 ( CFG ) 转为 下推自动机 ( PDA )

发布于

文章目录
  • I . 上下文无关语法 ( CFG ) 转为 下推自动机 ( PDA )
  • II . 下推自动机 ( PDA ) 三个状态
  • III . 下推自动机 ( PDA )
q_{start}

状态

  • IV . 下推自动机 ( PDA )
q_{loop}

状态

  • V . 下推自动机 ( PDA )
q_{accept}

状态

  • VI . 下推自动机 ( PDA ) 指令分解
  • VII . 最终转换成的 下推自动机 ( PDA ) 结果

I . 上下文无关语法 ( CFG ) 转为 下推自动机 ( PDA )

上下文无关语法 ( CFG ) :

S \to aTb | b
T \to Ta|\varepsilon

将上述 上下文无关语法 ( CFG ) 转为 下推自动机 ;

II . 下推自动机 ( PDA ) 三个状态

该 自动机 共包含

3

个状态 ,

q_{start}

,

q_{loop}

,

q_{accept}

, 最后一个状态是 可接受状态 ;

在这里插入图片描述
III . 下推自动机 ( PDA )
q_{start}

状态

1 . 首先在 栈顶 放入

K

字符 , 用于当做栈底的标识 ;

生成指令 :

\varepsilon , \varepsilon \to K

;

开始状态

q_{start}

状态 , 读取

\varepsilon , \varepsilon \to K

指令 , 读取空字符 , 使用

K

替换栈顶的空字符 , 就是将

K

放入栈中 ;

状态跳转 : 之后跳转到

q_{loop}

状态 ;

当前的 下推自动机 ( CFG ) 设计 :

在这里插入图片描述
IV . 下推自动机 ( PDA )
q_{loop}

状态

1 .

q_{loop}

状态下 在栈中模仿 上下文无关语法 ( CFG ) 的规则替换 ;

上下文无关语法 ( CFG ) :

S \to aTb | b
T \to Ta|\varepsilon

2 . 对照上述 上下文无关语法 ( CFG ) , 逐条生成指令 :

①

S \to aTb

对应的指令 :

\varepsilon , S \to aTb

, 读取

\varepsilon

时 , 使用

aTb

替换栈顶的

S

; 即如果栈顶是

S

, 使用

aTb

替换栈顶的

S

;

②

S \to b

对应的指令 :

\varepsilon , S \to b

, 读取

\varepsilon

时 , 使用

b

替换栈顶的

S

; 即如果栈顶是

S

, 使用

b

替换栈顶的

S

;

③

T \to Ta

对应的指令 :

\varepsilon , T \to Ta

, 读取

\varepsilon

时 , 使用

Ta

替换栈顶的

T

; 即如果栈顶是

T

, 使用

Ta

替换栈顶的

T

;

④

T \to \varepsilon

对应的指令 :

\varepsilon , T \to \varepsilon

, 读取

\varepsilon

时 , 使用

\varepsilon

替换栈顶的

T

; 即如果栈顶是

T

, 使用

\varepsilon

替换栈顶的

T

;

⑤ 如果栈上有终端字符

a

, 要将栈里的终端字符

a

移除 , 对应指令是

a , a \to \varepsilon

, 如果读取到字符

a

时 , 从栈顶将字符

a

移除 ;

⑥ 如果栈上有终端字符

b

, 要将栈里的终端字符

b

移除 , 对应指令是

b , b \to \varepsilon

, 如果读取到字符

b

时 , 从栈顶将字符

b

移除 ;

在这里插入图片描述
V . 下推自动机 ( PDA )
q_{accept}

状态

1 .

q_{accept}

状态 :

在

q_{loop}

状态下 , 将栈内的除

K

外所有的字符都移除完毕 , 开始向

q_{accept}

状态跳转 ;

此时需要生成指令

\varepsilon , K \to \varepsilon

, 读取 空字符

\varepsilon

, 使用 空字符

\varepsilon

替换栈顶的

K

字符 , 此时栈清空了 ;

在这里插入图片描述
VI . 下推自动机 ( PDA ) 指令分解

1 . 非法指令分解

上述生成的

\varepsilon , S \to aTb
\varepsilon , T \to Ta

两个指令是不合法的 , 在栈中 , 一个字符 ( 或空字符串

\varepsilon

) 只能由 一个字符 ( 或空字符串

\varepsilon

) 替换 ;

上述不合法的规则 , 多个字符替换栈顶的一个字符 , 需要进行分解操作 ;

2 .

\varepsilon , S \to aTb

指令分解流程 :

①

q_{loop}

状态 跳转到 新的状态

q_{loop1}

, 跳转读取的指令时

\varepsilon , S \to b

, 读取空字符 , 然后使用

b

替换栈顶的

S

字符 ;

在这里插入图片描述

②

q_{loop1}

状态 跳转到 新的状态

q_{loop2}

, 跳转读取的指令时

\varepsilon , \varepsilon \to T

, 读取空字符 , 然后使用

T

替换栈顶的

\varepsilon

字符 , 相当于在栈中放入了

T

字符 ;

在这里插入图片描述

③

q_{loop2}

状态 跳转到 原来的状态

q_{loop}

, 跳转读取的指令时

\varepsilon , \varepsilon \to a

, 读取空字符 , 然后使用

a

替换栈顶的

\varepsilon

字符 , 相当于在栈中放入了

a

字符 ;

在这里插入图片描述

分解

\varepsilon , S \to aTb

后的

3

个指令 :

\varepsilon , S \to b
\varepsilon , \varepsilon \to T
\varepsilon , \varepsilon \to a

上述三个指令都是合法的 , 上述

3

个指令 串联后的效果等价于

\varepsilon , S \to aTb

操作 , 等价于上下文无关语法的

S \to aTb

规则效果 ;

3 .

\varepsilon , T \to Ta

指令分解流程 :

①

q_{loop}

状态 跳转到 新的状态

q_{loop3}

, 跳转读取的指令时

\varepsilon , S \to a

, 读取空字符 , 然后使用

a

替换栈顶的

S

字符 ;

在这里插入图片描述

②

q_{loop3}

状态 跳转到 原来的状态

q_{loop}

, 跳转读取的指令时

\varepsilon , \varepsilon \to T

, 读取空字符 , 然后使用

T

替换栈顶的

\varepsilon

字符 , 相当于在栈中放入了

T

字符 ;

在这里插入图片描述

分解

\varepsilon , T \to Ta

后的

2

个指令 :

\varepsilon , S \to a
\varepsilon , \varepsilon \to T

上述

2

个指令都是合法的 , 上述

2

个指令 串联后的效果等价于

\varepsilon , T \to Ta

指令 , 等价于上下文无关语法的

T \to Ta

规则效果 ;

VII . 最终转换成的 下推自动机 ( PDA ) 结果

最终的 上下文无关语法 ( CFG ) 转为的 下推自动机 ( PDA ) 样式 :

在这里插入图片描述

上下文无关语法 ( CFG ) 与 下推自动机 ( PDA ) 是等价的 , 给定一个 下推自动机 ( PDA ) , 构造 上下文无关语法 ( CFG ) , 该语法生成的语言 , 就是该 下推自动机 ( PDA ) 所认识的语言 ;

#vi#设计#语法#终端#字符串