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

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

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

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

Ссылки

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

Похожие исследовательские статьи

Код — взаимно однозначное отображение конечного упорядоченного множества символов, принадлежащих некоторому конечному алфавиту, на иное, не обязательно упорядоченное, как правило более обширное множество символов для кодирования передачи, хранения или преобразования информации.

Теория автоматов — раздел дискретной математики, изучающий абстрактные автоматы — вычислительные машины, представленные в виде математических моделей, и задачи, которые они могут решать.

Контекстно-свободная грамматика — частный случай формальной грамматики, у которой левые части всех продукций являются одиночными нетерминалами. Смысл термина «контекстно-свободная» заключается в том, что есть возможность применить продукцию к нетерминалу, причём независимо от контекста этого нетерминала.

Грамматика с фразовой структурой — формальная грамматика, алгебраическая структура, состоящая из упорядоченной четвёрки G=(N, T, P, S) и определённой на ней неявно операцией конкатенации.

N — конечное множество нетерминальных символов
T — не пересекающееся с N конечное множество терминальных символов
P — набор ограничивающих правил (продукций)
S — стартовый

Алгори́тм Ле́мпеля — Зи́ва — Уэлча — это универсальный алгоритм сжатия данных без потерь, созданный Авраамом Лемпелем, Яаковом Зивом и Терри Велчем. Он был опубликован Велчем в 1984 году в качестве улучшенной реализации алгоритма LZ78, опубликованного Лемпелем и Зивом в 1978 году. Алгоритм разработан так, чтобы его было достаточно просто реализовать как программно, так и аппаратно.

<span class="mw-page-title-main">Формальная грамматика</span>

Формальная грамматика или просто грамматика в теории формальных языков — способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавита. Различают порождающие и распознающие грамматики — первые задают правила, с помощью которых можно построить любое слово языка, а вторые позволяют по данному слову определить, входит ли оно в язык или нет.

Иерархия Хомского — классификация формальных языков и формальных грамматик, согласно которой они делятся на 4 типа по их условной сложности. Предложена профессором Массачусетского технологического института, лингвистом Ноамом Хомским.

Регулярная грамматика — формальная грамматика типа 3 по иерархии Хомского, регулярные грамматики определяют в точности все регулярные языки, и поэтому эквивалентны конечным автоматам и регулярным выражениям. Регулярные грамматики являются подмножеством контекстно-свободных.

Лемма о разрастании для контекстно-свободных языков — лемма, по аналогии с одноименной леммой для регулярных языков позволяющая относительно несложно доказывать, что данный язык не является контекстно-свободным.

Матричная грамматика — это формальная грамматика, в которой правила вывода группируются в конечные последовательности. Правила вывода не могут применяться по отдельности, а только в последовательности. При применении такой последовательности, замена производится в соответствии с каждым правилом в последовательности, с первой по последнюю. Последовательности называют матрицами. Матричная грамматика является расширением контекстно-свободной грамматики.

Грамматика, разбирающая выражение (РВ-грамматика) — тип аналитической формальной грамматики, описывающей формальный язык в терминах набора правил для распознавания строк языка. Грамматика, разбирающая выражение, в сущности, представляет собой синтаксический анализатор рекурсивного спуска в чисто схематической форме, которая выражает только синтаксис и не зависит от конкретной реализации или применения синтаксического анализатора. Грамматики, разбирающие выражение, похожи на регулярные выражения и на контекстно-свободные грамматики (КС-грамматики) в нотации Бэкуса-Наура, но имеют отличную от них интерпретацию.

ACE — набор программных средств, реализующих шифрование в режиме схемы шифрования с открытым ключом, а также в режиме цифровой подписи. Соответствующие названия этих режимов — «ACE Encrypt» и «ACE Sign». Схемы являются вариантами реализации схем Крамера-Шоупа. Внесённые изменения нацелены на достижение наилучшего баланса между производительностью и безопасностью всей системы шифрования.

Группа Григорчука — первый пример конечнопорождённой группы промежуточного роста.

L-система или система Линденмайера — это параллельная система переписывания и вид формальной грамматики. L-система состоит из алфавита символов, которые могут быть использованы для создания строк, набора порождающих правил, которые задают правила подстановки вместо каждого символа, начальной строки («аксиомы»), с которой начинается построение, и механизма перевода образованной строки в геометрические структуры.

CL-Atse — это инструмент, который преобразует любое описание протокола безопасности на языке IF во множество предположений, которое затем может быть проанализировано на наличие атак на протокол.

Индукция грамматики — процедура машинного обучения, которая восстанавливает формальную грамматику языка на основе набора наблюдений (примеров) с известной принадлежностью этому языку. В результате процедуры строится модель наблюдаемых объектов в виде набора правил вывода или порождающих правил, конечного автомата или автомата другого вида. В более общем смысле, грамматический вывод — это одно из направлений машинного обучения, в котором пространство примеров состоит из дискретных комбинаторных объектов, таких как строки, деревья, графы.

Исчисление Ламбека — формальная логическая система, предложенная в 1958 году Иоахимом Ламбеком, которая предназначена для описания синтаксиса естественных языков. С математической точки зрения исчисление Ламбека является фрагментом линейной логики.

Су́ффиксный автома́т — структура данных, позволяющая хранить в сжатом виде и обрабатывать информацию, связанную с подстроками данной строки. Представляет собой детерминированный конечный автомат, принимающий все суффиксы слова $\text{[math]}$ и только их, и обладающий наименьшим возможным числом состояний среди всех таких автоматов. Менее формально, суффиксный автомат — это ориентированный ациклический граф с выделенной начальной вершиной и набором «финальных» вершин, дуги которого помечены символами, такой что у любой вершины символы на исходящих из неё дугах попарно различны и для любого суффикса слова $\text{[math]}$ существует путь из начальной вершины в некоторую финальную вершину, символы на котором при конкатенации образуют данный суффикс. Из всех графов, удовлетворяющих данному описанию, суффиксным автоматом называется тот, который обладает наименьшим возможным числом вершин.

Недетерминированный конечный автомат — это детерминированный конечный автомат, который не выполняет следующие условия:

любой его переход единственным образом определяется по текущему состоянию и входному символу
чтение входного символа требуется для каждого изменения состояния.

<span class="mw-page-title-main">Дерево палиндромов</span> структура данных, предназначенная для хранения и обработки палиндромных подстрок некоторой строки

Дерево палиндромов — структура данных, предназначенная для хранения и обработки палиндромных подстрок некоторой строки. Была предложена учёными из Уральского федерального университета Михаилом Рубинчиком и Арсением Шуром в 2015 году. Представляет собой два префиксных дерева, собранных из правых «половинок» палиндромных подстрок чётной и нечётной длины соответственно. Структура занимает $\text{[math]}$ памяти и может быть построена за время $\text{[math]}$ , где $\text{[math]}$ — длина строки, а $\text{[math]}$ — количество различных символов в ней. С помощью дерева палиндромов можно эффективно решать такие задачи, как подсчёт числа различных палиндромных подстрок, поиск разбиения строки на наименьшее число палиндромов, проверка подстроки на то, является ли она палиндромом, и другие.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.