自動(dòng)機(jī)應(yīng)用實(shí)例

711有限自動(dòng)機(jī)實(shí)例

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

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——實(shí)例例.某公共汽車始發(fā)站，在始發(fā)站有乘客的條件下，每隔一固定時(shí)間段發(fā)出一班車。車站發(fā)出一班車后,如果在下一發(fā)車時(shí)刻車站沒有乘客,則停一班次,當(dāng)再等到下一發(fā)車時(shí)刻時(shí),不管始發(fā)站有沒有乘客,則車站必發(fā)出一班車。

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