Если грамматика G не зависит от контекста, мы можем создать эквивалентный недетерминированный КПК, который принимает язык, который генерируется не зависящей от контекста грамматикой G. Парсер может быть построен для грамматики G.
Кроме того, если P является автоматом нажатия, может быть построена эквивалентная не зависящая от контекста грамматика G, где
L (G) = L (P)
В следующих двух темах мы обсудим, как перейти с КПК на CFG и наоборот.
Алгоритм нахождения КПК, соответствующего данному КФГ
Вход — A CFG, G = (V, T, P, S)
Выход — эквивалентный КПК, P = (Q, ∑, S, δ, q 0 , I, F)
Шаг 1 — Преобразование производства CFG в GNF.
Шаг 2 — КПК будет иметь только одно состояние {q}.
Шаг 3 — Начальный символ CFG будет начальным символом в КПК.
Шаг 4 — Все нетерминалы CFG будут символами стека КПК, а все терминалы CFG будут входными символами КПК.
Шаг 5 — Для каждого производства в форме A → aX, где a является терминалом, а A, X являются комбинацией терминалов и нетерминалов, выполните переход δ (q, a, A) .
проблема
Построить КПК из следующего CFG.
G = ({S, X}, {a, b}, P, S)
где производства —
S → XS | ε, A → aXb | Ab | аб
Решение
Пусть эквивалентный КПК,
P = ({q}, {a, b}, {a, b, X, S}, δ, q, S)
где δ —
δ (q, ε, S) = {(q, XS), (q, ε)}
δ (q, ε, X) = {(q, aXb), (q, Xb), (q, ab)}
δ (q, a, a) = {(q, ε)}
δ (q, 1, 1) = {(q, ε)}
Алгоритм поиска CFG, соответствующего данному КПК
Вход — A CFG, G = (V, T, P, S)
Вывод — Эквивалентный PDA, P = (Q, ∑, S, δ, q 0 , I, F), такой, что нетерминалы грамматики G будут {X wx | w, x ∈ Q}, и начальное состояние будет A q0, F.
Шаг 1 — Для каждого w, x, y, z ∈ Q, m ∈ S и a, b ∈ ∑, если δ (w, a, ε) содержит (y, m) и (z, b, m) содержит ( x, ε), добавьте правило производства X wx → a X yz b в грамматике G.
Шаг 2 — Для каждого w, x, y, z ∈ Q добавьте правило произведения X wx → X wy X yx в грамматике G.
Шаг 3 — Для w ∈ Q добавьте производное правило X ww → ε в грамматике G.