Publication Details

Characterization of the Chomsky Hierarchy through Sequential-Parallel Grammars

MEDUNA, A. Characterization of the Chomsky Hierarchy through Sequential-Parallel Grammars. Rostocker mathematisches kolloquium, 1987, vol. 1987, no. 32, p. 4-14. ISSN: 0138-3248.

Czech title

Charakterizace Chomského hierarchie pomocí sekvenčně-paralelních gramatik

Type

journal article

Language

English

Authors

Meduna Alexandr, prof. RNDr., CSc. (DIFS)

Keywords

selective substitution grammars, sequential-parallel grammars, Chomsky hierarchy

Abstract

In this paper we deal with a special type of selective substitution grammars, so-called sequential-parallel grammars.

Annotation

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.

Published

1987

Pages

4–14

Journal

Rostocker mathematisches kolloquium, vol. 1987, no. 32, ISSN 0138-3248

Book

Rostocker mathematisches kolloquium

Place

Rostock

BibTeX

@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"
}