The equivalence problem for LL- and LR-regular grammars

Anton Nijholt, F. Gecsec (Editor)

    Research output: Contribution to conferencePaperpeer-review

    91 Downloads (Pure)


    It will be shown that the equivalence problem for LL-regular grammars is decidable. Apart from extending the known result for LL(k) grammar equivalence to LLregular grammar equivalence, we obtain an alternative proof of the decidability of LL(k) equivalence. The equivalence prob]em for LL-regular grammars has been studied before, but not solved. Our proof that this equivalence problem is decidable is simple. However, this is mainly because we can reduce the problem to the equivalence problem for real-time strict deterministic grammlars, which is decidable.
    Original languageEnglish
    Number of pages10
    Publication statusPublished - Sep 1981
    EventFundamentals of Computation Theory - Szeged, Hungary
    Duration: 24 Aug 198128 Aug 1981


    ConferenceFundamentals of Computation Theory
    Other24-28 August 1981


    • EWI-9235
    • HMI-SLT: Speech and Language Technology
    • IR-66932


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

    Cite this