В теории формального языка контекстно -зависимая грамматика находится в нормальной форме Куроды , если все продукционные правила имеют вид: [1]
где A, B, C и D — нетерминальные символы, а a — терминальный символ . [1] Некоторые источники опускают шаблон A → B. [2]
Она названа в честь Сиге-Юки Куроды , который первоначально назвал ее линейной ограниченной грамматикой — терминология, которая впоследствии также использовалась несколькими другими авторами. [3]
Каждая грамматика в нормальной форме Куроды является несжимаемой и, следовательно, порождает контекстно-зависимый язык . И наоборот, каждый контекстно-зависимый язык, который не генерирует пустую строку , может быть сгенерирован грамматикой в нормальной форме Куроды. [2]
Прямая техника, приписываемая Дьёрдь Ревесу, преобразует грамматику в форме Куроды в CSG Хомского: AB → CD заменяется четырьмя контекстно-зависимыми правилами AB → AZ , AZ → WZ , WZ → WD и WD → CD . Этот метод также доказывает, что каждая неконтрактная грамматика является контекстно-зависимой. [1]
Аналогичная нормальная форма существует и для неограниченных грамматик , которую, по крайней мере, некоторые авторы также называют «нормальной формой Куроды»: [4]