星高

在理論計算機科學中，更確切地說，在形式語言的理論中，星高是衡量正則表達式和正則語言的結構復雜性的一個標準。一個正則表達式的星高等于該表達式中出現的星的xxx嵌套深度。一個正則語言的星高是該語言的任何正則表達式的最小星高。

更正式地說，有限字母表A上的正則表達式E的星高可以歸納為以下定義。對于A中的所有字母符號a。是表示空集的特殊正則表達式，ε是表示空詞的特殊表達式；E和F是任意的正則表達式。正則語言L的星高h(L)被定義為代表L的所有正則表達式中最小的星高。這里的直覺是，如果語言L有大的星高，那么它在某種意義上是內在復雜的，因為它不能通過簡單的正則表達式來描述，星高很低。

雖然計算一個正則表達式的星高很容易，但是確定一種語言的星高有時卻很棘手。例如，正則表達式然而，所描述的語言只是所有以a結尾的詞的集合：因此，該語言也可以通過表達式來描述為了證明這種語言確實具有1的星高，我們仍然需要排除它可以被更低星高的正則表達式所描述。對于我們的例子，這可以通過一個間接證明來完成。我們可以證明，星高為0的語言只包含有限數量的詞。由于所考慮的語言是無限的，它不可能是星高為0的。群體語言的星高是可以計算的：例如，{a,b}上的語言的星高是n，其中a和b的出現次數是全等的2n模。

在他對正則語言的星高的開創性研究中，Eggan（1963）建立了正則表達式、有限自動機和有向圖的理論之間的關系。我們回顧一下圖論和自動機理論的幾個概念。在圖論中，一個有向圖（digraph）G=（V，E）的循環等級r(G)被歸納定義如下。如果G是無環的，那么r(G)=0。如果G是強連接的，E是不空的，那么r(G)=1+是刪除頂點v和所有以v開始或結束的邊所產生的數字圖。如果G不是強連接的，那么r(G)等于G的所有強連接組件中的xxx循環等級。

一組有限的輸入符號Σ一組標記的邊δ，被稱為過渡關系。Q×(Σ∪{ε})×Q。這里ε表示空詞。一個初始狀態q0∈Q，一組狀態F，被區分為接受狀態F?Q。如果存在一條從初始狀態q0到F中某個最終狀態的有向路徑，并使用δ中的邊，使得沿路徑訪問的所有標簽的串聯產生單詞w，那么，一個單詞w∈Σ*就被ε-NFA所接受。

當談到具有狀態集Q的非確定性有限自動機A的數位圖特性時，我們自然要討論由其過渡關系誘導的具有頂點集Q的數位圖。正則語言L的星高等于所有具有接受L的ε-過渡的非確定有限自動機中的最小循環等級。