Title
Abstract Families Of Context-Free Grammars
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
ISSN
0020-7160
Recommended Citation
Workman, D., "Abstract Families Of Context-Free Grammars" (1981). Faculty Bibliography 1980s. 127.
https://stars.library.ucf.edu/facultybib1980/127
Comments
Authors: contact us about adding a copy of your work at STARS@ucf.edu