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

Материал из Викиконспекты
Перейти к: навигация, поиск
Определение:
Грамматика представлена в нормальной форме Куроды (англ. 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 \lt = i \lt = 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 =\gt w_1 =\gt ... =\gt w_n =\gt w[/math].

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

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

Для [math]0 \lt = j \lt = m - 1[/math] в переходах [math]v_j =\gt 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 =\gt * 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' =\gt x_1' =\gt ... =\gt x_r' =\gt x' =\gt y_1 =\gt y_2 =\gt ... =\gt y_s = x[/math], где для [math]0 \lt = i \lt = r - 1 x_{i + 1}' \in (N')^*[/math] и в переходе [math]x_i' \rightarrow x_{i + 1}'[/math] было использовано правило вывода [math]\alpha' \rightarrow \beta'[/math] и для [math]1 \lt = j \lt = s[/math] было использовано правило [math]a' \rightarrow a[/math], чтобы получить [math]y_j \rightarrow y_{j + 1}[/math].

Получаем вывод в [math]G[/math]: [math]S = x_0 =\gt x_1 =\gt ... =\gt 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| \lt = |\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, если


Лемма (об уменьшении порядка грамматики):
(Уменьшение порядка грамматики) Для любой грамматики 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]