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 ...
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...
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...
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...
Descriptive Linguistics
Descriptive Linguistics
AbstractWhen people who are not linguists consult a grammar book, it is usually because they want to find out the correct way of expressing something. This is the kind of informati...
Noncanonical SLR(1) Grammars
Noncanonical SLR(1) Grammars
Two noncanonical extensions of the simple LR(1) (SLR(1)) method are presented, which reduce not only handles but also other phrases of sentential forms. A class of context-free gra...
Domain-wide or variable-dependent vulnerability of the semantics—syntax interface in L2 acquisition? Evidence from wh-words used as existential polarity words in L2 Chinese grammars
Domain-wide or variable-dependent vulnerability of the semantics—syntax interface in L2 acquisition? Evidence from wh-words used as existential polarity words in L2 Chinese grammars
Most studies in the second language (L2) literature that deal with interface issues do so in holistic terms. On the one hand, researchers have suggested that interface relations be...