首頁
隨機
附近
登入
設定
資助維基百科
關於維基百科
免責聲明
搜尋
星高
語言
監視
編輯
在
數學
裡,
正則表示法
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
(
E
c
) =
h
(
E
)
h
(
E
*
) =
h
(
E
)+ 1
正則語言
L
的
星高
定義為所有能表示
L
的正則表示式的星高的最小值。
可證明,語言
L
有星高0
若且唯若
其
語法么半群
為
非週期么半群
。
另見
編輯
星高問題
廣義星高問題
注釋
編輯
^
此處給出的定義為「廣義星高」,允許正規表示法使用「補集」運算子。