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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «Грамматика представлена в нормальной форме Куроды (англ. Kuroda normal form), если каждое правил...»)
 
Строка 1: Строка 1:
−
Грамматика представлена в нормальной форме Куроды (англ.  Kuroda normal form), если каждое правило имеет одну из четырех форм:
+
{{Определение
 +
|definition=Грамматика представлена в '''нормальной форме Куроды''' (англ.  ''Kuroda normal form''), если каждое правило имеет одну из четырех форм:
 
# AB->CD
 
# AB->CD
 
# A->BC
 
# A->BC
Строка 5: Строка 6:
 
# A->a или A->\varepsilon
 
# A->a или A->\varepsilon
 
Где A, B, C, D {{---}} нетерминалы, a {{---}} терминал.
 
Где A, B, C, D {{---}} нетерминалы, a {{---}} терминал.
 +
}}
  
 
Данная грамматика названа в честь Куроды (англ. Sige-Yuki Kuroda), который изначально назвал ее линейно ограниченной грамматикой.
 
Данная грамматика названа в честь Куроды (англ. Sige-Yuki Kuroda), который изначально назвал ее линейно ограниченной грамматикой.
  
−
Грамматика представлена в нормальной форме Пенттонена (англ Penttonen normal form), если каждое правило имеет одну из трех форм:
+
{{Определение
 +
|definition=Грамматика представлена в '''нормальной форме Пенттонена''' (англ. ''Penttonen normal form''), если каждое правило имеет одну из трех форм:
 
# AB->CD
 
# AB->CD
 
# A->BC
 
# A->BC
 
# A->a или A->\varepsilon
 
# A->a или A->\varepsilon
 
Где A, B, C, D {{---}} нетерминалы, a {{---}} терминал.
 
Где A, B, C, D {{---}} нетерминалы, a {{---}} терминал.
 +
}}
  
 
Также грамматику Пенттонена называют односторонней нормальной формой (англ. one-sided normal form). Как можно заметить, она является частным случаем нормальной формы Куроды: когда A = C в первом правиле определения.
 
Также грамматику Пенттонена называют односторонней нормальной формой (англ. one-sided normal form). Как можно заметить, она является частным случаем нормальной формы Куроды: когда A = C в первом правиле определения.
 
Для каждой контестно-зависимой грамматики существует слабо эквивалентная ей грамматика в форме Пенттонена.  
 
Для каждой контестно-зависимой грамматики существует слабо эквивалентная ей грамматика в форме Пенттонена.  
  
−
Лемма 1. (Удаление терминалов)
+
{{Лемма
−
Для любой грамматики G = (N, T, P, S) может быть построена грамматика G' = (N', T, P', S) такая, что:
+
|about=об удалении терминалов
 +
|statement = Для любой грамматики 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,
 
* все правила в P' имеет вид \alpha \rightarrow \beta где \alpha \in (N')^+ и \beta \in (N')^* или A \rightarrow a, где A \in N', a \in T,
 
* L(G') = L(G)
 
* L(G') = L(G)
 
Кроме того, если G контекстно-свободна или контекстно-зависима, то и G' будет соответственно контекстно-свободной или контекстно-зависимой.
 
Кроме того, если G контекстно-свободна или контекстно-зависима, то и G' будет соответственно контекстно-свободной или контекстно-зависимой.
  
−
Доказательство.
+
|proof = Каждому терминалу a поставим в соотвествие новый символ a', которого нет в N U T, такой что a' != b' для разных терминалов a и b.
−
 
 
−
Каждому терминалу a поставим в соотвествие новый символ a', которого нет в N U T, такой что a' != b' для разных терминалов a и b.
 
 
Пусть N' = N U \{a' | a \in T\}
 
Пусть 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.
 
Пусть \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.
Строка 48: Строка 51:
 
Таким образом, L(G') = L(G).
 
Таким образом, L(G') = L(G).
 
Очевидно, что если грамматика была неукорочивающейся, то она такой и останется.
 
Очевидно, что если грамматика была неукорочивающейся, то она такой и останется.
 +
}}
  
−
 
+
{{Лемма
−
Лемма 2. (Удаление длинных правил)
+
|about=об удалении длинных правил
−
Для любой грамматики G = (N, T, P, S) может быть построена грамматика  G' = (N', T, P', S) такая, что:
+
|statement= Для любой грамматики G = (N, T, P, S) может быть построена грамматика  G' = (N', T, P', S) такая, что:
 
* любое правило из P' имеет вид:  
 
* любое правило из P' имеет вид:  
 
   \alpha \rightarrow \beta, где \alpha \in (N')^+ и \beta \in (N')^+ и |\alpha| <= |\beta|
 
   \alpha \rightarrow \beta, где \alpha \in (N')^+ и \beta \in (N')^+ и |\alpha| <= |\beta|
Строка 57: Строка 61:
 
   или A \rightarrow \varepsilon, где A \in N' и a \in T
 
   или A \rightarrow \varepsilon, где A \in N' и a \in T
 
* L(G') = L(G)
 
* L(G') = L(G)
−
 
+
|proof=
−
Доказательство.
 
 
Сначала по G построим грамматику G'' = (N'', T, P'', S), как в доказательстве леммы 1. По G'' построим грамматику G', в которой:
 
Сначала по G построим грамматику G'' = (N'', T, P'', S), как в доказательстве леммы 1. По G'' построим грамматику G', в которой:
 
N' = N'' U {D}, где D {{---}} новый символ,
 
N' = N'' U {D}, где D {{---}} новый символ,
Строка 67: Строка 70:
 
Заметим, что замена правила \alpha \rightarrow \beta на \alpha \rightarrow \betaD^{|\alpha| - |\beta|} не меняет язык грамматики, потому что дополнительная буква D запрещается при добавлении перехода D \rightarrow \varepsilon, а других правил для D нет.
 
Заметим, что замена правила \alpha \rightarrow \beta на \alpha \rightarrow \betaD^{|\alpha| - |\beta|} не меняет язык грамматики, потому что дополнительная буква D запрещается при добавлении перехода D \rightarrow \varepsilon, а других правил для D нет.
 
Тогда получаем, что L(G) <= L(G'), аналогично обратные изменения не меняют язык, то есть L(G') <= L(G).
 
Тогда получаем, что L(G) <= L(G'), аналогично обратные изменения не меняют язык, то есть L(G') <= L(G).
 +
}}
  
 +
{{Определение
 +
|definition=Грамматика имеет '''порядок n''', если |\alpha| <= n и |\beta| <= n для любого ее правила \alpha \rightarrow \beta.
 +
}}
  
  
−
Определение.
+
{{Лемма
−
Грамматика имеет порядок n, если |\alpha| <= n и |\beta| <= n для любого ее правила \alpha \rightarrow \beta.
+
|about=об уменьшении порядка грамматики
−
 
+
|statement=(Уменьшение порядка грамматики)
−
 
 
−
Лемма 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 >= 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).
 
может быть построена грамматика  G' = (N', T, P', S) порядка n - 1 такая, что L(G') = L(G).
−
 
+
|proof= Разделим P на три подмножества:
−
Доказательство.
 
−
Разделим P на три подмножества:
 
 
P_1 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| <= 2, |\beta| <= 2 \},
 
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_2 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| >= 2, |\beta| >= 3 \},
Строка 118: Строка 121:
 
который получается из (1) заменой правил P_p на применение p = AB\alpha' \rightarrow CDE\beta \in P. Аналогично, в случае (2) мы можем заменить применение P_p на p. Кроме того, это верно и для применения P_q, где q \in P_3.  
 
который получается из (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).
 
Таким образом, для r \in P_2 U P_3 мы можем заменить все применения P_r на r, то есть получаем вывод w, который состоит только из правил из P. Тогда w \in L(G) и L(G') <= L(G).
 +
}}
  
−
Теорема.
+
{{Теорема
 +
|statement=
 
Любую грамматику G можно преобразовать к грамматике G_K в нормальной форме Куроды, так что L(G) = L(G_K).
 
Любую грамматику G можно преобразовать к грамматике G_K в нормальной форме Куроды, так что L(G) = L(G_K).
−
Доказательство.
+
|proof=
 
По лемме 1 построим из G грамматику G', затем по лемме 2 построим из G' грамматику G'', Тогда G'' удовлетворит требованиям леммы 3.
 
По лемме 1 построим из G грамматику G', затем по лемме 2 построим из G' грамматику G'', Тогда G'' удовлетворит требованиям леммы 3.
 
Пусть G'' имеет порядок n. Нсли n = 2, то G'' в нормальной форме Куроды и G_K = G''. Если n >= 3, построим G''' порядка n - 1 из G'' по лемме 3.
 
Пусть G'' имеет порядок n. Нсли n = 2, то G'' в нормальной форме Куроды и G_K = G''. Если n >= 3, построим G''' порядка n - 1 из G'' по лемме 3.
 
Понятно, что G''' удовлетворяет условиям леммы 3, будем повторять процесс, пока не получим грамматику порядка 2, которую и примем за G_K.
 
Понятно, что G''' удовлетворяет условиям леммы 3, будем повторять процесс, пока не получим грамматику порядка 2, которую и примем за G_K.
 +
}}

Версия 12:57, 4 января 2015

Определение:
Грамматика представлена в нормальной форме Куроды (англ. 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 в первом правиле определения. Для каждой контестно-зависимой грамматики существует слабо эквивалентная ей грамматика в форме Пенттонена.

Лемма (об удалении терминалов):
Для любой грамматики 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' будет соответственно контекстно-свободной или контекстно-зависимой.
Доказательство:
[math]\triangleright[/math]

Каждому терминалу a поставим в соотвествие новый символ a', которого нет в N U T, такой что a' != b' для разных терминалов a и b.

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

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

P' получаем из P заменой всех правил вида \alpha \rightarrow \beta \in P, где
[math]\triangleleft[/math]


Определение:
Грамматика имеет порядок n, если


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

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

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

По лемме 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.
[math]\triangleleft[/math]
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Нормальная_форма_Куроды&oldid=43350»