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?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityFor 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?
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.