星高

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

在数学里，正则表示法E在有限字母A的星高h（E）定义如下：[1]:

  • h(∅) = 0, h(ε) = 0, h（a）= 0, ∀ a ∈ A.
  • h(E ∪ F) = h（EF）= max(h（E）, h（F）)
  • h(Ec) = h（E）
  • h(E*) = h（E）+ 1

正则语言L的星高定义为所有能表示L的正则表示式的星高的最小值。

可证明，语言L有星高0 当且仅当其语法幺半群为非周期幺半群。

另见[编辑]

注释[编辑]

  1. ^ 此处给出的定义为“广义星高”，允许正规表示法使用“补集”运算子。
取自“https://zh.wikipedia.org/w/index.php?title=星高&oldid=25501412”