Altezza star

Da Wikipedia, l'enciclopedia libera.

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

  • h(∅) := 0, h(μ) := 0
  • h(a) := 0 per ogni lettera aA.
  • h(EF) := h(E · F) := max(h(E), h(F))
  • h(Ec) := h(E) per ogni intero positivo c
  • h(E*) := h(E) + 1

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.

Voci correlate[modifica | modifica wikitesto]