首页
随机
附近
登录
设置
资助维基百科
关于维基百科
免责声明
搜索
星高
语言
监视
编辑
在
数学
里,
正则表示法
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
若且唯若
其
语法幺半群
为
非周期幺半群
。
另见
编辑
星高问题
广义星高问题
注释
编辑
^
此处给出的定义为“广义星高”,允许正规表示法使用“补集”运算子。