A direct algorithm for checking equivalence of LL(k) grammars

DOI10.1016/0304-3975(77)90016-0zbMath0358.68118OpenAlexW2023090947MaRDI QIDQ1238431

Amir Pnueli, Tmima Olshansky

Publication date: 1977

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

Full work available at URL: https://doi.org/10.1016/0304-3975(77)90016-0

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (11)

An axiomatic approach to the Korenjak-Hopcroft algorithms ⋮ A fast algorithm to decide on the equivalence of stateless DPDA ⋮ Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines ⋮ Superdeterministic DPDAs: The method of accepting does affect decision problems ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ The equivalence problem for LL- and LR-regular grammars ⋮ A direct algorithm for checking equivalence of LL(k) grammars ⋮ On equivalence of grammars through transformation trees ⋮ Synchronizable deterministic pushdown automata and the decidability of their equivalence ⋮ A direct branching algorithm for checking equivalence of strict deterministic vs. LL(k) grammars ⋮ An extended direct branching algorithm for checking equivalence of deterministic pushdown automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Completeness results for the equivalence of recursive schemas
• A direct algorithm for checking equivalence of LL(k) grammars
• Simple program schemes and formal languages
• Optimization of LR(k) parsers
• Optimality of a Two-Phase Strategy for Routing in Interconnection Networks
• Decidable Properties of Monadic Functional Schemas
• Functional schemas with nested predicates
• Properties of deterministic top-down grammars

This page was built for publication: A direct algorithm for checking equivalence of LL(k) grammars