正则表达式和正则语言的星高

这个 星高 与理论计算领域（TOC）有关。它用于表示正则表达式和正则语言的结构复杂性。这里的复杂性与正则表达式中克莱恩星的最大嵌套深度有关。 这里需要注意的是，正则语言可以由非唯一但等价的正则表达式表示。这些正则表达式可能有不同的星高，这取决于它们的结构复杂性（即嵌套）。但是 正则语言的星高是唯一的数字，等于表示该语言的任何正则表达式的最小星高。 在这种情况下 广义星高 是一个合适的术语，它定义了Kleene星的最小嵌套深度，用广义正则表达式来描述语言。例如：

字母集合{a，b}上的语言“aba”可以使用正则表达式生成，

(a + b)* ...... (1) Star height = 1
(a* b*)* ...... (2) Star height = 2

但是我们认为最小的星高。因此，正规语言“aba”的恒星高度为1。

对于正则表达式，星高也定义为该表达式中出现的克莱恩星的最大嵌套深度。 为了正式表示正则表达式的星高，“h”，可以写为，

h( )=0，其中 是空的吗 h( )=0，其中 是空字符串吗 h（t）=0，其中t可以是字母表集合的任何终端符号 h（EF）=max（h（E），h（F）），其中E，F表示正则表达式 h（E*）=h（E）+1

例如：

• h（a*（b a*）*）=2
• h（（AB*）+（a*AB*）*b）*）=3
• h（a）=0

Eggan教授试图给出接受语言L的自动机的循环复杂度与语言的星高L之间的关系。 语言的星高L等于接受L的自动机的最小循环复杂度。 也可以说，自动机的循环复杂性 可访问（即通过删除所有不可访问状态以及与它们之间的任何转换而构造的自动机） 和 共可访问（即，如果有一个字符串s将我们从q带到一个标记状态，则称自动机的状态q为共可访问） 是通过状态消除法（或BMC算法）的不同可能执行获得的正则表达式的最小星高。

显然，恒星高度为零的正则语言只能代表有限数量的正则语言。广义星高理论认为，取正则表达式的补码不会导致星高的增加。这种考虑产生了有趣的结果。

例如，考虑一组字母{x，y}。正则语言“以x开头和结尾的所有字符串”的正则表达式的星高，即

h(x(x + y)*x+x) = 1, since only one level of Kleene nesting exists

但同样的语言也可以用正则表达式x来表示 ^Cx+x，因为 ^c表示输入字母表上所有字符串的集合。

Now, h(x ^c x + x) = 0, as no Kleene nesting present

因此，该语言的广义星高为0，即使其星高为1。