Automata Theory 简明教程
PDA & Context-Free Grammar
如果一个语法 G 是无上下文的,我们可以构建一个等效的非确定性 PDA,它接受由无上下文语法 G 生成的语言。可以为语法 G 构建一个解析器。
If a grammar G is context-free, we can build an equivalent nondeterministic PDA which accepts the language that is produced by the context-free grammar G. A parser can be built for the grammar G.
另外,如果 P 是下推机,则可以构建一个等效的无上下文语法 G,其中
Also, if P is a pushdown automaton, an equivalent context-free grammar G can be constructed where
L(G) = L(P)
L(G) = L(P)
在接下来的两个主题中,我们将讨论如何从 PDA 转换为 CFG,反之亦然。
In the next two topics, we will discuss how to convert from PDA to CFG and vice versa.
Algorithm to find PDA corresponding to a given CFG
Input - 一个 CFG,G = (V, T, P, S)
Input − A CFG, G = (V, T, P, S)
Output − 等价的 PDA,P = (Q, ∑, S, δ, q0, I, F)
Output − Equivalent PDA, P = (Q, ∑, S, δ, q0, I, F)
Step 1 − 将 CFG 的产生式转换成 GNF。
Step 1 − Convert the productions of the CFG into GNF.
Step 2 − PDA 将只有唯一状态 {q}。
Step 2 − The PDA will have only one state {q}.
Step 3 − CFG 的起始符号将是 PDA 中的起始符号。
Step 3 − The start symbol of CFG will be the start symbol in the PDA.
Step 4 − CFG的所有非终结符号将是 PDA 的栈符号,且 CFG 的所有终结符号将是 PDA 的输入符号。
Step 4 − All non-terminals of the CFG will be the stack symbols of the PDA and all the terminals of the CFG will be the input symbols of the PDA.
Step 5 − 对于形式 A → aX 的每个产生式,其中 a 为终结符, A, X 是终结符和非终结符的组合,创建转换 δ (q, a, A) 。
Step 5 − For each production in the form A → aX where a is terminal and A, X are combination of terminal and non-terminals, make a transition δ (q, a, A).
Algorithm to find CFG corresponding to a given PDA
Input - 一个 CFG,G = (V, T, P, S)
Input − A CFG, G = (V, T, P, S)
Output − 等价的 PDA,P = (Q, ∑, S, δ, q0, I, F),其中语法 G 的非终结符为 {Xwx | w,x ∈ Q},开始状态为 Aq0,F。
Output − Equivalent PDA, P = (Q, ∑, S, δ, q0, I, F) such that the non- terminals of the grammar G will be {Xwx | w,x ∈ Q} and the start state will be Aq0,F.
Step 1 − 对于 Q 中的每个 w、x、y、z,S 中的 m 以及 ∑ 中的 a、b,如果 δ (w, a, ε) 包含 (y, m) 且 (z, b, m) 包含 (x, ε) ,则在语法 G 中添加产生式规则 Xwx → a Xyzb。
Step 1 − For every w, x, y, z ∈ Q, m ∈ S and a, b ∈ ∑, if δ (w, a, ε) contains (y, m) and (z, b, m) contains (x, ε), add the production rule Xwx → a Xyzb in grammar G.
Step 2 - 对于任意 Q 中的 w、x、y、z,在语法 G 中添加产生式 Xwx → XwyXyx。
Step 2 − For every w, x, y, z ∈ Q, add the production rule Xwx → XwyXyx in grammar G.
Step 3 - 对于 Q 中的 w,在语法 G 中添加产生式 Xww → ε。
Step 3 − For w ∈ Q, add the production rule Xww → ε in grammar G.