Изменения
Новая страница: «Грамматика представлена в нормальной форме Куроды (англ. Kuroda normal form), если каждое правил...»
Грамматика представлена в нормальной форме Куроды (англ. Kuroda normal form), если каждое правило имеет одну из четырех форм:
# AB->CD
# A->BC
# A->B
# A->a или A->\varepsilon
Где A, B, C, D {{---}} нетерминалы, a {{---}} терминал.
Данная грамматика названа в честь Куроды (англ. Sige-Yuki Kuroda), который изначально назвал ее линейно ограниченной грамматикой.
Грамматика представлена в нормальной форме Пенттонена (англ Penttonen normal form), если каждое правило имеет одну из трех форм:
# AB->CD
# A->BC
# 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_1''B_p\alpha'\gamma_2'' => \gamma_1''DE\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_1''A_p\gamma_2'' => \gamma_1''C\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_1''DE\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.
# AB->CD
# A->BC
# A->B
# A->a или A->\varepsilon
Где A, B, C, D {{---}} нетерминалы, a {{---}} терминал.
Данная грамматика названа в честь Куроды (англ. Sige-Yuki Kuroda), который изначально назвал ее линейно ограниченной грамматикой.
Грамматика представлена в нормальной форме Пенттонена (англ Penttonen normal form), если каждое правило имеет одну из трех форм:
# AB->CD
# A->BC
# 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_1''B_p\alpha'\gamma_2'' => \gamma_1''DE\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_1''A_p\gamma_2'' => \gamma_1''C\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_1''DE\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.
