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

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

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

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

Σ — конечный алфавит
S — конечное множество основных строк над Σ
P — множество правил вывода в форме u → v, где 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.