Нормальная форма Куроды — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 90: Строка 90:
 
|about=об уменьшении порядка грамматики
 
|about=об уменьшении порядка грамматики
 
|statement=(Уменьшение порядка грамматики)
 
|statement=(Уменьшение порядка грамматики)
Для любой грамматики <tex>G = (N, T, P, S)</tex> порядка <tex>n >= 3</tex>, такой что: любое правило из <tex>P'</tex> имеет вид <tex>\alpha \rightarrow \beta</tex>, где <tex>\alpha \in (N')^+</tex> и <tex>\beta \in (N')^+</tex> и <tex>|\alpha| \leqslant |\beta|</tex> или <tex>A \rightarrow a</tex> или <tex>A \rightarrow \varepsilon</tex>, где <tex>A \in N'</tex> и <tex>a \in T</tex> может быть построена грамматика  <tex>G' = (N', T, P', S)</tex> порядка <tex>n - 1</tex> такая, что <tex>L(G') = L(G)</tex>.
+
Для любой грамматики <tex>G = (N, T, P, S)</tex> порядка <tex>n \geqslant 3</tex>, такой что: любое правило из <tex>P'</tex> имеет вид <tex>\alpha \rightarrow \beta</tex>, где <tex>\alpha \in (N')^+</tex> и <tex>\beta \in (N')^+</tex> и <tex>|\alpha| \leqslant |\beta|</tex> или <tex>A \rightarrow a</tex> или <tex>A \rightarrow \varepsilon</tex>, где <tex>A \in N'</tex> и <tex>a \in T</tex> может быть построена грамматика  <tex>G' = (N', T, P', S)</tex> порядка <tex>n - 1</tex> такая, что <tex>L(G') = L(G)</tex>.
 
|proof=  
 
|proof=  
 
Разделим <tex>P</tex> на три подмножества:
 
Разделим <tex>P</tex> на три подмножества:
 +
 
<tex>P_1 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| \leqslant 2, |\beta| \leqslant 2 \}</tex>,
 
<tex>P_1 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| \leqslant 2, |\beta| \leqslant 2 \}</tex>,
  
<tex>P_2 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| >= 2, |\beta| >= 3 \}</tex>,
+
<tex>P_2 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| \geqslant 2, |\beta| \geqslant 3 \}</tex>,
  
<tex>P_3 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| = 1, |\beta| >= 3 \}</tex>.
+
<tex>P_3 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| = 1, |\beta| \geqslant 3 \}</tex>.
  
 
Очевидно, что <tex>P = P_1 \cup P_2 \cup P_3</tex>.
 
Очевидно, что <tex>P = P_1 \cup P_2 \cup P_3</tex>.
Строка 152: Строка 153:
 
Пусть <tex>G''</tex> имеет порядок <tex>n</tex>.  
 
Пусть <tex>G''</tex> имеет порядок <tex>n</tex>.  
 
Если <tex>n = 2</tex>, то <tex>G''</tex> в нормальной форме Куроды и <tex>G_K = G''</tex>.  
 
Если <tex>n = 2</tex>, то <tex>G''</tex> в нормальной форме Куроды и <tex>G_K = G''</tex>.  
Если <tex>n >= 3</tex>, построим <tex>G'''</tex> порядка <tex>n - 1</tex> из <tex>G''</tex> по лемме 3.
+
Если <tex>n \geqslant 3</tex>, построим <tex>G'''</tex> порядка <tex>n - 1</tex> из <tex>G''</tex> по лемме 3.
 
Понятно, что <tex>G'''</tex> удовлетворяет условиям леммы 3.  
 
Понятно, что <tex>G'''</tex> удовлетворяет условиям леммы 3.  
 
Будем повторять процесс, пока не получим грамматику порядка <tex>2</tex>, которую и примем за <tex>G_K</tex>.
 
Будем повторять процесс, пока не получим грамматику порядка <tex>2</tex>, которую и примем за <tex>G_K</tex>.
 
}}
 
}}

Версия 14:18, 4 января 2015

Определение:
Грамматика представлена в нормальной форме Куроды (англ. Kuroda normal form), если каждое правило имеет одну из четырех форм:
  1. [math]AB \rightarrow CD[/math]
  2. [math]A \rightarrow BC[/math]
  3. [math]A \rightarrow B[/math]
  4. [math]A \rightarrow a[/math] или [math]A \rightarrow \varepsilon[/math]
Где [math]A, B, C, D[/math] — нетерминалы, [math]a[/math] — терминал.


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


Определение:
Грамматика представлена в нормальной форме Пенттонена (англ. Penttonen normal form), если каждое правило имеет одну из трех форм:
  1. [math]AB \rightarrow CD[/math]
  2. [math]A \rightarrow BC[/math]
  3. [math]A \rightarrow a[/math] или [math]A \rightarrow \varepsilon[/math]
Где [math]A, B, C, D [/math] — нетерминалы, [math]a[/math] — терминал.


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

Лемма (об удалении терминалов):
Для любой грамматики [math]G = (N, T, P, S)[/math] может быть построена грамматика [math]G' = (N', T, P', S)[/math] такая, что:
  • все правила в [math]P'[/math] имеет вид [math]\alpha \rightarrow \beta[/math] где [math]\alpha \in (N')^+[/math] и [math]\beta \in (N')^*[/math] или [math]A \rightarrow a[/math], где [math]A \in N', a \in T[/math],
  • [math]L(G') = L(G)[/math]
Кроме того, если G контекстно-свободна или контекстно-зависима, то и [math]G'[/math] будет соответственно контекстно-свободной или контекстно-зависимой.
Доказательство:
[math]\triangleright[/math]

Каждому терминалу [math]a[/math] поставим в соотвествие новый символ [math]a'[/math], которого нет в [math]N \cup T[/math], такой что [math]a' \neq b'[/math] для разных терминалов [math]a[/math] и [math]b[/math].

Пусть [math]N' = N \cup \{a' : a \in T\}[/math].

Пусть [math]\alpha = x_1x_2...x_n[/math] — часть правила, тогда [math]\alpha' = y_1y_2...y_n[/math], где [math]y_i = \{x_i[/math], если [math]x_i \in N[/math]; [math]x_i'[/math], если [math]x_i \in T\}[/math] для [math]1 \leqslant i \leqslant n[/math].

Построим грамматику [math]G' = (N', T, P', S)[/math], где [math]P' = \{\alpha' \rightarrow \beta' : \alpha \rightarrow \beta \in P\} \cup \{a' \rightarrow a: a \in T\}[/math].

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

Пусть [math]w \in L(G)[/math]. Тогда в G существует вывод [math]S = w_0 \Rightarrow w_1 \Rightarrow ... \Rightarrow w_n \Rightarrow w[/math].

Согласно конструкции [math]P'[/math], в [math]G'[/math] существует вывод [math]S = w_0' \Rightarrow w_1' \Rightarrow w_2' \Rightarrow ... \Rightarrow w_n' = v_0 \Rightarrow v_1 \Rightarrow v_2 \Rightarrow ... \Rightarrow v_m = w[/math].

Для [math]0 \leqslant i \leqslant n - 1[/math] в переходах [math]w_i' \Rightarrow w_{i + 1}'[/math] используем правило [math]\alpha' \rightarrow \beta'[/math], так как правило [math]\alpha \rightarrow \beta[/math] было использовано при выводе [math]w_i \Rightarrow w_{i + 1}[/math].

Для [math]0 \leqslant j \leqslant m - 1[/math] в переходах [math]v_j \Rightarrow v_{j + 1}[/math] используем правила вида [math]a' \rightarrow a[/math].

Заменяем разрешенные в [math]w'[/math] символы на новые и получаем, что [math]w \in L(G')[/math]. Тогда [math]L(G) \lt = L(G')[/math].

Пусть [math]x \in L(G')[/math]. Тогда в [math]G'[/math] существует вывод [math]S \Rightarrow^* x[/math]. Мы можем поменять порядок применения правил в этом выводе: сначала применяем только правила вида [math]\alpha' \rightarrow \beta'[/math], а потом только правила вида [math]a' \rightarrow a[/math].

Из построения: после применения правила вида [math]a' \rightarrow a[/math] полученное [math]a[/math] не может быть использовано при применении правил из [math]P'[/math].

Изменение порядка вывода не меняет язык, то есть в [math]G'[/math] существует вывод: [math]S = x_0' \Rightarrow x_1' \Rightarrow ... \Rightarrow x_r' \Rightarrow x' \Rightarrow y_1 \Rightarrow y_2 \Rightarrow ... \Rightarrow y_s = x[/math], где для [math]0 \leqslant i \leqslant r - 1 x_{i + 1}' \in (N')^*[/math] и в переходе [math]x_i' \rightarrow x_{i + 1}'[/math] было использовано правило вывода [math]\alpha' \rightarrow \beta'[/math] и для [math]1 \leqslant j \leqslant s[/math] было использовано правило [math]a' \rightarrow a[/math], чтобы получить [math]y_j \rightarrow y_{j + 1}[/math].

Получаем вывод в [math]G[/math]: [math]S = x_0 \Rightarrow x_1 \Rightarrow ... \Rightarrow x_n = x[/math].

Тогда [math]L(G') \lt = L(G)[/math].

Таким образом, [math]L(G') = L(G)[/math].

Очевидно, что если грамматика была неукорочивающейся, то она такой и останется.
[math]\triangleleft[/math]
Лемма (об удалении длинных правил):
Для любой грамматики [math]G = (N, T, P, S)[/math] может быть построена грамматика [math]G' = (N', T, P', S)[/math] такая, что:
  • любое правило из [math]P'[/math] имеет вид: [math]\alpha \rightarrow \beta[/math], где [math]\alpha \in (N')^+[/math] и [math]\beta \in (N')^+[/math] и [math]|\alpha| \leqslant |\beta|[/math], или [math]A \rightarrow a[/math], или [math]A \rightarrow \varepsilon[/math], где [math]A \in N'[/math] и [math]a \in T[/math]
  • [math]L(G') = L(G)[/math]
Доказательство:
[math]\triangleright[/math]

Сначала по [math]G[/math] построим грамматику [math]G'' = (N'', T, P'', S)[/math], как в доказательстве леммы 1. По [math]G''[/math] построим грамматику [math]G'[/math], в которой:

  • [math]N' = N'' \cup \{D\}[/math], где [math]D[/math] — новый символ,
  • [math]P'[/math] получаем из [math]P''[/math] заменой всех правил вида [math]\alpha \rightarrow \beta \in P''[/math], где [math]|\alpha| \gt |\beta|[/math] на правила вида [math]\alpha \rightarrow \beta D^{|\alpha| - |\beta|}[/math], и добавлением правила [math]D \rightarrow \varepsilon[/math].

Теперь все правила в [math]P'[/math] имеет требуемую форму.

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

Заметим, что замена правила [math]\alpha \rightarrow \beta[/math] на [math]\alpha \rightarrow \beta D^{|\alpha| - |\beta|}[/math] не меняет язык грамматики, потому что дополнительная буква [math]D[/math] запрещается при добавлении перехода [math]D \rightarrow \varepsilon[/math], а других правил для [math]D[/math] нет.

Тогда получаем, что [math]L(G) \lt = L(G')[/math], аналогично обратные изменения не меняют язык, то есть [math]L(G') \lt = L(G)[/math].
[math]\triangleleft[/math]


Определение:
Грамматика имеет порядок n, если [math]|\alpha| \leqslant n[/math] и [math]|\beta| \leqslant n[/math] для любого ее правила [math]\alpha \rightarrow \beta[/math].


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

Разделим [math]P[/math] на три подмножества:

[math]P_1 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| \leqslant 2, |\beta| \leqslant 2 \}[/math],

[math]P_2 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| \geqslant 2, |\beta| \geqslant 3 \}[/math],

[math]P_3 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| = 1, |\beta| \geqslant 3 \}[/math].

Очевидно, что [math]P = P_1 \cup P_2 \cup P_3[/math].

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

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

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

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

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

Тогда [math]N' = N \bigcup_{p \in (P_2 \cup P_3)} N_p[/math], [math]P' = P_1 \bigcup_{p \in (P_2 \cup P_3)} P_p[/math].

Из построения очевидно, что [math]G'[/math] имеет порядок [math]n - 1[/math].

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

Сначала докажем, что [math]L(G) \lt = L(G')[/math]. Это следует из того, что:

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

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

Чтобы показать обратное включение, рассмотрим вывод [math]w \in L(G')[/math] в [math]G'[/math], который содержит применение правил вида [math]AB \rightarrow A_pB_p[/math] для какого-то правила [math]p = AB\alpha' \rightarrow CDE\beta' \in P_2[/math]. Заметим, что другие два правила из [math]P_p[/math] могут быть применены только если правило [math]AB \rightarrow A_pB_p[/math] было применено в этом выводе ранее.

Данный вывод имеет вид (1) : [math]S \Rightarrow^* \gamma_1AB\alpha'\gamma_2 \Rightarrow \gamma_1A_pB_p\alpha'\gamma_2 \Rightarrow^q_1 \gamma_1'A_pB_p\alpha'\gamma_2' \Rightarrow \gamma_1'CB_p\alpha'\gamma_2' \Rightarrow^q_2 \gamma_1''B_p\alpha'\gamma_2'' \Rightarrow \gamma_1''DE\beta'\gamma_2'' \Rightarrow^* w \in T^*[/math],

где [math]q_1[/math] — последовательность правил, примененых после [math]AB \rightarrow A_pB_p[/math] и до [math]A_p \rightarrow C[/math], которая осуществляет [math]\gamma_1 \Rightarrow^* \gamma_1'[/math] и [math]\gamma_2 \Rightarrow^* \gamma_2'[/math],

где [math]q_2[/math] — последовательность правил, осуществляющих [math]\gamma_1'C \Rightarrow^* \gamma_1''[/math] и [math]\gamma_2' \Rightarrow^* \gamma_2''[/math].

Или вид (2) : [math]S \Rightarrow^* \gamma_1AB\alpha'\gamma_2 \Rightarrow \gamma_1A_pB_p\alpha'\gamma_2 \Rightarrow^{q_1}' \gamma_1'A_pB_p\alpha'\gamma_2' \Rightarrow \gamma_1'A_pDE\beta'\alpha'\gamma_2' \Rightarrow^{q_2'} \gamma_1''A_p\gamma_2'' \Rightarrow \gamma_1''C\gamma_2'' \Rightarrow^* w \in T^*[/math],

где [math]q_1'[/math] — последовательность правил, которая осуществляет [math]\gamma_1 \Rightarrow^* \gamma_1'[/math] и [math]\gamma_2 \Rightarrow^* \gamma_2'[/math],

где [math]q_2'[/math] — последовательность правил, осуществляющих [math]\gamma_1' \Rightarrow^* \gamma_1''[/math] и [math]DE\beta'\gamma_2' \Rightarrow^* \gamma_2''[/math].

Таким образом, существует вывод: [math]S \Rightarrow^* \gamma_1AB\alpha'\gamma_2 \Rightarrow \gamma_1CDE\beta'\gamma_2 \Rightarrow^{q_1} \gamma_1'CDE\beta'\gamma_2' \Rightarrow^{q_2} \gamma_1''DE\beta'\gamma_2'' \Rightarrow^* w \in T^*[/math], который получается из (1) заменой правил [math]P_p[/math] на применение [math]p = AB\alpha' \rightarrow CDE\beta \in P[/math]. Аналогично, в случае (2) мы можем заменить применение [math]P_p[/math] на [math]p[/math]. Кроме того, это верно и для применения [math]P_q,[/math] где [math]q \in P_3[/math].

Таким образом, для [math]r \in P_2 \cup P_3[/math] мы можем заменить все применения [math]P_r[/math] на [math]r[/math], то есть получаем вывод [math]w[/math], который состоит только из правил из [math]P[/math].

Тогда [math]w \in L(G)[/math] и [math]L(G') \lt = L(G)[/math].
[math]\triangleleft[/math]
Теорема:
Любую грамматику [math]G[/math] можно преобразовать к грамматике [math]G_K[/math] в нормальной форме Куроды так, что [math]L(G) = L(G_K)[/math].
Доказательство:
[math]\triangleright[/math]

По лемме 1 построим из [math]G[/math] грамматику [math]G'[/math], затем по лемме 2 построим из [math]G'[/math] грамматику [math]G''[/math], Тогда [math]G''[/math] удовлетворит требованиям леммы 3.

Пусть [math]G''[/math] имеет порядок [math]n[/math]. Если [math]n = 2[/math], то [math]G''[/math] в нормальной форме Куроды и [math]G_K = G''[/math]. Если [math]n \geqslant 3[/math], построим [math]G'''[/math] порядка [math]n - 1[/math] из [math]G''[/math] по лемме 3. Понятно, что [math]G'''[/math] удовлетворяет условиям леммы 3.

Будем повторять процесс, пока не получим грамматику порядка [math]2[/math], которую и примем за [math]G_K[/math].
[math]\triangleleft[/math]