有限狀態語言（finite state language）是2011年公布的語言學名詞。
基本介紹
- 中文名：有限狀態語言
- 外文名：finite state language
- 所屬學科：語言學
- 公布時間：2011年
定義,出處,
定義
一種語法模型。由喬姆斯基1957年提出。按照從左到右的線性順序，選擇語言成分並生成句子，先選擇的成分會制約後面所選的成分。這類語法生成有限狀態語言。
出處
《語言學名詞》第一版。
有限狀態語言
相關詞條
- 有限狀態語言
有限狀態語言（finite state language）是2011年公布的語言學名詞。定義一種語法模型。由喬姆斯基1957年提出。按照從左到右的線性順序，選擇語言成分並生成句子，先選擇的成分會制約後面所選的成分。這類語...
- 有限狀態語法
有限狀態語法的生成能力小於2型語法，它不能生成全部合格的句子，只能生成其中一部分。用這種語法生成的語言叫作“有限狀態語言”。喬姆斯基（Noam Chomsky，1928— ）指出，自然語言有許多不是有限狀態語言，自然語言中互相依存的詞可能被另一些詞隔開，因此用有限狀態語法來描寫人類的語言是不充分的。有限狀態語言可以...
- 有限狀態自動機
有限狀態自動機識別的語言是正規語言。有限狀態自動機除了它在理論上的價值，還在數字電路設計、詞法分析、文本編輯器程式等領域得到了套用。自動機接受的所有字串構成了自動機識別的語言 L(M)。非確定有限狀態自動機 一個非確定有限狀態自動機（NFA "Non-deterministic finite automaton"）M 是由下述元素構成的五元組...
- 擴展狀態變遷模型語言
Estelle是一種基於擴展有限狀態自動機的形式化描述語言，是由ISO/TC97/SC21/WGI/SUBGROUP B定義的。技術簡介 Estelle是一種基於擴展有限狀態自動機的形式化描述語言，是由ISO/TC97/SC21/WGI/SUBGROUP B定義的。它的主要思想是將系統分成許多互連的模組，每個模組都是一個擴展有限狀態自動機，利用Pascal語言成份來...
- 確定有限狀態自動機最小化
重複反轉操作，就可以得到原語言的最小DFA。Brzozowski算法在最壞情況下的複雜度是指數的，因為存在這樣的正則語言，其反序的最小DFA的規模是原語言DFA規模的指數大。但通常來說這個算法比最壞情況表現得要好。NFA最小化 以上的步驟都對DFA有效，可是劃分的方法並不適用於非確定有限狀態自動機(NFA)。雖然窮舉搜尋...
- 確定有限狀態自動機
經典的DFA不能識別的簡單語言的例子是括弧語言，就是由正確配對的括弧組成的語言，比如 (()())。由形如ab的字元串組成的語言，就是有限數目個a，隨後是相等數目個b。可以證明沒有DFA有足夠狀態來識別這種語言（通俗地說，因為需要至少2n個狀態，而n是不恆定的）。其他 能被確定有限狀態自動機識別的語言是正則...
- 摩爾型有限狀態機
Moore機器或Moore圖的狀態圖是將輸出值與每個狀態相關聯的圖。 摩爾機器是一個輸出生產者。與Mealy機器的關係 由於Moore和Mealy機器都是有限狀態機的類型，它們同樣具有表現力：任何一種類型都可以用來解析常規語言。Moore機器和Mealy機器之間的區別在於，在後者中，轉換的輸出由當前狀態和當前輸入的組合決定（ 作為 的...
- 非確定有限狀態自動機
非確定有限狀態自動機區別於確定有限狀態自動機（DFA），它的下一個可能狀態是唯一確定的。儘管DFA和NFA有不同的定義，在形式理論中可以證明它們是等價的；就是說，對於任何給定NFA，都可以構造一個等價的DFA，反之亦然：通過使用冪集構造。兩種類型的自動機只識別正則語言。非確定有限自動機有時被稱為有限類型的子...
- 公式處理語言
巴黎工藝學院(Institute Universite de Technologie)計算機科學系的M．Laplace一直在致力於改進原有的FORMAC語言。FORMAC(FORmula MAnipulation Compiler)是從1964年以來搞了很久的一個語言。最初從事這一語言的人都已轉走，因此這個語言的內部問題一度處於無人過問狀態。這是一個功能有限的語言，只能處理多項式運算和初等...
- 有限自動機
在計算機科學中，可以找到許多有限狀態系統的例子，如計算機本身也可以是認為是一個有限狀態系統，儘管其可能狀態數目很大，但仍然是有限的，有限自動機理論是設計這些系統的有效工具，研究有限狀態系統的重要原因是概念的自然性和套用的廣泛性，例如，在編譯器中，人們主要用自動機來識別程式設計語言中的單詞，但是它不...
- 功能規範和描述語言
CCITT建議的一種高級語言簡稱SDL，用於電信系統的描述，包括對系統應具有行為的描述（這種描述稱為功能規範）以及對系統實際具有行為的描述。用SDL描述系統的目的是為了使人們能夠唯一地定義、分析和解釋系統。描述方式 SDL以激勵/回響方式來描述系統的性能和行為。這種方式以擴展有限狀態自動機概念為基礎，將系統的狀況...
- 有限自動機理論
第四章 正則語言 4.1 正則語言與有限狀態自動機 4.1.1 正則表達式對應有限狀態自動機 4.1.2 正則語言的等價模型 4.2 正則語言的泵浦引理 4.3 正則語言對運算的封閉性 4.4 正則語言類中的判定算法 習題四 第五章 下推自動機 5.1 下推自動機 5.1.1 確定的下推自動機 5.1.2 不確定的下...
- 形式語言
設S⊆Σ*是一個語言，S的補語言定義為集合{ω|ω∈Σ*且ω∉S} 語言的表示方法 一個形式語言可以通過多種方法來限定自身，比如：枚舉出各個字串（只適用於有限字串集合）。通過形式文法來產生（參見喬姆斯基譜系）。通過正則表達式來產生。通過某種自動機來識別，比如圖靈機、有限狀態自動機。套用 程式語言 ...
- 語言機制
語言機制（language faculty）該機制的特徵：⑴人類進化的產物，是一種帶有普遍性的先天機制，受UG原則的支配和調節；⑵以模組（modular）形式運作，每個模組掌管一定的語法功能，模組間既獨立又相互作用。如句法和音系屬不同模組，它們各自的表達式由各自模組的原則支配，模組之間又有接口；⑶語言機制具有初始狀態（...
- 馬爾可夫模型狀態
一個馬爾可夫鏈模型可表示為=（S，P， Q），其中各字母的含義如下：S 是系統所有可能的狀態所組成的非空的狀態集，有時也稱之為系統的狀態空間，它可以是有限的、可列的集合或任意非空集。狀態之間關係滿足馬爾可夫性質，不同狀態之間轉移有一個確定的機率分布，通常用一系列有向圖來來描述狀態之間的關係。馬爾...
- 語言發展
語言獲得理論 關於兒童為什麼能在短短几年內掌握結構極為複雜的語言這個問題，有各種不同解釋。其中典型的有先天能力論、環境論和認知基礎論。先天能力論 N.喬姆斯基提出先天語言能力的主張，認為人類具有先天的語言能力，亦即先天的、內在的語法規則系統。這種規則系統是在有限的基本語言素材基礎上，通過先天語言獲得裝置...
- 句法結構
《句法結構》是美國語言學家喬姆斯基創作的語言學著作，首次出版於1957年。《句法結構》提出三種句法模型：（1）有限狀態模型，構想一個機器具有有限數量的語詞結合狀態，其困難在於語言太複雜。這種構成句子不能達到簡化的目的。（2）短語結構規則，以先有的一套短語結構改寫規則作為形成句子的規則，從結構上分析句子如何...
- 自動機理論
該自動機識別的語言是否為空集；該自動機識別的語言是否為有限集；該自動機是否與另一個確定有限狀態自動機識別同一個的語言。理論發展 美國語言學家N.喬姆斯基等人建立了形式文法和自動機之間的聯繫，證明語言的形式文法與自動機之間存在著如下的對應關係：①若某一語言能用圖靈機來識別，則它就能用 O型文法生成，...
- 自動機
一個語言可以被認為是所有可能字的子集。所有可能字的集合可以被認為是所有可能的字元串串接的集合。形式上說，所有可能字元串的集合叫做自由么半群。它被指示為 Σ ，上標 * 被稱為Kleene星號。形式描述 自動機可以表示為5-元組，這裡的:Q 是狀態的非空有窮集合。∑ 是符號的有限集合，我們稱為這個自動機接受...
- HMMs
HMMs是指隱馬爾科夫模型，是一種算法模型，用於語言信號處理，是對語音信號的時間序列結構建立統計模型。模型介紹 為了分析語音信號而提出的一個算法模型.在語音信號處理上用的比較多 隱馬爾可夫模型（HMMs）是對語音信號的時間序列結構建立統計模型，可將之看作一個數學上的雙重隨機過程：一個是用具有有限狀態數的...
- 喬姆斯基文法
在理論計算機科學中，自動機理論是對抽象機和它們能解決的問題的研究。自動機理論密切關聯於形式語言理論，因為自動機經常按它們所能識別的形式語言類來分類。自動機是有限狀態機（FSM）的數學模型。FSM是給定符號輸入，依據（可表達為一個表格的）轉移函式“跳轉”過一系列狀態的一種機器。在常見的FSM的“米利型有限...
- 邁希爾-尼羅德定理(數學術語)
Myhill–Nerode 定理的一個結論是語言L是正則的(就是說可被有限狀態機接受)，若且唯若R的等價類的數目是有限的。直接推論是如果一個語言定義等價類的無限集合，它就不是正則的。這個推論經常被用來證明一個語言不是正則的。例如，由可以被 3 整除的二進制數組成的語言是正則的。有三個等價類 3 - 被 3 除的...
