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?
$\begingroup$
$\endgroup$
4
-
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
Add a comment
|
$\begingroup$
$\endgroup$
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.
