Изменения
Нет описания правки
{{Определение
|definition=Грамматика представлена в '''нормальной форме Пенттонена''' (англ. ''Penttonen normal form''), если каждое правило имеет одну из трех форм:
# <tex>AB \rightarrow CDAC</tex>
# <tex>A \rightarrow BC</tex>
# <tex>A \rightarrow a</tex> или <tex>A \rightarrow \varepsilon</tex>
Также грамматику Пенттонена называют односторонней нормальной формой (англ. ''one-sided normal form''). Как можно заметить, она является частным случаем нормальной формы Куроды: когда <tex>A = C</tex> в первом правиле определения.
Для каждой контестно-зависимой грамматики существует слабо эквивалентная ей грамматика в форме Пенттонена.
{{Лемма
