Langue sans étoile - Star-free language

Un langage régulier est dit sans étoile s'il peut être décrit par une expression régulière construite à partir des lettres de l' alphabet , du symbole de l' ensemble vide , de tous les opérateurs booléens – y compris la complémentation – et la concaténation mais pas d' étoile de Kleene . Par exemple, la langue des mots sur l'alphabet qui n'ont pas de a consécutifs peut être définie par , où désigne le complément d'un sous-ensemble de . La condition équivaut à avoir une hauteur d'étoile généralisée nulle. ${\style d'affichage \{a,\,b\}}$${\displaystyle (\emptyset ^{c}aa\emptyset ^{c})^{c}}$${\style d'affichage X^{c}}$${\style d'affichage X}$${\displaystyle \{a,\,b\}^{*}}$

Un exemple de langage régulier qui n'est pas sans étoiles est . ${\displaystyle \{(aa)^{n}\mid n\geq 0\}}$

Marcel-Paul Schützenberger a caractérisé les langues sans étoiles comme celles avec des monoïdes syntaxiques apériodiques . Ils peuvent aussi être caractérisés logiquement comme des langues définissables dans FO[<], la logique du premier ordre sur les nombres naturels avec la relation inférieure à, comme les langues contre-libres et comme des langues définissables dans la logique temporelle linéaire .

Toutes les langues sans étoiles sont en AC ⁰ uniforme .

Voir également

• Hauteur d'étoile
• Problème généralisé de hauteur d'étoile
• Problème de hauteur d'étoile

Les références

• Lawson, Mark V. (2004). Automates finis . Chapman et Hall/CRC. ISBN 1-58488-255-7. Zbl  1086.68074 .
• Diekert, Volker ; Gastin, Paul (2008). "Langues définissables de premier ordre". Dans Jörg Flum ; Erich Grädel; Thomas Wilke (éd.). Logique et automates : histoire et perspectives (PDF) . Presse universitaire d'Amsterdam. ISBN 978-90-5356-576-6.