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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

Формальное определение[править | править вики-текст]

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

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

Примеры[править | править вики-текст]

Следующая граматика задает контекстно-зависимый язык  \{ a^n b^n c^n : n \ge 1 \} :

  1. S \rightarrow aSBC
  2. S \rightarrow aBC
  3. CB\rightarrow HB
  4. HB \rightarrow HC
  5. HC \rightarrow BC
  6. aB \rightarrow ab
  7. bB \rightarrow bb
  8. bC \rightarrow bc
  9. cC \rightarrow cc


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

S
\Rightarrow_1 aSBC
\Rightarrow_1 a\boldsymbol{aSBC}BC
\Rightarrow_2 aa\boldsymbol{aBC}BCBC
\Rightarrow_3 aaaB\boldsymbol{HB}CBC
\Rightarrow_4 aaaB\boldsymbol{HC}CBC
\Rightarrow_5 aaaB\boldsymbol{BC}CBC
\Rightarrow_3 aaaBBC\boldsymbol{HB}C
\Rightarrow_4 aaaBBC\boldsymbol{HC}C
\Rightarrow_5 aaaBBC\boldsymbol{BC}C
\Rightarrow_3 aaaBB\boldsymbol{HB}CC
\Rightarrow_4 aaaBB\boldsymbol{HC}CC
\Rightarrow_5 aaaBB\boldsymbol{BC}CC
\Rightarrow_6 aa\boldsymbol{ab}BBCCC
\Rightarrow_7 aaa\boldsymbol{bb}BCCC
\Rightarrow_7 aaab\boldsymbol{bb}CCC
\Rightarrow_8 aaabb\boldsymbol{bc}CC
\Rightarrow_9 aaabbb\boldsymbol{cc}C
\Rightarrow_9 aaabbbc\boldsymbol{cc}

См. также[править | править вики-текст]

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