Префиксная грамматика

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

В информатике префиксной грамматикой называется тип системы переписывания строк, состоящей из множества правил переписывания строк, схожей с формальными грамматиками. Характерной для префиксной грамматики является не форма правил, а способ их применения: переписываются только префиксы.

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

Префиксная грамматика G — это тройка (Σ, S, P), где

  • Σ — конечный алфавит
  • S — конечное множество основных строк над Σ
  • P — множество правил вывода в форме uv, где u и v — строки над Σ

Для строк x, y, справедлива запись x →G y (читается: G выводит y из x за один шаг) если есть строки u, v, w, такие что x = vu, y = wu, и v → w принадлежит P. Заметим, что G является двоичным отношением на строках над Σ.

Язык G, обозначаемый L(G), — это множество строк, выводимых из S за ноль и более шагов. Формально, это множество строк w, таких что для некоторого s из S выполнено s R w, где R — транзитивное замыкание G.

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

Префиксная грамматика

  • Σ = {0, 1}
  • S = {01, 10}
  • P = {0 → 010, 10 → 100}

описывает язык, задаваемый регулярным выражением

 01(01)^* \cup 100^*

Свойства[править | править вики-текст]

Префиксные грамматики описывают ровно все регулярные языки.[1]

Ссылки[править | править вики-текст]