Loading AI tools
Theoretical computer science concept From Wikipedia, the free encyclopedia
In formal language theory within theoretical computer science, an infinite word is an infinite-length sequence (specifically, an ω-length sequence) of symbols, and an ω-language is a set of infinite words. Here, ω refers to the first infinite ordinal number, modeling a set of natural numbers.
This article includes a list of general references, but it lacks sufficient corresponding inline citations. (October 2015) |
Let Σ be a set of symbols (not necessarily finite). Following the standard definition from formal language theory, Σ* is the set of all finite words over Σ. Every finite word has a length, which is a natural number. Given a word w of length n, w can be viewed as a function from the set {0,1,...,n−1} → Σ, with the value at i giving the symbol at position i. The infinite words, or ω-words, can likewise be viewed as functions from to Σ. The set of all infinite words over Σ is denoted Σω. The set of all finite and infinite words over Σ is sometimes written Σ∞ or Σ≤ω.
Thus an ω-language L over Σ is a subset of Σω.
Some common operations defined on ω-languages are:
The set Σω can be made into a metric space by definition of the metric as:
where |x| is interpreted as "the length of x" (number of symbols in x), and inf is the infimum over sets of real numbers. If then there is no longest prefix x and so . Symmetry is clear. Transitivity follows from the fact that if w and v have a maximal shared prefix of length m and v and u have a maximal shared prefix of length n then the first characters of w and u must be the same so . Hence d is a metric.
The most widely used subclass of the ω-languages is the set of ω-regular languages, which enjoy the useful property of being recognizable by Büchi automata. Thus the decision problem of ω-regular language membership is decidable using a Büchi automaton, and fairly straightforward to compute.
If the language Σ is the power set of a set (called the "atomic propositions") then the ω-language is a linear time property, which are studied in model checking.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.