The equivalence problem for LL- and LR-regular grammars

Anton Nijholt; F. Gecsec

doi:10.1007/3-540-10854-8_32

The equivalence problem for LL- and LR-regular grammars

Anton Nijholt, F. Gecsec (Editor)

Research output: Contribution to conference › Paper › peer-review

137 Downloads (Pure)

Abstract

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 language	English
Pages	291-300
Number of pages	10
DOIs	https://doi.org/10.1007/3-540-10854-8_32
Publication status	Published - Sept 1981
Event	Fundamentals of Computation Theory - Szeged, Hungary Duration: 24 Aug 1981 → 28 Aug 1981

Conference

Conference	Fundamentals of Computation Theory
Period	24/08/81 → 28/08/81
Other	24-28 August 1981

Keywords

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

Access to Document

10.1007/3-540-10854-8_32

fct1981Final published version, 482 KB

Cite this

@conference{e7f28c2bbc9849ab8a0ea3253eb8587a,

title = "The equivalence problem for LL- and LR-regular grammars",

abstract = "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.",

keywords = "EWI-9235, HMI-SLT: Speech and Language Technology, IR-66932",

author = "Anton Nijholt and F. Gecsec",

year = "1981",

month = sep,

doi = "10.1007/3-540-10854-8_32",

language = "English",

pages = "291--300",

note = "Fundamentals of Computation Theory ; Conference date: 24-08-1981 Through 28-08-1981",

}

TY - CONF

T1 - The equivalence problem for LL- and LR-regular grammars

AU - Nijholt, Anton

A2 - Gecsec, F.

PY - 1981/9

Y1 - 1981/9

N2 - 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.

AB - 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.

KW - EWI-9235

KW - HMI-SLT: Speech and Language Technology

KW - IR-66932

U2 - 10.1007/3-540-10854-8_32

DO - 10.1007/3-540-10854-8_32

M3 - Paper

SP - 291

EP - 300

T2 - Fundamentals of Computation Theory

Y2 - 24 August 1981 through 28 August 1981

ER -

The equivalence problem for LL- and LR-regular grammars

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this