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

Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей.

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

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

Префиксная грамматика 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}

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

$01(01)^* \cup 100^*$

Свойства

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

Ссылки

1. ↑ M. Frazier and C. D. Page. Prefix grammars: An alternative characterization of the regular languages. Information Processing Letters, 51(2):67–71, 1994.