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

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

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

• T 是一组终端。

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

• S 是起始符号。

下推自动机

下推自动机(PDA)包括以下内容 -

• 由 Q 表示的有限非空状态集。

• 由∑表示的有限非空输入符号集。

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

• 一种特殊状态称为初始状态，用 q0 表示。

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

• 由 F 表示的 Q 的最终子集的集合。

• 转换函数∂= 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 达到最终状态时，我们就可以说上下文无关语法转换为下推自动机。