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

DOI10.1016/0304-3975(82)90110-4zbMath0486.68082MaRDI 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 languages; real-time deterministic pushdown automaton

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q45: Formal languages and automata

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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