跳转到内容

星高

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

在數學裡，正則表示法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://wikicn.playgoteam.workers.dev/w/index.php?title=星高&oldid=25501412”