Вестник СамГУ 2014. № 10 (121). С.102-108.
УДК 519.713.34:519.171
Цветов В.П.
ОБ ОДНОМ НАДКЛАССЕ A-ГРАММАТИК
Аннотация. В статье рассматривается класс грамматик, допускающих представление правил порождения при помощи алгоритмов нахождения маршрутов на графах. Дается определение граф-порожденной грамматики или G-грамматики (над алфавитом A) в терминах семейств маршрутов на вершинно размеченных графах. В отличие от графовых грамматик, которые применяются для описания динамики графовых структур, G-грамматики, напротив, используют граф-отношения в качестве средства представления формальных языков. Приводится алгоритм построения G-грамматики, порождающей язык, распознаваемый детерминированным конечным автоматом. Показывается, что класс языков, порождаемых G-грамматиками, является строгим надмножеством регулярных языков.
Ключевые слова: формальные языки, формальные грамматики, порождающие грамматики, теория автоматов, теория графов, маршруты на графах, размеченн;