The equivalence problem for LL- and LR-regular grammars

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)
46 Downloads (Pure)

Abstract

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
Volume24
Issue number2
DOIs
Publication statusPublished - 1982
Externally publishedYes

Keywords

  • HMI-SLT: Speech and Language Technology

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

  • Cite this