如何將上下文無關文法轉換為下推自動機？

上下文無關文法 (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+ 瀏覽量

啟動你的職業生涯

完成課程獲得認證

開始學習