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

Определение:

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

Лемма (об удалении терминалов):

Для любой грамматики 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]