Llenguatge lliure d'estrella

Un llenguatge regular es diu que és un llenguatge lliure d'estrella si es pot descriure amb una expressió regular construïda amb les lletres d'un alfabet, el símbol buit, tots els operadors booleans (incloent-hi complement i concatenació) però no la clausura de Kleen.^[1] Per exemple, el llenguatge de paraules de l'alfabet ${\displaystyle \{a,\,b\}}$que no té as consecutives es pot definir com ${\displaystyle (\emptyset ^{c}aa\emptyset ^{c})^{c}}$, on ${\displaystyle X^{c}}$denota el complement del subconjunt ${\displaystyle X}$de ${\displaystyle \{a,\,b\}^{*}}$.

Un exemple d'un llenguatge que no es lliure d'estrella és ${\displaystyle \{(aa)^{n}\mid n\geq 0\}}$.^[2]

Es va caracteritzar els llenguatges lliures d'estrella com aquells monoides sintàctics aperiòdics.^[3] També es poden caracteritzar lògicament com llenguatges que es poden definir per FO[<], la lògica de primer ordre sobre els nombres naturals amb la relació "més petit que", també es poden caracteritzar com llenguatges sense comptadors i com a llenguatges definits per una lògica temporal lineal.^[4][5][6]

Tots els llenguatges lliure d'estrella pertanyen a la classe de complexitat AC⁰.