The equivalence problem for LL- and LR-regular grammars

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)
171 Downloads (Pure)


The equivalence problem for context-free grammars is "given two arbitrary grammars, do they generate the same language?" Since this is undecidable in general, attention has been restricted to decidable subclasses of the context-free grammars. For example, the classes of LL(k) grammars and real-time strict deterministic grammars. In this paper it is shown that the equivalence problem for LL-regular grammars is decidable by reducing it to the equivalence problem for real-time strict deterministic grammars. Moreover, we show that the LL-regular equivalence problem is a special case of a more general equivalence problem which is also decidable. Our techniques can also be used to show that the equivalence problem for LR-regular grammars is decidable if and only if the equivalence problem for LR(0) grammars is decidable.
Original languageEnglish
Pages (from-to)149-161
Number of pages13
JournalJournal of computer and system sciences
Issue number2
Publication statusPublished - 1982
Externally publishedYes


  • HMI-SLT: Speech and Language Technology


Dive into the research topics of 'The equivalence problem for LL- and LR-regular grammars'. Together they form a unique fingerprint.

Cite this