Нормальная форма Куроды

Грамматика представлена в нормальной форме Куроды (англ. Kuroda normal form), если каждое правило имеет одну из четырех форм:

1. AB->CD
2. A->BC
3. A->B
4. A->a или A->\varepsilon

Где A, B, C, D — нетерминалы, a — терминал.

Данная грамматика названа в честь Куроды (англ. Sige-Yuki Kuroda), который изначально назвал ее линейно ограниченной грамматикой.

Грамматика представлена в нормальной форме Пенттонена (англ Penttonen normal form), если каждое правило имеет одну из трех форм:

1. AB->CD
2. A->BC
3. A->a или A->\varepsilon

Где A, B, C, D — нетерминалы, a — терминал.

Также грамматику Пенттонена называют односторонней нормальной формой (англ. one-sided normal form). Как можно заметить, она является частным случаем нормальной формы Куроды: когда A = C в первом правиле определения. Для каждой контестно-зависимой грамматики существует слабо эквивалентная ей грамматика в форме Пенттонена.

Лемма 1. (Удаление терминалов) Для любой грамматики G = (N, T, P, S) может быть построена грамматика G' = (N', T, P', S) такая, что:

• все правила в P' имеет вид \alpha \rightarrow \beta где \alpha \in (N')^+ и \beta \in (N')^* или A \rightarrow a, где A \in N', a \in T,
• L(G') = L(G)

Кроме того, если G контекстно-свободна или контекстно-зависима, то и G' будет соответственно контекстно-свободной или контекстно-зависимой.

Доказательство.

Каждому терминалу a поставим в соотвествие новый символ a', которого нет в N U T, такой что a' != b' для разных терминалов a и b. Пусть N' = N U \{a' | a \in T\} Пусть \alpha = x_1x_2...x_n — часть правила, тогда \alpha' = y_1y_2...y_n, где y_i = {x_i, если x_i \in N; x_i', если x_i \in T} для 1 <= i <= n. Построим грамматику G' = (N', T, P', S), где P' = {\alpha' \rightarrow \beta' : \alpha \rightarrow \beta \in P} U {a' \rightarrow a: a \in T}.

Покажем, что L(G') = L(G).

Пусть w \in L(G). Тогда в G существует вывод S = w_0 => w_1 => ... => w_n => w. Согласно конструкции P', в G' существует вывод S = w_0' => w_1' => w_2' => ... => w_n' = v_0 => v_1 => v_2 => ... => v_m = w. Для 0 <= i <= n - 1 в переходах w_i' => w_{i + 1}' используем правило \alpha' \rightarrow \beta', так как правило \alpha \rightarrow \beta было использовано при выводе w_i => w_{i + 1}. Для 0 <= j <= m - 1 в переходах v_j => v_{j + 1} используем правила вида a' \rightarrow a. Заменяем разрешенные в w' символы на новые и получаем, что w \in L(G'). Тогда L(G) <= L(G').

Пусть x \in L(G'). Тогда в G' существует вывод S =>* x. Мы можем поменять порядок применения правил в этом выводе: сначала только правила вида \alpha' \rightarrow \beta', а потом только правила вида a' \rightarrow a. Из построения: после применения правила вида a' \rightarrow a полученное a не может быть использовано при применении правил из P'. Изменение порядка вывода не меняет язык, то есть в G' существует вывод: S = x_0' => x_1' => ... => x_r' => x' => y_1 => y_2 => ... => y_s = x, где для 0 <= i <= r - 1 x_{i + 1}' \in (N')^* и в переходе x_i' \rightarrow x_{i + 1}' было использовано правило вывода \alpha' \rightarrow \beta' и для 1 <= j <= s было использовано правило a' \rightarrow a, чтобы получить y_j \rightarrow y_{j + 1}. Получаем вывод в G: S = x_0 => x_1 => ... => x_n = x. Тогда L(G') <= L(G). Таким образом, L(G') = L(G). Очевидно, что если грамматика была неукорочивающейся, то она такой и останется.

Лемма 2. (Удаление длинных правил) Для любой грамматики G = (N, T, P, S) может быть построена грамматика G' = (N', T, P', S) такая, что:

• любое правило из P' имеет вид:

 \alpha \rightarrow \beta, где \alpha \in (N')^+ и \beta \in (N')^+ и |\alpha| <= |\beta|
 или A \rightarrow a 
 или A \rightarrow \varepsilon, где A \in N' и a \in T

• L(G') = L(G)

Доказательство. Сначала по G построим грамматику G = (N, T, P, S), как в доказательстве леммы 1. По G построим грамматику G', в которой: N' = N U {D}, где D — новый символ, P' получаем из P заменой всех правил вида \alpha \rightarrow \beta \in P, где |\alpha| > |\beta| на правила вида \alpha \rightarrow \betaD^{|\alpha| - |\beta|}, и добавлением правила D \rightarrow \varepsilon. Теперь все правила в P' имеет требуемую форму.

Покажем, что L(G') = L(G). Заметим, что замена правила \alpha \rightarrow \beta на \alpha \rightarrow \betaD^{|\alpha| - |\beta|} не меняет язык грамматики, потому что дополнительная буква D запрещается при добавлении перехода D \rightarrow \varepsilon, а других правил для D нет. Тогда получаем, что L(G) <= L(G'), аналогично обратные изменения не меняют язык, то есть L(G') <= L(G).

Определение. Грамматика имеет порядок n, если |\alpha| <= n и |\beta| <= n для любого ее правила \alpha \rightarrow \beta.

Лемма 3. (Уменьшение порядка грамматики) Для любой грамматики G = (N, T, P, S) порядка n >= 3, такой что: любое правило из P' имеет вид \alpha \rightarrow \beta, где \alpha \in (N')^+ и \beta \in (N')^+ и |\alpha| <= |\beta| или A \rightarrow a или A \rightarrow \varepsilon, где A \in N' и a \in T может быть построена грамматика G' = (N', T, P', S) порядка n - 1 такая, что L(G') = L(G).

Доказательство. Разделим P на три подмножества: P_1 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| <= 2, |\beta| <= 2 \}, P_2 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| >= 2, |\beta| >= 3 \}, P_3 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| = 1, |\beta| >= 3 \}. Очевидно, что P = P_1 U P_2 U P_3.

Построим G' следующим образом:

• Если правило p \in P_2, то оно имеет вид AB\alpha' \rightarrow CDE\beta', где \alpha' \in N^* и \beta' \in N^*.

Полагаем N_p = \{ A_p, B_p \}, P_p = \{ AB \rightarrow A_pB_p, A_p  \rightarrow C, B_p\alpha' \rightarrow DE\beta'}, где A_p, B_p — дополнительные символы не из N: {A_p, B_p) пересечь {A_q, B_q} = 0 для разных правил p и q из P_2.

• Если правило p \in P_3, то оно имеет вид A \rightarrow CDE\beta', где \beta' \int N^*.

Полагаем N_p = \{B_p \}, P_p = \{A \rightarrow CB_p, B_p \rightarrow DE\beta'\}, где A_p, B_p — дополнительные символы.

Тогда N' = N U (объединение по P из (P_2 U P_3) N_p), P' = P_1 U (объединение по P из (P_2 U P_3) P_p). Из построения очевидно, что G' имеет порядок n - 1.

Покажем, что L(G') = L(G).

Сначала докажем, что L(G) <= L(G'). Это следует из того, что:

• все правила из P_1 применимы к обеим грамматикам,
• шаг вывода \gamma_1AB\alpha'\gamma_2 => \gamma_1CDE\beta'\gamma_2, благодаря правилу p = AB\alpha \rightarrow CDE\beta' \in P_2 в G, может быть использавано в G' с помощью трех шагов:

\gamma_1AB\alpha'\gamma_2 => \gamma_1A_pB_p\alpha'\gamma_2 => \gamma_1CB_p\alpha'\gamma_2 => \gamma_1CDE\beta\gamma_2, с использованием правил из P_p и вывода \gamma_1A\gamma_2 => \gamma_1CDE\beta'\gamma_2 на основе правила p = A\alpha \rightarrow CDE\beta' \in P_3 в G, которое может быть применено в G' с помощью трех шагов вывода: \gamma_1A\alpha1'\gamma_2 => \gamma_1A_pB_p\alpha'\gamma_2 => \gamma_1CB_p\alpha'\gamma_2 => \gamma_1CDE\beta\gamma_2. Таким образом, любой вывод в G может быть преобразован в вывод в G'.

Чтобы показать обратное включение, рассмотрим вывод w \in L(G') в G', который содержит применение правил вида AB \rightarrow A_pB_p для какого-то правила p = AB\alpha' \rightarrow CDE\beta' \in P_2 (Заметим, что другие два правила из P_p могут быть применены только если правило AB \rightarrow A_pB_p было применено в этом выводе ранее). Данный вывод имеет вид: (1) S =>* \gamma_1AB\alpha'\gamma_2 => \gamma_1A_pB_p\alpha'\gamma_2 =>(q_1) \gamma_1'A_pB_p\alpha'\gamma_2' => \gamma_1'CB_p\alpha'\gamma_2' =>(q_2) \gamma_1B_p\alpha'\gamma_2 => \gamma_1DE\beta'\gamma_2 =>* w \in T^*, где q_1 — последовательность правил, примененых после AB \rightarrow A_pB_p и до A_p \rightarrow C, которая осуществляет \gamma_1 =>* \gamma_1' и \gamma_2 =>* \gamma_2', где q_2 — последовательность правил, осуществляющих \gamma_1'C =>* \gamma_1 и \gamma_2' =>* \gamma_2.

Или (2) S =>* \gamma_1AB\alpha'\gamma_2 => \gamma_1A_pB_p\alpha'\gamma_2 =>(q_1') \gamma_1'A_pB_p\alpha'\gamma_2' => \gamma_1'A_pDE\beta'\alpha'\gamma_2' =>(q_2') \gamma_1A_p\gamma_2 => \gamma_1C\gamma_2 =>* w \in T^*, где q_1' — последовательность правил, которая осуществляет \gamma_1 =>* \gamma_1' и \gamma_2 =>* \gamma_2', где q_2' — последовательность правил, осуществляющих \gamma_1' =>* \gamma_1 и DE\beta'\gamma_2' =>* \gamma_2.

Таким образом, существует вывод: S =>* \gamma_1AB\alpha'\gamma_2 => \gamma_1CDE\beta'\gamma_2 => (q_1) \gamma_1'CDE\beta'\gamma_2' => (q_2) \gamma_1DE\beta'\gamma_2 =>* w \in T^*, который получается из (1) заменой правил P_p на применение p = AB\alpha' \rightarrow CDE\beta \in P. Аналогично, в случае (2) мы можем заменить применение P_p на p. Кроме того, это верно и для применения P_q, где q \in P_3. Таким образом, для r \in P_2 U P_3 мы можем заменить все применения P_r на r, то есть получаем вывод w, который состоит только из правил из P. Тогда w \in L(G) и L(G') <= L(G).

Теорема. Любую грамматику G можно преобразовать к грамматике G_K в нормальной форме Куроды, так что L(G) = L(G_K). Доказательство. По лемме 1 построим из G грамматику G', затем по лемме 2 построим из G' грамматику G, Тогда G удовлетворит требованиям леммы 3. Пусть G имеет порядок n. Нсли n = 2, то G в нормальной форме Куроды и G_K = G. Если n >= 3, построим G порядка n - 1 из G по лемме 3. Понятно, что G удовлетворяет условиям леммы 3, будем повторять процесс, пока не получим грамматику порядка 2, которую и примем за G_K.