- is the set of all ''finite'' words over Σ. Every finite word has a length, which is, obviously, a natural number. It should be noted that, given a word ''w'' of length ''n'', ''w'' can be viewed as a function from the set {0,1,...,''n''-1} → Σ. The infinite words, or ω-words, can likewise be viewed as functions from to Σ, with the value at ''i'' giving the symbol at position ''i''. The set of all infinite words over Σ is denoted Σω. The set of all finite ''and'' infinite words over Σ is sometimes written Σ∞.
Thus, an ω-language ''L'' over Σ is a Subset of Σω.
Some common operations defined on ω-languages are:
- ''Intersection and union''. Given ω-languages ''L'' and ''M'', both ''L'' ∪ ''M'' and ''L'' ∩ ''M'' are ω-languages.
- ''Left catenation''. Let ''L'' be an ω-language, and ''K'' be a language of finite words only. Then ''K'' can be catenated on the left ''only'' to ''L'' to yield the new ω-language ''KL''.
- ''Omega (infinite iteration)''. As the notation hints, the operation ()ω is the infinite version of the Kleene Star operator on finite-length languages. Given a formal language ''L'', ''L''ω is the ω-language of all infinite sequence of words from ''L''; in the functional view, of all functions →''L''.
- ''Prefixes''. Let ''w'' be an ω-word. Then the formal language Pref(''w'') contains every ''finite'' Prefix of ''w''.
- ''Limit''. Given a finite-length language ''L'', an ω-word ''w'' is in the ''limit'' of ''L'' if and only if Pref(''w'') ∩ ''L'' is an ''infinite'' set. In other words, for an arbitrarily large natural number ''n'', it is always possible to choose some word in ''L'', whose length is greater than ''n'', ''and'' which is a prefix of ''w''. The limit operation on ''L'' can be written ''L''δ or .
The set Σω can be made into a Metric Space by definition of the Metric d:Σω × Σω → R as:
|
