Computer Science – Formal Languages and Automata Theory
Scientific paper
2011-11-15
Computer Science
Formal Languages and Automata Theory
Scientific paper
It is known that if a B\"uchi context-free language (BCFL) consists of scattered words, then there is an integer $n$, depending only on the language, such that the Hausdorff rank of each word in the language is bounded by $n$. Every BCFL is a M\"uller context-free language (MCFL). In the first part of the paper, we prove that an MCFL of scattered words is a BCFL iff the rank of every word in the language is bounded by an integer depending only on the language. Then we establish operational characterizations of the BCFLs of well-ordered and scattered words. We prove that a language is a BCFL consisting of well-ordered words iff it can be generated from the singleton languages containing the letters of the alphabet by substitution into ordinary context-free languages and the $\omega$-power operation. We also establish a corresponding result for BCFLs of scattered words and define expressions denoting BCFLs of well-ordered and scattered words. In the final part of the paper we give some applications.
Esik Zoltan
Okawa Satoshi
No associations
LandOfFree
On context-free languages of scattered words does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On context-free languages of scattered words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On context-free languages of scattered words will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-708426