稀疏語言
在計算複雜性理論裡面, 稀疏語言是一種形式語言 (一堆字串的集合字串)，並且這語言內長度為n的字串個數，被一個n的多項式所限制住。 這種語言主要被用來研究NP這類語言與其他種類語言的關係。包含所有稀疏語言的複雜度類被稱作SPARSE。 稀疏語言會被叫做稀疏的原因是因為，對任何語言，長度為n的字串可能性個數總共有2n個，而如果某特定語言只有包含這一些字串裡面的多項式個數個，那這語言所包含字串的比例會隨著n的成長很快的減少。 所有一元語言都…
标签：#形式語言
共 5 篇文章
左遞歸
在電腦科學裡面，左遞歸是一種遞歸的特殊狀況。 在上下文無關文法內裡的說法，若一個非终结符號（non-terminal）r有任何直接的文法規則或者透過多個文法規則，推導出的句型（sentential form）其中最左邊的符號 又會出現r，則我們說這個非终结符號r是左遞歸的。 使用類似的方式我們可以定義出某文法本身是左遞歸的。 定義 "一個文法是左遞歸的，若我們可以找出其中存在某非终结符號A，最終會推導出來的句型(sentential f…
解釋 (邏輯)
解釋是一種將形式語言中的符號賦予意義的行為。許多使用於數學、邏輯及理論電腦科學的形式語言都會以純句法的方式定義，且直到給予某些解釋之前，不含有任何意義。一般研究形式語言的解釋的學科稱為形式語義學。 最常研究的形式邏輯為命題邏輯、謂詞邏輯及其衍生的邏輯，且此類的邏輯都已經有標準的方式來給出解釋。在這些情況下，解釋是一個可以提供目標語言的符號及符號字串外延的函數。例如，一個解釋函數可作用在謂詞T（表示「高」）上，並賦予其一個外延{a}（表示…
一元語言
在計算複雜度理論內，一元語言或者結算語言是一種形式語言 (由字串組成的集合)，裡面所有的字串都是像1k的形式(這裡的"1"可以是任何的符號）。例如，{1, 111, 1111}就是一個一元語言,或是像{1k | k是 質數}。這一類語言的複雜度類有時被叫做TALLY。 理論 "一元"這個名字的起源來自於我們可以將一元語言視為將語言轉成自然數後，再以一進位系統轉出來產生的語言。既然所有語言的字串均可以視作有限字母的集合，故字串的集合必然屬…
星高
在數學裡，正則表示法E在有限字母A的星高h（E）定義如下：: h(∅) = 0, h(ε) = 0, h（a）= 0, ∀ a ∈ A. h(E ∪ F) = h（EF）= max(h（E）, h（F）) h(Ec) = h（E） h(E*) = h（E）+ 1 正則語言L的星高定義為所有能表示L的正則表示式的星高的最小值。 可證明，語言L有星高0 若且唯若其么}-半群為非週期么半群。 另見 星高問題 *廣義星高問題 注釋