Изменения

# <tex>AB-\rightarrow CD</tex>CD# <tex>A-\rightarrow BC</tex>BC# <tex>A-\rightarrow B</tex>B# <tex>A-\rightarrow a</tex>a или <tex>A->\rightarrow \varepsilon</tex>Где <tex>A, B, C, D </tex> {{---}} нетерминалы, <tex>a </tex> {{---}} терминал.

# <tex>AB-\rightarrow CD</tex>CD# <tex>A-\rightarrow BC</tex>BC# <tex>A-\rightarrow a</tex>a или <tex>A->\rightarrow \varepsilon</tex>Где <tex>A, B, C, D </tex> {{---}} нетерминалы, <tex>a </tex> {{---}} терминал.

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

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

|proof = Каждому терминалу <tex>a </tex> поставим в соотвествие новый символ <tex>a'</tex>, которого нет в <tex>N U \cup T</tex>, такой что <tex>a' != \neq b' </tex> для разных терминалов <tex>a </tex> и <tex>b.Пусть 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.Построим грамматику G' = (N', T, P', S), где P' = {\alpha' \rightarrow \beta' : \alpha \rightarrow \beta \in P} U {a' \rightarrow a: a \in T}/tex>.

Покажем, что L(GПусть <tex>N') = L(G)N \cup \{a' | a \in T\}</tex>.

Пусть w <tex>\in L(G). Тогда в G существует вывод S = w_0 => w_1 alpha => x_1x_2... =x_n</tex> w_n => w. Согласно конструкции P'{{---}} часть правила, в G' существует вывод S = w_0' =тогда <tex> w_1' => w_2\alpha' => y_1y_2... =y_n</tex> w_n' = v_0 =, где <tex> v_1 y_i =\{x_i</tex> v_2 =, если <tex> ... =x_i \in N</tex> v_m = w.Для 0 ; <= i tex>x_i'<= n - 1 в переходах w_i' =/tex> w_{i + 1}' используем правило \alpha' \rightarrow \beta', так как правило если <tex>x_i \alpha in T\rightarrow \beta было использовано при выводе w_i =}</tex> для <tex> w_{i + 1}.Для 0 <= j i <= m - 1 в переходах v_j =n</tex> v_{j + 1} используем правила вида a' \rightarrow a.Заменяем разрешенные в w' символы на новые и получаем, что w \in L(G').Тогда L(G) <= L(G').

Построим грамматику <tex>G' = (N', T, P', S)</tex>, где <tex>P' = \{\alpha' \rightarrow \beta' : \alpha \rightarrow \beta \in P\} \cup \{a' \rightarrow a: a \in T\}</tex>. Покажем, что <tex>L(G') = L(G)</tex>. Пусть <tex>w \in L(G)</tex>. Тогда в G существует вывод <tex>S = w_0 => w_1 => ... => w_n => w</tex>.  Согласно конструкции <tex>P'</tex>, в <tex>G'</tex> существует вывод <tex>S = w_0' => w_1' => w_2' => ... => w_n' = v_0 => v_1 => v_2 => ... => v_m = w</tex>. Для <tex>0 <= i <= n - 1</tex> в переходах <tex>w_i' => w_{i + 1}'</tex> используем правило <tex>\alpha' \rightarrow \beta'</tex>, так как правило <tex>\alpha \rightarrow \beta</tex> было использовано при выводе <tex>w_i => w_{i + 1}</tex>. Для <tex>0 <= j <= m - 1</tex> в переходах <tex>v_j => v_{j + 1}</tex> используем правила вида <tex>a' \rightarrow a</tex>. Заменяем разрешенные в <tex>w'</tex> символы на новые и получаем, что <tex>w \in L(G')</tex>.Тогда <tex>L(G) <= L(G')</tex>. Пусть <tex>x \in L(G')</tex>. Тогда в <tex>G' </tex> существует вывод <tex>S =>* x</tex>. Мы можем поменять порядок применения правил в этом выводе:сначала применяем только правила вида <tex>\alpha' \rightarrow \beta'</tex>, а потом только правила вида <tex>a' \rightarrow a</tex>.  Из построения: после применения правила вида <tex>a' \rightarrow a </tex> полученное <tex>a </tex> не может быть использовано при применении правил из <tex>P'</tex>.  Изменение порядка вывода не меняет язык, то есть в <tex>G' </tex> существует вывод: <tex>S = x_0' => x_1' => ... => x_r' => x' => y_1 => y_2 => ... => y_s = x</tex>,где для <tex>0 <= i <= r - 1 x_{i + 1}' \in (N')^* </tex> и в переходе <tex>x_i' \rightarrow x_{i + 1}' </tex> было использовано правило вывода <tex>\alpha' \rightarrow \beta'</tex> и для <tex>1 <= j <= s </tex> было использовано правило <tex>a' \rightarrow a</tex>, чтобы получить <tex>y_j \rightarrow y_{j + 1}</tex>. Получаем вывод в <tex>G</tex>: <tex>S = x_0 => x_1 => ... => x_n = x</tex>.Тогда <tex>L(G') <= L(G)</tex>.Таким образом, <tex>L(G') = L(G)</tex>.

|statement= Для любой грамматики <tex>G = (N, T, P, S) </tex> может быть построена грамматика <tex>G' = (N', T, P', S) </tex> такая, что:* любое правило из <tex>P' </tex> имеет вид: <tex>\alpha \rightarrow \beta</tex>, где <tex>\alpha \in (N')^+ </tex> и <tex>\beta \in (N')^+ </tex> и <tex>|\alpha| <= |\beta| </tex>, или <tex>A \rightarrow a </tex>, или <tex>A \rightarrow \varepsilon</tex>, где <tex>A \in N' </tex> и <tex>a \in T</tex>* <tex>L(G') = L(G)</tex>