A pushdown automaton or a context-free grammar - which is more economical?
From MaRDI portal
Publication:1165026
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
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