A Hierarchy of Context-Free Derivations

Article type: Research Article

Authors: Mäkinen, Erkki

Affiliations: University of Tampere, Department of Computer Science, P.O. Box 607, SF-33101 Tampere, Finland

Abstract: This note discusses a hierarchy of different kind of context-free derivations by studying the corresponding Szilard languages. Especially, we introduce the leftmost and rightmost breadth-first derivations which are the counterparts of the well-known (depth-first) leftmost and rightmost derivations. It is shown that the Szilard languages related to different derivation types can be recognized by one-state automata which differ from each others by their memory devices.

DOI: 10.3233/FI-1991-14206

Journal: Fundamenta Informaticae, vol. 14, no. 2, pp. 255-259, 1991