Article ID Journal Published Year Pages File Type
437540 Theoretical Computer Science 2011 17 Pages PDF
Abstract

We define context-free grammars with Büchi acceptance condition generating languages of countable words. We establish several closure properties and decidability results for the class of Büchi context-free languages generated by these grammars. We also define context-free grammars with Müller acceptance condition and show that there is a language generated by a grammar with Müller acceptance condition which is not a Büchi context-free language.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics