В информатике - префиксной грамматикой называется тип системы переписывания строк, состоящей из множества правил переписывания строк, схожей с формальными грамматиками. Характерной для префиксной грамматики является не форма правил, а способ их применения: переписываются только префиксы.
Формальное определение
Префиксная грамматика 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.
Пример
Префиксная грамматика Σ = {0, 1} S = {01, 10} P = {0 → 010, 10 → 100} описывает язык, задаваемый регулярным выражением
Свойства Префиксные грамматики описывают ровно все регулярные языки.M. Frazier and C. D. Page. Prefix grammars: An alternative characterization of the regular languages. Information Processing Letters, 51(2):67–71, 1994.
Ссылки
Категория:Формальные грамматики