Главная
Новости
Строительство
Ремонт
Дизайн и интерьер




25.08.2022


11.08.2022


09.08.2022


25.07.2022


18.07.2022





Яндекс.Метрика





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

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

29.01.2021


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

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

Префиксная грамматика 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 ) ∗ ∪ 100 ∗ {displaystyle 01(01)^{*}cup 100^{*}}

Свойства

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