語言識別器
形式語言中的四類基本語言，即字母表（有限符號集）中符號所組成的鏈的集合（見短語結構文法），分別對應著四類自動機。當某類自動機能接受、且只能接受某類形式語言（即相應類的輸入信號符號串）時，就稱該類自動機與相應類的形式語言等價。而該類自動機也就是相應形式語言的識別器。在模式識別中，當一類模式能用短語結構文法來描述時，相應的自動機可作為該類模式的識別器。這樣可以把有關形式語言文法的性質和相應自動機的性質結合起來研究，互相補充。通過自動機極易獲得相應形式語言文法的識別程式，識別程式乃是數字計算機編譯程式的核心，可用於完成對語言句子的語法分析，最終可用於模式識別。自動機是離散數字動態系統的數學模型。很多實際問題可以用自動機這樣一種數學模型來進行分析。例如按順時針方向或逆時針方向轉動某個規定角度的操作可以用一些基本動作組成的鍊表示,設R代表順時針方向轉動30°,L代表逆時針方向轉動30°,RLLRRR 就表示先順時針方向轉動30°，接著逆時針方向轉動60°，然後再順時針方向轉動90°。把一個數字鎖從初始的鎖住狀態轉移到開啟狀態這樣一個問題便可以用自動機的狀態集合(這個集合中包含有初始狀態和終止狀態)、輸入符號集合（上述例子中的{R、L}）以及狀態轉移函式這樣一種數學模型進行分析。對自動機的研究，開始於20世紀30年代。1936年英國數學家A.M.圖靈首先提出圖靈機概念。這種數學模型在物理上可以用一個有限控制器和一個輸入磁帶來進行討論。輸入磁帶上劃分為方格，一個方格可容納一個輸入符號或空白。在每一離散時刻，有限控制器處於某有限狀態集合中的一個狀態。通過掃描輸入磁帶上的符號和作一系列狀態轉移，來實現計算的功能。
自動機按存儲和狀態轉移特性分為四類。①有限自動機：它的狀態轉移，僅取決於當前輸入符號和有限控制器的當前狀態，當輸入符號不為空白而使狀態轉移時，磁頭便右移一個方格，對準下一個輸入符號。②下推自動機：它比有限自動機多一個下推存儲器，它的狀態轉移取決於輸入符號、有限控制器的當前狀態以及下推存儲器頂端的符號。在狀態轉移時，不僅能向右移動輸入磁頭，而且能改變下推存儲器的內容。③圖靈機：它雖然沒有下推存儲器，但在狀態轉移時可改寫輸入磁帶上的符號，並允許磁頭或左或右雙向移動。④線性有界自動機：它是圖靈機的一種特殊形式，它的磁頭移動時不會離開輸入符號串在磁帶上所占據區間。
如果一個自動機於初態時開始掃描一輸入符號串 x，經過一系列狀態轉移，在掃描完x 時恰好進入一個終態，則輸入符號串 x為該自動機所接受或識別。自動機理論的主要結果之一是上述各類自動機可以作為喬姆斯基層次中各類形式語言的識別器。具體地說，圖靈機接受的語言為0型語言,即遞歸可數集；線性有界自動機接受的語言為1型語言,即上下文敏感語言；下推自動機接受的語言為2型語言,即上下文無關語言；有限自動機接受的語言為3型語言，即正規集。
除上述經常討論的四種對應關係外，有些形式語言文法（如線性文法、順序文法、界限語言等）所對應的自動機還沒有專名，而有些自動機(如堆疊自動機等)所對應的文法也沒有專名。這表明文法和自動機同中有異，有些問題從文法入手研究較容易，而有些問題則從自動機入手研究較容易。
參考書目
J.E.Hopcroft,J.D.Ullmann,Introduction to Automate Theory， Languages, and Computation, Addison-Wesley Publ.Co., Reading Mass., 1979.
