Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
ON A SUPERCLASS OF A-GRAMMARS
View through CrossRef
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.
Samara National Research University
Title: ON A SUPERCLASS OF A-GRAMMARS
Description:
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.
Related Results
Evolutionary Grammatical Inference
Evolutionary Grammatical Inference
Grammatical Inference (also known as grammar induction) is the problem of learning a grammar for a language from a set of examples. In a broad sense, some data is presented to the ...
Phrase Structure Grammars
Phrase Structure Grammars
Phrase structure grammars model the internal structure of a sentence in terms of a hierarchically organized representation. The sentence Every boy has a bike, for instance, is take...
Structurally and Arithmetically Controlled Grammars
Structurally and Arithmetically Controlled Grammars
Over the quarter century, it is gratifying to note that the significance of regulated or controlledgrammars (i.e. grammars with regulated rewriting) has been recognized by many par...
Remote attribute grammars
Remote attribute grammars
Describing the static semantics of programming languages with attribute grammars is eased when the formalism allows direct dependencies to be induced between rules for nodes arbitr...
Unification Grammars
Unification Grammars
Grammars of natural languages can be expressed as mathematical objects, similar to computer programs. Such a formal presentation of grammars facilitates mathematical reasoning with...
Semantics and algorithms for data-dependent grammars
Semantics and algorithms for data-dependent grammars
We present the design and theory of a new parsing engine, YAKKER, capable of satisfying the many needs of modern programmers and modern data processing applications. In particular,...
Tree Valence Controlled Grammars
Tree Valence Controlled Grammars
Beyond a shadow of a doubt, the studying of context-free grammars with restricted derivationtrees known as tree controlled grammars have achieved plentiful remarkable results withi...
Chomsky, Noam (1928–)
Chomsky, Noam (1928–)
Fish swim, birds fly, people talk. The talents displayed by fish and birds rest on specific biological structures whose intricate detail is attributable to genetic endowment. Human...