如何将上下文无关文法转换为下推自动机？

上下文无关文法 (CFG) 由一组有限的语法规则组成，是一个四元组 **(V, T, P, S)**，其中：

• V 是变量（非终结符）。

• T 是一组终结符。

• P 是一组规则，P: V→ (V ∪ T)*，即产生式规则 P 的左侧没有任何右上下文或左上下文。

• S 是起始符号。

下推自动机

下推自动机 (PDA) 包含以下内容：

• 一组有限的非空状态，用 Q 表示。

• 一组有限的非空输入符号，用 ∑ 表示。

• 一组有限的非空下推符号 ┌。

• 一个特殊的初始状态，用 q0 表示。

• 一个特殊的符号，称为下推存储上的初始符号，用 Z0 表示。

• Q 的最终子集，用 F 表示。

• 转移函数 ∂= QX(∑U{^})X┌ 到 QX┌* 的有限子集。

示例

CFG 如下：

S->aSa

S->aSa

S->c

设计一个下推自动机来接受字符串

要将 CFG 转换为 PDA，首先编写产生式规则，然后弹出。

转换规则如下：

• S(q0, ɛ, ɛ)=(q0, ɛ)

• S(q0, ɛ,S)=(q0,aSa)

• S(q0, ɛ,S)=(q0,bsb)

• (q0, ɛ,S)=(q0,c)

现在开始弹出转换

• S(q0,a,a)=(q1, ɛ)

• S(q1,b,b)=(q2, ɛ)

• S(q2,c,c)=(q3, ɛ)

转移表

将 CFG 转换为 PDA 的转移表如下：

当使用 PDA 达到最终状态时，可以说上下文无关文法已转换为下推自动机。

Bhanu Priya

更新于：2021年6月16日

16K+ 浏览量

启动你的职业生涯

完成课程获得认证

开始学习