Hypergrammars: An extension of macrogrammars

摘要

A new class of generative grammars called hypergrammars is introduced. They are described as a natural extension of Fischer's macrogrammars. Three modes of derivation, inside-out, outside-in, and unrestricted are considered, and the classes of languages so defined are compared with other known classes. It is shown that the outside-in hyper-languages are the same as the outside-in macrolanguages but that inside-out hyperlanguages are the same as Fischer's quoted languages. Various closure properties are considered as well as generalizations of the original definitions. Three new hierarchies of languages each embedded in the class of quoted languages are discovered. It is claimed that this new approach to Fischer's work is more understandable and also mathematically elegant.