-2

http://i.stack.imgur.com/QoXru.png

a) M の遷移表を構築 b) 文字列 baba,baab,abab,abaaab のどれ c) L(M) の正規表現を与える

これがカバーされた日、私は実際に病気のために授業を欠席し、これに非常に混乱しています. ウィキペディアで DFA に関する情報を確認しましたが、さらに混乱しました。この問題に関連するこのトピックに関する洞察は大歓迎です!!

4

1 に答える 1

0

DFA = 決定論的有限状態オートマトン (検索)、

  • 開始状態があり ( を参照q0) >、
  • (ゼロ以上) 円で指定された非終末状態 (中の名前を参照)、
  • 二重の同心円で指定された終端 (終了) 状態、
  • イベントによってラベル付けされた線 (矢印) によって指定された状態遷移

DFA (DFSA) を使用して、入力のパターンを「認識する」ことができます。入力パターン (文字列) を DFA にフィードすると、DFA が状態間を遷移するときに、DFA は次のエントリを認識するか、エラーまたは認識されない結果を生成します。入力が終了したら、終了状態が終了/認識状態かどうかを確認します。

次のように実装されます。

states[] = { 'q0', 'q1', 'q2' }
events[] = { 'a', 'b' }
transition[]
transition['q0'] = []
transition['q1'] = []
transition['q2'] = []
transition['q0']['a'] = 'q1'
transition['q0']['b'] = 'q0'
transition['q1']['a'] = 'q1
transition['q1']['b'] = 'q2'
transition['q2']['a'] = 'q0'
transition['q2']['b'] = 'q1'
state = 'q0' #start state
terminal[]
terminal['q2'] = true # you can have more than one terminal/recognized state
terminal['q0'] = false # you can have more than one terminal/recognized state
terminal['q1'] = false # you can have more than one terminal/recognized state

上記のステートマシンを次のように実装できます (rubylike) terminal['q2'] = 1 # 複数の端末/認識状態を持つことができます

def DFArun( initstate, input )
    state = initstate
    each input.each do |inp|
        if !transition[ state, inp ].exists then
            return :notrecognized
        end
        state = transition [ state, inp ]
    end
    if terminal[ state ].exists then return :recognized
    else return :notrecognized end
end

特定の遷移が行われたときに発生するセマンティック アクションを使用して、DFSA または DFSM (Deterministic Finite State Machine) にさらに注釈を付けることができます。これは、特定の遷移 (「認識」) で出力を「発行」するか、特定のアクションを発生させることができます。DFA (DFSA、DFSM) を使用して、言語パーサーでトークンを認識したり、ファクトリー オートメーションやビジネス ワークフローを制御したりできます。

操作のために DFSM にロードできるファイルで DFSM の認識を簡単に表現でき、それによって、編集可能なファイルによって制御されるアクションを持つプログラムを構築できます。たとえば、単純な CSV ファイル、

#state,input,newstate,actions(optional)
q0,a,q1,none
q0,b,q0,none
q1,a,q1,none
q1,b,q2,none
q2,a,q0,none
q2,b,q1,none
init,q0
terminal,q2
于 2013-10-23T23:25:55.047 に答える