跳转到内容

星高

维基百科,自由的百科全书

数学里,正则表示法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. ^ 此处给出的定义为“广义星高”,允许正规表示法使用“补集”运算子。