A pushdown automaton or a context-free grammar - which is more economical?

DOI10.1016/0304-3975(82)90110-4zbMath0486.68082OpenAlexW2074593591MaRDI QIDQ1165026

Detlef Wotschke, John K. Price, Jonathan Goldstine

Publication date: 1982

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

Full work available at URL: https://doi.org/10.1016/0304-3975(82)90110-4

zbMATH Keywords

context-free languagesreal-time deterministic pushdown automaton

Mathematics Subject Classification ID

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

Related Items (11)

Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds. ⋮ Generating all permutations by context-free grammars in Greibach normal form ⋮ Syntax checking either way ⋮ Detecting Useless Transitions in Pushdown Automata ⋮ Syntax checking either way ⋮ Deterministic Pushdown Automata and Unary Languages ⋮ Detecting useless transitions in pushdown automata ⋮ DETERMINISTIC PUSHDOWN AUTOMATA AND UNARY LANGUAGES ⋮ Simulating finite automata with context-free grammars. ⋮ On reducing the number of states in a PDA ⋮ On reducing the number of stack symbols in a PDA

Cites Work

• Economy of description by parsers, DPDA's, and PDA's
• Optimization of LR(k) parsers
• Size complexity in context-free grammars forms
• A note on the succinctness of descriptions of deterministic languages
• Succinctness of Descriptions of Unambiguous Context-Free Languages
• Finite-Turn Pushdown Automata
• A helpful result for proving inherent ambiguity
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A pushdown automaton or a context-free grammar - which is more economical?