自動機應(yīng)用實例

711有限自動機實例

有限狀態(tài)自動機有限狀態(tài)自動機是最簡單的一類語言識別器，也是有限狀態(tài)系統(tǒng)的一種模型。有限狀態(tài)自動機確定型（DFA）不確定型（NFA）確定型有限狀態(tài)自動機（DFA）定義：確定的有限自動機（DFA）是一個五元組

M=（Q,Σ,δ,q0,F）其中Q:有限狀態(tài)集,Σ:字母表,q0∈Q是初始狀態(tài),F?Q是終止?fàn)顟B(tài)集,δ:Q×EQ稱為狀態(tài)轉(zhuǎn)換函數(shù)。DFA——實例例.某公共汽車始發(fā)站，在始發(fā)站有乘客的條件下，每隔一固定時間段發(fā)出一班車。車站發(fā)出一班車后,如果在下一發(fā)車時刻車站沒有乘客,則停一班次,當(dāng)再等到下一發(fā)車時刻時,不管始發(fā)站有沒有乘客,則車站必發(fā)出一班車。

用有限自動機刻畫這一過程：設(shè)x0,x1分別表示始發(fā)站沒有乘客和有乘客,為自動機的輸入信息；自動機的狀態(tài)有兩個,分別為上一發(fā)車時刻沒有發(fā)車和發(fā)車兩個狀態(tài),我們分別用q0,q1表示這兩個狀態(tài)，設(shè)q0為初始狀態(tài)。此有限自動機M=（Q,Σ,δ,q0,F）可表述: Q={q0,q1},Σ={x0,x1},F?Q δ=Q×Σ→Q其中δ(q0,x0)=q1,δ(q0,x1)=q1, δ(q1,x0)=q0,δ(q1,x1)=q1DFA——實例\x0x1q0q1q1q1q0q1狀態(tài)轉(zhuǎn)換表：狀態(tài)轉(zhuǎn)換圖：q1x0x1\x0x1q0q1q1q1q0q1q0\x0x1q0q1q1q1q0q1\x0x1q0q1q1q1q0q1\x0x1q0q1q1q1q0q1startx0/x1檢測字符串s1、s2對于如下有限自動機，待檢測字符串s1、s2a0a1a4a3a2a5a6青島春風(fēng)期景區(qū)S1=青島風(fēng)景區(qū)S2=青島大學(xué)NFA——實例例.為了搞清基因表達之間的相互制約關(guān)系，科學(xué)家采用了其有正（positive）、負（negative）控制的基因網(wǎng)絡(luò)的一個形式化模型-有限狀態(tài)自動機。具體地講，基因被激活后，將在一段時間后出現(xiàn)產(chǎn)生物蛋白質(zhì)；基因被抑制后，在一段時間后停止出現(xiàn)蛋白質(zhì)。如果把單個基因的狀態(tài)看成on和off，產(chǎn)生物（例如蛋白質(zhì)）的狀態(tài)表示成absent和present，就得了一個基因的邏輯模型。進一步地，把單個基因X的狀態(tài)on和off以及X的產(chǎn)生物狀態(tài)present和absent看作自動機的輸入，并分別用符號α、γ、β和λ表示，可進一步構(gòu)造其對應(yīng)的有限狀態(tài)自動機。NFA——實例一個基因X及其產(chǎn)生物蛋白質(zhì)組成的非確定型有限狀態(tài)自動機G=（Q,Σ,Δ,q,F），其中狀態(tài)集Q={0,1,2,3,4}，其中4為異常狀態(tài)；輸入字符集