Изменения

# AB->CD

# A->BC

# A->a или A->\varepsilon

Где A, B, C, D {{---}} нетерминалы, a {{---}} терминал.

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

# AB->CD

# A->BC

# A->a или A->\varepsilon

Где A, B, C, D {{---}} нетерминалы, a {{---}} терминал.

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

Для каждой контестно-зависимой грамматики существует слабо эквивалентная ей грамматика в форме Пенттонена.

* все правила в 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' будет соответственно контекстно-свободной или контекстно-зависимой.

Пусть 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.

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

Очевидно, что если грамматика была неукорочивающейся, то она такой и останется.

* любое правило из P' имеет вид:

\alpha \rightarrow \beta, где \alpha \in (N')^+ и \beta \in (N')^+ и |\alpha| <= |\beta|

или 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 {{---}} новый символ,

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

Тогда получаем, что L(G) <= L(G'), аналогично обратные изменения не меняют язык, то есть L(G') <= L(G).

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

который получается из (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.