I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Publications - An Efficient Automata Approach to Some Problems on Context-free Grammars


A. Bouajjani, J. Esparza, A. Finkel, O. Maler, P. Rossmanith, B. Willems, and P. Wolper. An efficient automata approach to some problems on context-free grammars. Information Processing Letters, 74(5–6):221–227, 2000.


In Chapter 4 of their book ``String-Rewriting Systems'', Book and Otto solve a number of word problems for monadic string-rewriting systems using an elegant automata-based technique. In this note we observe that the technique is also very interesting from a pedagogical point of view, since it provides a uniform solution to several elementary problems on context-free languages.

Suggested BibTeX entry:

    author = {A. Bouajjani and J. Esparza and A. Finkel and O. Maler and P. Rossmanith and B. Willems and P. Wolper},
    journal = {Information Processing Letters},
    number = {5--6},
    pages = {221--227},
    title = {An Efficient Automata Approach to Some Problems on Context-free Grammars},
    volume = {74},
    year = {2000}

GZipped PostScript (84 kB)
PDF (212 kB)
An even more efficient approach can be found in ERS00