Открыть главное меню

Контекстно-зависимая грамматика

Контекстно-зависимая грамматика (КЗ-грамматика, контекстная грамматика) — частный случай формальной грамматики (тип 1 по иерархии Хомского), у которой левые и правые части всех продукций могут быть окружены терминальными и нетерминальными символами.

Частным случаем формальной грамматики также является контекстно-свободная грамматика.

Язык, который может быть задан КЗ-грамматикой, называется контекстно-зависимым языком или КЗ-языком.

Формальное определениеПравить

Формальная грамматика G=(N, T, I, P) является контекстно-зависимой, если все правила P имеют вид: αAβ → αωβ

где A ∈ N (то есть одиночный нетерминальный символ), ω ∈ (N ∪ T)+ (то есть непустая цепочка, состоящая из терминальных и/или нетерминальных символов), α, β ∈ (N ∪ T)* (то есть любая цепочка, состоящая из терминальных и/или нетерминальных символов).

ПримерыПравить

Следующая грамматика задает контекстно-зависимый язык  :

  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  
  9.  
  10.  

Так выглядит цепочка порождения aaa bbb ccc:

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

См. такжеПравить

  • JFLAP кроссплатформенная программа симулятор автоматов, машины Тьюринга, грамматик, рисует граф автомата

ЛитератураПравить

  • Кук Д., Бейз Г. Глава 8. Языки и грамматики // Компьютерная математика = Computer Mathematics. — М.: Наука. Физматлит, 1990. — 384 с. — ISBN 5-02-014216-6.