Home About Upload Latest Additions Statistics Contact
UT Proceedings
UT Student Theses
Dutch Academic Output Dutch Dissertations EU Publications (OpenAIRE)
Printversion
Advanced search

The equivalence problem for LL- and LR-regular grammars

Share/Save/Bookmark

Nijholt, A. (1982) The equivalence problem for LL- and LR-regular grammars. Journal of Computer and System Sciences, 24 (2). pp. 149-161. ISSN 0022-0000

[img]
Preview
PDF
733Kb
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.
Item Type:Article
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/66941
Official URL:http://dx.doi.org/10.1016/0022-0000(82)90044-7
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page