Indietro

ⓘ Altezza star




Altezza star
                                     

ⓘ Altezza star

In matematica, considerata una espressione regolare E sopra un alfabeto finito A, si dice altezza star di E lintero naturale che denotiamo con h definito dalle seguenti richieste ricorsive:

  • h E c:= h E per ogni intero positivo c
  • h E *:= h E + 1
  • h a:= 0 per ogni lettera a ∈ A.
  • h ∅:= 0, h μ:= 0
  • h E ∩ F:= h E F:= maxh E, h F)

Si definisce inoltre come altezza star h L di un linguaggio regolare L la minima delle altezze star delle espressioni regolari che esprimono L.

Marcel Schützenberger nel 1965 ha dimostrato che un linguaggio regolare L ha altezza star uguale a 0 se e solo se il suo monoide sintattico è aperiodico.