Title

Abstract Families Of Context-Free Grammars

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Abbreviated Journal Title

Int. J. Comput. Math.

Keywords

Mathematics; Applied; nonexpansive grammars

Abstract

An abstract family of grammars (AFG) may be defined as a class of grammars for which the corresponding class of languages forms an abstract family of languages (AFL) as defined by Ginsburg and Greibach. The derivation bounded grammars of Ginsburg and Spanier is an example of an AFG which is properly included in the class of all context-free grammars (also AFG). The main result is that there exist two distinct infinite hierarchies of AFG which exhaust the derivation bounded AFG such that the AFL associated with the kth member of one of these AFG hierarchies is properly included in the AFL associated with the k-lst member of that same hierarchy. Each hierarchy is shown to be strongly incomparable to the other; that is, the first member of each generates some language not generated by a fixed but arbitrary member of the other. We designate these hierarchies as the hierarchies of left and right dominant grammars (languages)

Journal Title

International Journal of Computer Mathematics

Volume

9

Issue/Number

2

Publication Date

1-1-1981

Document Type

Article

Language

English

First Page

97

Last Page

115

WOS Identifier

WOS:A1981LE95300001

ISSN

0020-7160

Share

COinS