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.
… excerpt ends here. Continue reading the full article.
