首页
随机
附近
登录
设置
资助维基百科
关于维基百科
免责声明
搜索
星高
语言
监视
编辑
在
數學
裡,
正則表示法
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
若且唯若
其
語法幺半群
為
非週期么半群
。
另見
编辑
星高問題
廣義星高問題
注釋
编辑
^
此處給出的定義為「廣義星高」,允許正規表示法使用「補集」運算子。