星高

维基百科,自由的百科全书
跳转至: 导航搜索

數學裡,正則表示法E在有限字母A星高hE)定義如下:[1]:

  • h(∅) = 0, h(ε) = 0, ha)= 0, ∀ aA.
  • h(EF) = hEF)= max(hE), hF))
  • h(Ec) = hE
  • h(E*) = hE)+ 1

正則語言L星高定義為所有能表示L的正則表示式的星高的最小值。

可證明,語言L有星高0 若且唯若語法幺半群非週期么半群

另見[编辑]

注釋[编辑]

  1. ^ 此處給出的定義為「廣義星高」,允許正規表示法使用「補集」運算子。