A note on depth-first derivations
type: Item
instance of: scholarly article
title: A note on depth-first derivations
zbMATH Open document ID: 0577.68071
DOI: 10.1007/BF01935008
published in: BIT
publication date: 1985-01-01T00:00:00Z
review text: It is known that the Szilard language of a context-free grammar is not necessarily context-free, while the left Szilard language is always a simple deterministic language. Depth-first derivations can be regarded as a natural extension of leftmost derivations. In this note, it is shown that the depth-first Szilard languages are simple deterministic ones. In addition, breadth-first Szilard languages are also studied. The author gives an example of a context-free grammar with the property that the associated depth-first Szilard language is not context-free.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 3924156
zbMATH Keywords: depth-first derivation
zbMATH Keywords: breadth-first derivation
zbMATH Keywords: Szilard language
zbMATH Keywords: context-free grammar
zbMATH Keywords: simple deterministic language
author: Erkki Mäkinen
MaRDI profile type: Publication
cites work: Q4198075
cites work: Associate languages and derivational complexity of formal grammars and languages
description: scientific article; zbMATH DE number 3924156