Русская Википедия:Контекстно-зависимая грамматика

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

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

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

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

Примеры

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

1. <math>S \rightarrow aSBC</math>
2. <math>S \rightarrow aBC </math>
3. <math>CB\rightarrow CZ </math>
4. <math>CZ \rightarrow WZ </math>
5. <math>WZ \rightarrow WC </math>
6. <math>WC \rightarrow BC </math>
7. <math>aB \rightarrow ab </math>
8. <math>bB \rightarrow bb </math>
9. <math>bC \rightarrow bc </math>
10. <math>cC \rightarrow cc </math>

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

<math>S</math>

<math>\Rightarrow_1 aSBC</math>

<math>\Rightarrow_1 a\boldsymbol{aSBC}BC </math>

<math>\Rightarrow_2 aa\boldsymbol{aBC}BCBC </math>

<math>\Rightarrow_3 aaaB\boldsymbol{CZ}CBC </math>

<math>\Rightarrow_4 aaaB\boldsymbol{WZ}CBC </math>

<math>\Rightarrow_5 aaaB\boldsymbol{WC}CBC </math>

<math>\Rightarrow_6 aaaB\boldsymbol{BC}CBC </math>

<math>\Rightarrow_3 aaaBBC\boldsymbol{CZ}C </math>

<math>\Rightarrow_4 aaaBBC\boldsymbol{WZ}C </math>

<math>\Rightarrow_5 aaaBBC\boldsymbol{WC}C </math>

<math>\Rightarrow_6 aaaBBC\boldsymbol{BC}C </math>

<math>\Rightarrow_3 aaaBB\boldsymbol{CZ}CC </math>

<math>\Rightarrow_4 aaaBB\boldsymbol{WZ}CC </math>

<math>\Rightarrow_5 aaaBB\boldsymbol{WC}CC </math>

<math>\Rightarrow_6 aaaBB\boldsymbol{BC}CC </math>

<math>\Rightarrow_7 aa\boldsymbol{ab}BBCCC </math>

<math>\Rightarrow_8 aaa\boldsymbol{bb}BCCC </math>

<math>\Rightarrow_8 aaab\boldsymbol{bb}CCC </math>

<math>\Rightarrow_9 aaabb\boldsymbol{bc}CC </math>

<math>\Rightarrow_{10} aaabbb\boldsymbol{cc}C </math>

<math>\Rightarrow_{10} aaabbbc\boldsymbol{cc} </math>

См. также

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

Литература

• Шаблон:Книга