Об одном надклассе A-грамматик

В статье рассматривается класс грамматик, допускающих представление правил порождения при помощи алгоритмов нахождения маршрутов на графах. Дается определение граф-порожденной грамматики или $\mathrm{G}$-грамматики (над алфавитом $\mathcal{A}$) в терминах семейств маршрутов на вершинно размеченных графах. В отличие от графовых грамматик, которые применяются для описания динамики графовых структур, $\mathrm{G}$-грамматики, напротив, используют граф-отношения в качестве средства представления формальных языков. Приводится алгоритм построения $\mathrm{G}$-грамматики, порождающей язык, распознаваемый детерминированным конечным автоматом. Показывается, что класс языков, порождаемых $\mathrm{G}$-грамматиками, является строгим надмножеством регулярных языков.