A note on depth-first derivations

DOI10.1007/BF01935008MaRDI QIDQ1065553zbMATH OpenFDO

Authors Erkki Mäkinen

Publication date 1985

Published in BIT (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01935008

zbMATH Keywords

breadth-first derivationcontext-free grammardepth-first derivationsimple deterministic languageSzilard language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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.

Recommendations

• Publication:3200545
• scientific article; zbMATH DE number 4147543
• On context-free and Szilard languages
• Publication:3028359
• On the synchronized derivation depth of context-free grammars

Cites work

• Associate languages and derivational complexity of formal grammars and languages
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)

Cited in

(3)

• On some derivation mechanisms and the complexity of their Szilard languages
• scientific article; zbMATH DE number 4176462 (Why is no real title available?)
• scientific article; zbMATH DE number 3878384 (Why is no real title available?)

This page was built for publication: A note on depth-first derivations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1065553)