自動機理論

數理語言學中研究抽象自動機的理論。抽象自動機是一種能夠識別語言的抽象的裝置，它不是具有物理實體的機器，而是表示計算機運算方式的抽象的邏輯關係系統，這樣的抽象自動機可以用來檢驗輸入的符號串是不是語言中合格的句子，如果是合格的句子，自動機就接收它，如果不是，就不接收它。如圖所示：

自動機可分為有限自動機、後進先出自動機、線性有界自動機、圖靈機等幾種。它們對語言的識別能力各不相同。

美國語言學家N.喬姆斯基等人建立了形式文法和自動機之間的聯繫，證明語言的形式文法與自動機之間存在著如下的對應關係：①若某一語言能用圖靈機來識別，則它就能用 O型文法生成，反之亦然；②若某一語言能用線性有界自動機來識別，則它就能用上下文敏感文法生成，反之亦然；③若某一語言能用後進先出自動機來識別，則它就能用上下文自由文法生成，反之亦然；④若某一語言能用有限自動機來識別，則它就能用有限狀態文法生成，反之亦然。

這種關於形式文法與自動機的關係，反映了語言的生成過程與識別過程的內在聯繫，它已成為計算機科學的基石之一。這是語言學對於現代自然科學發生影響的一個明證。