ON A SUPERCLASS OF A-GRAMMARS

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.

формальные языки, формальные грамматики, порождающие грамматики, теория автоматов, теория графов, маршруты на графах, размеченные графы, граф-порожденные грамматики,