學習編譯原理Time07 ~ 有窮自動機
有窮自動機，是對一類處理系統(tǒng)建立的數(shù)學模型，這類系統(tǒng)具有一系列離散的輸入輸出信息和有窮數(shù)目的內(nèi)部狀態(tài)，系統(tǒng)只需要根據(jù)當前所處的狀態(tài)和當前面臨輸入信息就可以決定的后繼行為。每當系統(tǒng)處理了當前的輸入后，系統(tǒng)的內(nèi)部狀態(tài)也將發(fā)生改變。
舉一個有窮自動機的典型例子
●電梯控制裝置
▲輸入：顧客的乘梯需求（所要到達的層號）
▲狀態(tài)：電梯所處的層數(shù)+運動方向
電梯控制裝置并不需要記住先前全部的服務要求，只需要知道電梯當前所處的狀態(tài)以及還沒有滿足的所有服務請求
再來談談有窮自動機的模型
輸入帶：用來存放輸入符號串
讀頭：從左向右逐個讀取輸入符號，不能修改（只讀），也不能往返移動
有窮控制器：具有有窮個狀態(tài)數(shù)，根據(jù)當前的狀態(tài)和當前輸入符號控制轉(zhuǎn)入下一個狀態(tài)
接下來談談有窮自動機的表示——轉(zhuǎn)換圖
結(jié)點：有窮自動機的狀態(tài)
初始狀態(tài)（開始狀態(tài)）：只有一個，由start箭頭指向
終止狀態(tài)（接受狀態(tài)）：可以有多個，用雙圈表示
帶標號的有向邊：如果對于輸入a，存在一個從狀態(tài)p到狀態(tài)q的轉(zhuǎn)換，就在p、q之間畫一條有向邊，并標記上a
再深入談談有窮自動機定義（接受）的語言
給定輸入串x，如果存在一個對應于串x的從初始化狀態(tài)到某個終止狀態(tài)的轉(zhuǎn)換序列，則稱串x被該有窮自動機接收
第一個符號a的時候，狀態(tài)為0，然后兩個字符b，依然是狀態(tài)0，接著下一個字符a，還是狀態(tài)0，那么再下一個字符a就進入狀態(tài)1，接下來，遇到字符b就進入狀態(tài)2，再遇到字符b就進入狀態(tài)3，也就是終止狀態(tài)?？梢?，這個自動機可接受這個字符串a(chǎn)bbaabb。
由一個有窮自動機M接受的所有串構(gòu)成的集合稱為是該有窮自動機定義（接受）的語言，記為L(M)
L(M)=所有以abb結(jié)尾的字母表{a，b}上的串的集合
小浩筆記
