Star-free language

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".