A direct branching algorithm for checking equivalence of strict deterministic vs. LL(k) grammars
From MaRDI portal
Publication:1838320
DOI10.1016/0304-3975(83)90052-XzbMath0509.68072MaRDI QIDQ1838320
Publication date: 1983
Published in: Theoretical Computer Science (Search for Journal in Brave)
equivalence; context-free grammar; branching algorithm; Greibach normal form; LL(k) grammar; skipping; strict deterministic grammar
68Q45: Formal languages and automata
Related Items
An extended direct branching algorithm for checking equivalence of deterministic pushdown automata, New techniques for proving the decidability of equivalence problem, Synchronizable deterministic pushdown automata and the decidability of their equivalence, The extended equivalence problem for a class of non-real-time deterministic pushdown automata
Cites Work
- Unnamed Item
- Unnamed Item
- Superdeterministic DPDAs: The method of accepting does affect decision problems
- Deterministic one-counter automata
- A result on the equivalence problem for deterministic pushdown automata
- A direct algorithm for checking equivalence of LL(k) grammars
- An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
- Two decidability results for deterministic pushdown automata
- On equivalence of grammars through transformation trees
- Strict deterministic grammars
- Optimization of LR(k) parsers
- A direct branching algorithm for checking equivalence of some classes of deterministic pushdown automata
- Optimality of a Two-Phase Strategy for Routing in Interconnection Networks
- The equivalence problem for real-time strict deterministic languages
- On the Parsing of Deterministic Languages
- Some remarks on the KH algorithm fors-grammars
- The decidability of equivalence for deterministic stateless pushdown automata
- The equivalence problem for deterministic finite-turn pushdown automata
- Properties of deterministic top-down grammars
- Real-Time Strict Deterministic Languages
