Back to University of Twente portal
The equivalence problem for LL- and LR-regular grammars
Nijholt, A. (1981) The equivalence problem for LL- and LR-regular grammars. In: Fundamentals of Computation Theory, 24-28 August 1981, Szeged, Hungary.
![[img]](http://doc.utwente.nl/style/images/fileicons/application_pdf.png)
| PDF 482Kb |
| 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. |
| Item Type: | Conference or Workshop Item |
| Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |
| Research Group: | |
| Link to this item: | http://purl.utwente.nl/publications/66932 |
| Official URL: | http://dx.doi.org/10.1007/3-540-10854-8_32 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page