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

Материал из Seo Wiki - Поисковая Оптимизация и Программирование

Перейти к: навигация, поиск

Контекстно-зависимая грамматика (КЗ-грамматика, контекстная грамматика) — частный случай формальной грамматики (тип 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 HB </math>
  4. <math>HB \rightarrow HC </math>
  5. <math>HC \rightarrow BC </math>
  6. <math>aB \rightarrow ab </math>
  7. <math>bB \rightarrow bb </math>
  8. <math>bC \rightarrow bc </math>
  9. <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{HB}CBC </math>
<math>\Rightarrow_4 aaaB\boldsymbol{HC}CBC </math>
<math>\Rightarrow_5 aaaB\boldsymbol{BC}CBC </math>
<math>\Rightarrow_3 aaaBBC\boldsymbol{HB}C </math>
<math>\Rightarrow_4 aaaBBC\boldsymbol{HC}C </math>
<math>\Rightarrow_5 aaaBBC\boldsymbol{BC}C </math>
<math>\Rightarrow_3 aaaBB\boldsymbol{HB}CC </math>
<math>\Rightarrow_4 aaaBB\boldsymbol{HC}CC </math>
<math>\Rightarrow_5 aaaBB\boldsymbol{BC}CC </math>
<math>\Rightarrow_6 aa\boldsymbol{ab}BBCCC </math>
<math>\Rightarrow_7 aaa\boldsymbol{bb}BCCC </math>
<math>\Rightarrow_7 aaab\boldsymbol{bb}CCC </math>
<math>\Rightarrow_8 aaabb\boldsymbol{bc}CC </math>
<math>\Rightarrow_9 aaabbb\boldsymbol{cc}C </math>
<math>\Rightarrow_9 aaabbbc\boldsymbol{cc} </math>cs:Kontextová gramatika

de:Kontextsensitive Grammatik en:Context-sensitive grammar es:Gramáticas sensibles al contexto hr:Kontekstno ovisna gramatika it:Grammatica dipendente dal contesto ja:文脈依存文法 pl:Gramatyka kontekstowa pt:Gramática sensível ao contexto sk:Kontextová gramatika sr:Контекстно-сензитивна граматика sh:Kontekstno ovisna gramatika zh:上下文有关文法

Личные инструменты

Served in 0.055 secs.