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

In this paper we consider a superclass of automaton grammars that can be represented in terms of paths on graphs. With this approach, we assume that vertices of graph are labeled by symbols of finite alphabet A. We will call such grammars graph-generated grammars or G-grammars. In contrast to the graph grammars that are used to describe graph structure transformations, G-grammars using a graphs as a means of representing formal languages. We will give an algorithm for constructing G-grammar which generate the language recognized by deterministic finite automaton. Moreover, we will show that the class of languages generated by G-grammars is a proper superset of regular languages.