starfree
Let $\mathcal{R}$ and $\mathcal{G}\mathcal{R}$ be the families of languages^{} represented by regular expressions^{} and generalized regular expressions respectively. It is wellknown that
$$\mathcal{R}=\mathcal{G}\mathcal{R}.$$ 
This means that the additional symbols $\cap $ and $\mathrm{\neg}$ in a generalized regular expressions are extraneous: removing them will not affect the representational power of the expressions with respect to regular languages.
What if we remove ${}^{*}$, the Kleene star symbol, instead? With regard to regular expressions, removing ${}^{*}$ severely limits the power of the expressions. By induction^{}, the represented languages are all finite. In this entry, we briefly discuss what happens when ${}^{*}$ is removed from the generalized regular expressions.
Definition. Let $\mathrm{\Sigma}$ be an alphabet. A language $L$ over $\mathrm{\Sigma}$ is said to be starfree if it can be expressed by a generalized regular expression without ${}^{*}$. In other words, a starfree language is a language that can be obtained by applying the operations^{} of union, concatenation^{}, and complementation to $\mathrm{\varnothing}$ and atomic languages (singleton subsets of $\mathrm{\Sigma}$) a finite number of times.
If we denote $\mathcal{S}\mathcal{F}$ the family of starfree languages (over some alphabet $\mathrm{\Sigma}$), then $\mathcal{S}\mathcal{F}$ is the smallest set of languages over $\mathrm{\Sigma}$ such that

•
$\mathrm{\varnothing}\in \mathcal{S}\mathcal{F}$,

•
$\{a\}\in \mathcal{S}\mathcal{F}$ for any $a\in \mathrm{\Sigma}$,

•
if $L,M\in \mathcal{S}\mathcal{F}$, then $L\cup M,LM,{L}^{c}\in \mathcal{S}\mathcal{F}$.
A shorter characterization^{} of a starfree language is a language with star height $0$ with respect to representations by generalized regular expressions.
In relations^{} to finite and regular languages, we have the following:
$$\mathcal{F}\subseteq \mathcal{S}\mathcal{F}\subseteq \mathcal{R},$$  (1) 
where $\mathcal{F}$ denotes the family of finite languages over $\mathrm{\Sigma}$.
Furthermore, it is easy to see that $\mathcal{S}\mathcal{F}$ is closed under Boolean operations, so that $\mathcal{S}\mathcal{F}$ contains infinite^{} languages, for example $\mathrm{\neg}\mathrm{\varnothing}$ represents ${\mathrm{\Sigma}}^{*}$. As a result, the first inclusion must be strict. This example also shows that languages representable by expressions including the Kleene star may still be starfree. Here’s another example: ${\{ab\}}^{*}$ over the alphabet $\{a,b\}$. This language can be represented as
$$\lambda \cup (ab{\mathrm{\Sigma}}^{*}\cap {\mathrm{\Sigma}}^{*}ab\cap \mathrm{\neg}({\mathrm{\Sigma}}^{*}{a}^{2}{\mathrm{\Sigma}}^{*})\cap \mathrm{\neg}({\mathrm{\Sigma}}^{*}{b}^{2}{\mathrm{\Sigma}}^{*}))$$ 
The expression above, of course, is not starfree, and includes the symbol $\lambda $ representing the empty word^{}. However, ${\mathrm{\Sigma}}^{*}$ is just $\mathrm{\neg}\mathrm{\varnothing}$, and $\lambda $ is just ${\mathrm{\Sigma}}^{*}\cap \mathrm{\neg}(a{\mathrm{\Sigma}}^{*})\cap \mathrm{\neg}(b{\mathrm{\Sigma}}^{*})$. Some substitutions show that ${\{ab\}}^{*}$ is indeed starfree.
Is the second inclusion strict? Are there regular languages such that representations by expressions including the Kleene star is inevitable? The following proposition^{} answers the question:
Proposition 1.
A language $L$ is starfree iff there exists a nonnegative integer $n$ such that, for any words $u\mathrm{,}v\mathrm{,}w$ over $\mathrm{\Sigma}$, $u\mathit{}{v}^{n}\mathit{}w\mathrm{\in}L$ iff $u\mathit{}{v}^{n\mathrm{+}\mathrm{1}}\mathit{}w\mathrm{\in}L$.
A language satisfying the second statement in the proposition is known as noncounting, so the proposition can be restated as: a language is starfree iff it is noncounting.
As a result of this fact, we see that languages such as ${\{{(ab)}^{2}\}}^{*}$ is not starfree, although it is regular^{}. Indeed, if we pick $u=v=w=ab$ as in the statement of the proposition above, we see that $u{v}^{n}w$ is in the language iff $u{v}^{n+1}w$ is not in the language, for any $n\ge 0$. Therefore, the second inclusion in chain (1) above is also strict.
The above proposition also strengthens chain (1): denote by $\mathcal{T}(\mathrm{\infty})$ the family of locally testable languages, then
$$\mathcal{T}(\mathrm{\infty})\subset \mathcal{S}\mathcal{F}\subset \mathcal{R}.$$  (2) 
The first inclusion is due to the fact that, for any $k$testable language $L$ (over some $\mathrm{\Sigma}$), we have
$${\mathrm{sw}}_{k}(u{v}^{k}w)={\mathrm{sw}}_{k}(u{v}^{k+1}w)$$ 
(the definition of ${\mathrm{sw}}_{k}(u)$ is found in the entry on locally testable languages). Note the first inclusion is also strict. For example, the language represented by ${(ab)}^{*}\cup {(ba)}^{*}$ is starfree but not locally testable.
References
 1 A. Ginzburg, Algebraic Theory of Automata, Academic Press (1968).
 2 A. Salomaa, Formal Languages^{}, Academic Press, New York (1973).
Title  starfree 

Canonical name  Starfree 
Date of creation  20130322 18:59:05 
Last modified on  20130322 18:59:05 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  16 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 68Q42 
Classification  msc 68Q45 
Synonym  star free 
Synonym  noncounting 
Synonym  noncounting 
Related topic  StarHeight 