星高

正則語言L的星高定義為所有能表示L的正則表示式的星高的最小值。

基本介紹

• 中文名：星高
• 學科：數學
• 領域：數學
• 相關術語：正則語言

簡介

在數學里，正則表示法E在有限字母A的星高h（E）定義如下：:

• h(∅) = 0,h(ε) = 0,h（a）= 0, ∀a∈A.
  
• h(E∪F) =h（EF）= max(h（E）,h（F）)
  
• h(E⁰) =h（E）
  
• h(E^*) =h（E）+ 1
  

正則語言L的星高定義為所有能表示L的正則表示式的星高的最小值。

可證明，語言L有星高0若且唯若其語法么半群為非周期么半群。

正則語言

在字母表集合Σ上的正則語言定義如下：

（1）空集合Ø是正則語言

（2）只包含一個空字元串的語言{ε}是正則語言

（3）對所有，{a}是正則語言

（4）若A,B是正則語言，則(kleene星號)都是正則語言

除此之外都不是正則語言

如果一個語言不是正則語言，它需要一個存儲器至少是Ω(log logn)的自動機才能辨認。換句話說，DSPACE(o(log logn))等於所有正則語言的集合。實際上，大部分的非正則語言需要至少O(logn)的空間。

另見

• 星高問題
  
• 廣義星高問題