ON A SUPERCLASS OF A-GRAMMARS


Cite item

Abstract

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.

About the authors

V.P. Tsvetov

Самарский государственный университет

Author for correspondence.
Email: morenov.sv@ssau.ru

References


Copyright (c) 2017 В.П. Цветов

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies