Complexity of normal form grammars

DOI10.1016/0304-3975(83)90026-9zbMath0548.68070OpenAlexW1998938240MaRDI QIDQ799380

Alica Kelemenová

Publication date: 1984

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(83)90026-9

zbMATH Keywords

normal formsformal languagescontext free languagesdescription complexitycontext free grammarposition restricted grammars

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items

Generating all permutations by context-free grammars in Chomsky normal form ⋮ Greibach normal form transformation, revisited ⋮ Generating all permutations by context-free grammars in Greibach normal form ⋮ Descriptional complexity of bounded context-free languages ⋮ Lower bounds for context-free grammars ⋮ DESCRIPTIONAL COMPLEXITY OF SPLICING SYSTEMS ⋮ Efficient reconfigurable embedded parsers ⋮ Non-Self-Embedding Grammars and Descriptional Complexity ⋮ Descriptional complexity of context-free grammar forms ⋮ GENERATING ALL CIRCULAR SHIFTS BY CONTEXT-FREE GRAMMARS IN GREIBACH NORMAL FORM ⋮ Non-Self-Embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata ⋮ Greibach normal form transformation revisited.

Cites Work

• Position-restricted grammar forms and grammars
• Optimization of LR(k) parsers
• A Supernormal-Form Theorem for Context-Free Grammars
• Non-context-free grammars generating context-free languages
• Some classifications of context-free languages
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Complexity of normal form grammars