自动机CFG到PDA的转换

R.H.S.上的第一个符号生产必须是终端符号。以下步骤用于从CFG获取PDA:
步骤1:将给定的CFG生产转换为GNF。
步骤2:PDA仅具有一种状态{q}。
步骤3:CFG的初始符号将成为PDA中的初始符号。
步骤4:对于非终端符号,添加以下规则:

δ(q, ε, A) = (q, α)

生产规则为A→α
步骤5:对于每个终端符号,添加以下规则:
δ(q, a, a) = (q, ε) for every terminal symbol

范例1:
将以下语法转换为接受相同语言的PDA。
S → 0S1 | A A → 1A0 | S | ε

解:
首先可以通过消除单元生产来简化CFG:
S → 0S1 | 1S0 |ε

现在,我们将此CFG转换为GNF:
S → 0SX | 1SY |ε X → 1 Y → 0

PDA可以是:
R1: δ(q, ε, S) = {(q, 0SX) | (q, 1SY) | (q, ε)} R2: δ(q, ε, X) = {(q, 1)} R3: δ(q, ε, Y) = {(q, 0)} R4: δ(q, 0, 0) = {(q, ε)} R5: δ(q, 1, 1) = {(q, ε)}

范例2:
为给定的CFG构造PDA,并测试该PDA是否接受0104。
S → 0BB B → 0S | 1S | 0

解:
PDA可以表示为:
A = {(q), (0, 1), (S, B, 0, 1), δ, q, S, ?}

生产规则δ可以是:
R1: δ(q, ε, S) = {(q, 0BB)} R2: δ(q, ε, B) = {(q, 0S) | (q, 1S) | (q, 0)} R3: δ(q, 0, 0) = {(q, ε)} R4: δ(q, 1, 1) = {(q, ε)}

针对PDA测试0104,即010000:
δ(q, 010000, S) ? δ(q, 010000, 0BB) ? δ(q, 10000, BB)R1 ? δ(q, 10000, 1SB)R3 ? δ(q, 0000, SB)R2 ? δ(q, 0000, 0BBB)R1 ? δ(q, 000, BBB)R3 ? δ(q, 000, 0BB)R2 ? δ(q, 00, BB)R3 ? δ(q, 00, 0B)R2 ? δ(q, 0, B)R3 ? δ(q, 0, 0)R2 ? δ(q, ε)R3 ACCEPT

因此,PDA接受0104。
范例3:
为以下给出的CFG绘制PDA:
S → aSb S → a | b | ε

解:
PDA可以表示为:
P = {(q), (a, b), (S, a, b, z0), δ, q, z0, q}

映射函数δ将为:
R1: δ(q, ε, S) = {(q, aSb)} R2: δ(q, ε, S) = {(q, a) | (q, b) | (q, ε)} R3: δ(q, a, a) = {(q, ε)} R4: δ(q, b, b) = {(q, ε)} R5: δ(q, ε, z0) = {(q, ε)}

【自动机CFG到PDA的转换】模拟:考虑字符串aaabb
δ(q, εaaabb, S) ? δ(q, aaabb, aSb)R3 ? δ(q, εaabb, Sb)R1 ? δ(q, aabb, aSbb)R3 ? δ(q, εabb, Sbb)R2 ? δ(q, abb, abb)R3 ? δ(q, bb, bb)R4 ? δ(q, b, b)R4 ? δ(q, ε, z0)R5 ? δ(q, ε) ACCEPT

    推荐阅读