For regular languages we have $\omega$-regular languages which extend them to infinite words.

Are there such extensions for CFG's, CSG's and recursively enumerable languages?

  • 1
    $\begingroup$ This paper compares a number of formalisms: arxiv.org/abs/1308.4516 - is this what you are looking for? Note in particular that in this setting, it makes a difference whether you use grammars or automata to define your languages. $\endgroup$ – Klaus Draeger Aug 21 '15 at 15:07
  • 2
    $\begingroup$ What's wrong with just using the respective automata models with Büchi's acceptance criterion? $\endgroup$ – Raphael Aug 21 '15 at 16:28
  • $\begingroup$ Nothing, really. I just figured that since the question was explicitly about grammars, the arxiv paper might be interesting. $\endgroup$ – Klaus Draeger Aug 21 '15 at 17:31
  • $\begingroup$ @KlausDraeger My comment was aimed towards nikhil_vyas, otherwise I'd have @-pinged you. :) $\endgroup$ – Raphael Aug 21 '15 at 20:31

We have the following MSO characterization of regular nested word languages:

Regular languages over nested words are exactly the set of languages described by Monadic second-order logic with two unary predicates call and return, linear successor and the matching relation ↝.

The recommended reference on Nested Words and Visibly Pushdown Languages treats infinite words in section 8. Nested $\omega$-Words, and shows that the MSO characterization carries over:

Theorem 8.4 (MSO characterization of $\omega$-languages). A language $L$ of nested $\omega$-words over $\Sigma$ is regular iff there is an MSO sentence $\varphi$ over $\Sigma$ that defines $L$.

Because often deterministic CFGs are actually visibly pushdown languages, this covers a huge portion of the practically relevant CFGs. Moreover, this even provides a context where considering $\omega$-languages is practically relevant, as explained in the same section of the reference.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.