如何将上下文无关语法转换为下推自动机？
由有限语法规则集组成的上下文无关文法(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达到最终状态时，我们就可以说上下文无关语法转换为下推自动机。