Result Details
Characterization of the Chomsky Hierarchy through Sequential-Parallel Grammars
In this paper we deal with a special type of selective substitution grammars, so-called sequential-parallel grammars.
selective substitution grammars, sequential-parallel grammars, Chomsky hierarchy
In this paper we deal with a special type of selective substitution grammars, so-called sequential-parallel grammars. Some restrictions imposed on productions, derivations and selectors of these grammars are introduced and studied. In particular, we investigate the effect of these restrictions on the language generating power. Characterizations of the four well-known language families of the Chomsky hierarchy (that are the families of regular, context-free, context-sensitive, and recursively enumerable languages) are obtained.
@article{BUT191818,
author="Alexandr {Meduna}",
title="Characterization of the Chomsky Hierarchy through Sequential-Parallel Grammars",
journal="Rostocker mathematisches kolloquium",
year="1987",
volume="1987",
number="32",
pages="4--14",
issn="0138-3248"
}