Context-free grammar forms with strict interpretations

DOI10.1016/0022-0000(80)90045-8zbMath0523.68064OpenAlexW2077372141MaRDI QIDQ1056550

Arto Salomaa, Derick Wood, Hermann Maurer

Publication date: 1980

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(80)90045-8

zbMATH Keywords

reducibilitygeneratorsnormal formsclosure propertiesregular setslinear languagesgrammar formscontext-free grammar formshierarchies of language familiesstrict interpretation

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Cut point languages of markov DTOL systems, Colorings and interpretations: a connection between graphs and grammar forms, On minimal graphs, Sub-regular grammar forms, Completeness of context-free grammar forms, Color-families are dense, Decidability and density in two-symbol grammar forms, On form-equivalence of deterministic pure grammar forms, On the generative capacity of context-free matrix forms, On finite grammar forms, Synchronized EOL forms, Derivation languages of grammar forms†

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Grammar and L forms: an introduction
• An approach to a unified theory of grammar and L forms
• On generators and generative capacity of EOL forms
• Position-restricted grammar forms and grammars
• Context-free grammar forms
• EOL forms
• On non context-free grammar forms
• An Observation on Relative Parsing Time
• On strict interpretations of grammar forms