arXiv Open Access 2015

Formalization of simplification for context-free grammars

Marcus V. M. Ramos Ruy J. G. B. de Queiroz

Lihat Sumber

Abstrak

Context-free grammar simplification is a subject of high importance in computer language processing technology as well as in formal language theory. This paper presents a formalization, using the Coq proof assistant, of the fact that general context-free grammars generate languages that can be also generated by simpler and equivalent context-free grammars. Namely, useless symbol elimination, inaccessible symbol elimination, unit rules elimination and empty rules elimination operations were described and proven correct with respect to the preservation of the language generated by the original grammar.

Topik & Kata Kunci

cs.FL

Penulis (2)

Marcus V. M. Ramos

Ruy J. G. B. de Queiroz

Format Sitasi

APA MLA BibTeX

Ramos, M.V.M., Queiroz, R.J.G.B.d. (2015). Formalization of simplification for context-free grammars. https://arxiv.org/abs/1509.02032

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2015
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓