Star-free language
In-game article clicks load inline without leaving the challenge.
In theoretical computer science and formal language theory, a regular language is said to be star-free if it can be described by a regular expression constructed from the letters of the alphabet, the empty word, the empty set symbol, all boolean operators – including complementation – and concatenation but no Kleene star. The condition is equivalent to having generalized star height zero.
It turns out some class of transformers exactly corresponds to star-free languages.
Examples
All finite languages are star-free. But no having stars does not mean that we are stuck to finite languages. Indeed, we can use the complementation to build infinite languages. Actually, the language Σ ∗ {\displaystyle \Sigma ^{*}} of all finite words over an alphabet Σ {\displaystyle \Sigma } is star-free because it is the complement of the empty set, Σ ∗ = ∅ ¯ {\displaystyle \Sigma ^{*}={\bar {\emptyset }}}.
Then, the language of words over the alphabet { a , b } {\displaystyle \{a,\,b\}} that do not have consecutive a's can be defined as Σ ∗ a a Σ ∗ ¯ {\displaystyle {\overline {\Sigma ^{*}aa\Sigma ^{*}}}}, first constructing the language of words consisting of a a {\displaystyle aa} with an arbitrary prefix and suffix, and then taking its complement, which must be all words which do not contain the substring a a {\displaystyle aa}.
An example of a regular language which is not star-free is ( a a ) ∗ {\displaystyle (aa)^{*}}, i.e. the language of strings consisting of an even number of "a". However, for ( a b ) ∗ {\displaystyle (ab)^{*}} where a ≠ b {\displaystyle a\neq b}, the language can be defined as Σ ∗ ∖ ( b Σ ∗ ∪ Σ ∗ a ∪ Σ ∗ a a Σ ∗ ∪ Σ ∗ b b Σ ∗ ) {\displaystyle \Sigma ^{*}\setminus (b\Sigma ^{*}\cup \Sigma ^{*}a\cup \Sigma ^{*}aa\Sigma ^{*}\cup \Sigma ^{*}bb\Sigma ^{*})}, taking the set of all words and removing from it words starting with b {\displaystyle b}, ending in a {\displaystyle a} or containing a a {\displaystyle aa} or b b {\displaystyle bb}. However, when a = b {\displaystyle a=b}, this definition does not create ( a a ) ∗ {\displaystyle (aa)^{*}}.
Characterisations
Via aperiod syntact monoids
Marcel-Paul Schützenberger characterized star-free languages as those with aperiodic syntactic monoids. Said differently, they are characterised as languages accepted by some aperiodic finite-state automaton (known as counter-free languages).
Logical characterisation
They can also be characterized logically as languages definable in FO[<], the first-order logic over the natural numbers with the less-than relation. First-order variables denote positions in words and < means that a position is strictly before another one. Here are some examples.
- The language Σ ∗ {\displaystyle \Sigma ^{*}}(all words) is captured by the tautology ⊤ {\displaystyle \top } (no constraints on the words)
- The language of that have no consecutive a's is defined by the FO[<] formula ∀ x ∀ y ( ( a ( x ) ∧ x < y ∧ ¬ ∃ z ( x < z ∧ z < y ) ) ⟹ ¬ a ( y ) ) {\displaystyle \forall x\forall y\,{\Big (}{\big (}a(x)\land x<y\land \neg \exists z(x<z\land z<y){\big )}\implies \neg a(y){\Big )}} meaning for all positions x {\displaystyle x} and y {\displaystyle y}, if x {\displaystyle x} contains letter a {\displaystyle a} and if y {\displaystyle y} is the position after x {\displaystyle x} (y {\displaystyle y} is after x {\displaystyle x} but there is no positions in between x {\displaystyle x} and y {\displaystyle y}), then there is y {\displaystyle y} does not contain letter a {\displaystyle a}.
They can also be characterized by formulas in linear temporal logic. Here are some examples.
- Again, The language Σ ∗ {\displaystyle \Sigma ^{*}} is captured by the tautology ⊤ {\displaystyle \top }
- The language of that have no consecutive a's is defined by the formula in linear temporal logic G ( a → X ¬ a ) {\displaystyle G(a\rightarrow X\lnot a)} where is the meaning is as follows: always (operator G {\displaystyle G}), if there is letter a {\displaystyle a} then at the next step (operator X {\displaystyle X}) there is no letter a {\displaystyle a}.
Algorithms
Membership
All star-free languages are in uniform AC0. More precisely, given a star-free language L {\displaystyle L}, deciding whether a word belongs to L {\displaystyle L} is in uniform AC0.
Non-emptiness
It takes non-elementary time to decide whether a star-free language over two letters is empty. More precisely, the non-emptiness problem of starfree language is defined as follows.
- Input: a string in the symbols of { a , b } {\displaystyle \{a,\,b\}}, empty set, concatenation, union, intersection, and complement.
- Output: Whether this language contains any element.
This problem is decidable, but only in nonelementary time. As immediate corollaries, it is decidable but nonelementary to decide whether two starfree languages are equal, are disjoint, or contain one another.