|
Vestnik SamGU. Estestvenno-Nauchnaya Ser., 2014, Issue 10(121), Pages 102–108
(Mi vsgu454)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
Mathematics
On a superclass of A-grammars
V. P. Tsvetov Samara State University, Samara, 443011, Russian Federation
(published under the terms of the Creative Commons Attribution 4.0 International License)
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 $\mathcal{A}$. We will call such grammars graph-generated grammars or $\mathrm{G}$-grammars. In contrast to the graph grammars that are used to describe graph structure transformations, $\mathrm{G}$-grammars using a graphs as a means of representing formal languages. We will give an algorithm for constructing $\mathrm{G}$-grammar which generate the language recognized by deterministic finite automaton. Moreover, we will show that the class of languages generated by $\mathrm{G}$-grammars is a proper superset of regular languages.
Keywords:
formal languages, formal grammars, generative grammars, automata theory, graph theory, paths in graphs, labeled graphs, graph-generated grammars.
Received: 10.09.2014
Citation:
V. P. Tsvetov, “On a superclass of A-grammars”, Vestnik Samarskogo Gosudarstvennogo Universiteta. Estestvenno-Nauchnaya Seriya, 2014, no. 10(121), 102–108
Linking options:
https://www.mathnet.ru/eng/vsgu454 https://www.mathnet.ru/eng/vsgu/y2014/i10/p102
|
Statistics & downloads: |
Abstract page: | 93 | Full-text PDF : | 22 | References: | 14 |
|