Înălțimea stelei

În matematică , considerată o expresie regulată E peste un alfabet finit A , numim stea înălțime a lui E întregul natural pe care îl notăm cu h ( E ) definit de următoarele cereri recursive:

• h (∅): = 0, h (μ): = 0
• h ( a ): = 0 pentru fiecare literă a ∈ A.
• h ( E ∩ F ): = h ( E F ): = max ( h ( E ), h ( F ))
• h ( E ^c ): = h ( E ) pentru fiecare număr întreg pozitiv c
• h ( E ^* ): = h ( E ) + 1

Mai mult, înălțimea stelei h ( L ) a unui limbaj regulat L este definită ca minimul înălțimilor stelelor ale expresiilor regulate care exprimă L.

Marcel Schützenberger în 1965 a demonstrat că un limbaj regulat L are înălțimea stelelor egală cu 0 dacă și numai dacă monoidul său sintactic este aperiodic .

Elemente conexe

• Problema înălțimii stelelor
• Problemă generalizată a înălțimii stelelor

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică