Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 6 января 2016 года; проверки требуют 10 правок.
Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 6 января 2016 года; проверки требуют 10 правок.
Контекстно зависимая грамматика (КЗ-грамматика, контекстная грамматика) — частный случай формальной грамматики (тип 1 по иерархии Хомского), у которой левые и правые части всех продукций могут быть окружены терминальными и нетерминальными символами.
Формальная грамматика G=(N, T, I, P) является контекстно-зависимой, если все правила P имеют вид:
αAβ → αωβ
где A ∈ N (то есть одиночный нетерминальный символ), ω ∈ (N ∪ T)+ (то есть непустая цепочка, состоящая из терминальных и/или нетерминальных символов), α, β ∈ (N ∪ T)* (то есть любая цепочка, состоящая из терминальных и/или нетерминальных символов).
Кук Д., Бейз Г.Глава 8. Языки и грамматики // Компьютерная математика = Computer Mathematics. — М.: Наука. Физматлит, 1990. — 384 с. — ISBN 5-02-014216-6.