形式言語 と オートマト 第3-2回 鳥取大学工学研究科 情報エレクトロニクス専攻 田中美栄子 有限オートマトン (Finite State Automata: FSA) の 5字組による表示 形式言語とオートマト 有限オートマトン (Finite State Automata: FSA) FSA: M = <Q, Σ, d, q, F> の5字組 ・ Q : 状態の集合 ・ Σ : 使用するアルファベット ・ d : 動作関数 ・ q :初期状態 ・ F : 受理状態の集合 形式言語とオートマト 有限オートマトンの例 M = <Q, Σ, d, q, F> Q {r , s, t} {a, b} :Q Q ( r , a ) s, ( r , b) r , ( s, a ) t , ( s, b) r , (t , a ) t , (t , b) r q0 r F {t} 形式言語とオートマト b r a b s a b t a 有限オートマトン (Finite State Automata: FSA) の変遷を様相を使って見る 様相(configuration)=時点表示 形式言語とオートマト 様相でオートマトンの変遷を 追う 様相の定義=(オートマトンの状態,未読の入力) オートマトンの動作に従い、状態が変化する 未読入力が減ってゆく ->> 最後に (終状態, 空列)となったら受理、 そうでなければ受理しない 形式言語とオートマト 入力abbaが受理されるかどう かを 様相(configuration)を使って調べる 1. 文字列 M = abaaを入力 2. これを1文字ずつ読んで行く 3. 読み終わったら$が入力される(εは空列) 4. その状態で受理状態のどこかにいれば Mは受理される 形式言語とオートマト | 様相(configuration)の変遷 (q 0 , a1a 2 a 3 a n ) (q1 , a 2 a 3 a n ) M M (q1 , a 3 a n ) (q n , ) M M * (q0 , a1a2 a3 an ) (qn , ) M 形式言語とオートマト “有限オートマトンの例” で示したオートマトンMにabaaを入力し てみる M = <Q, Σ, d, q, F> Q {r , s, t} {a, b} :Q Q ( r , a ) s, ( r , b) r , ( s, a ) t , ( s, b) r , (t , a ) t , (t , b) r q0 r F {t} 形式言語とオートマト (r , abba) ( s, bba) M M (r , ba) (r , a) ( s, ) M M 受理状態でない s で終了 →拒否 “有限オートマトンの例” で示したオートマトンMにaaaaを入力し てみる M = <Q, Σ, d, q, F> (r , aaaa) ( s, aaa) Q {r , s, t} {a, b} :Q Q ( r , a ) s, ( r , b) r , ( s, a ) t , ( s, b) r , (t , a ) t , (t , b) r q0 r F {t} 形式言語とオートマト M M (t , aa) (t , a) (t , ) M M 受理状態 t で終了 →受理 非決定性FAの様相(=時点表示) 状態rでa を入力すると遷移は2種類 ( r , aab ) ( r , ab ) ( r , b) ( r , ε ) M M M ( r , ab ) (s, b) ? M M 受理状態でないrで入力が尽きるか、 状態sでbを読めない、のどちらにし てもaabは受理されない 形式言語とオートマト a a r b s a t 形式言語とオートマト 非決定性有限オートマトンとは!? (前回までの授業) 決定性有限オートマトン すべての状態ですべての入力に対して、 遷移先が唯一 a 形式言語とオートマト 非決定性有限オートマトンとは!? 非決定性有限オートマトン 一つの入力に対し、遷移先が唯一でない a a 形式言語とオートマト 非決定性有限オートマトンとは!? 非決定性有限オートマトン 決定性有限オートマトンと同様に五字組みで表す 但し、動作関数σは以下のように表す Q σ:Q×Σ→2 形式言語とオートマト 非決定性有限オートマトンとは!? 以下のオートマトンを五字組みで表すと・・・ a a r b 形式言語とオートマト s a t 非決定性有限オートマトンとは!? Q {r , s, t} {a, b} Q :Q 2 (r , a) {r , s}, (r , b) {r}, ( s, a) {t}, ( s, b) , (t , a) , (t , b) q0 r F {t} 形式言語とオートマト a a r b s a t 非決定性有限オートマトンと は!? 動作関数の読み方は・・・ :Q 2 (r , a) {r , s}, (r , b) {r}, ( s, a) {t}, ( s, b) , (t , a) , (t , b) Q r a a s b 状態がrで入力記号がaである時は、 rとsどちらに遷移しても良い 形式言語とオートマト a t 非決定性有限オートマトンとは!? 動作関数の読み方は・・・ : Q 2Q (r , a) {r , s}, (r , b) {r}, ( s, a) {t}, ( s, b) , (t , a) , (t , b) a a r b 状態がtで入力記号がaである時は、 遷移先がないという事 形式言語とオートマト s a t 非決定性有限オートマトンとは!? この非決定性FSAにbaaを入力する a a r b 形式言語とオートマト s a t 非決定性有限オートマトンとは!? この非決定性FSAにbaaを入力する a b a r b 形式言語とオートマト s a t 非決定性有限オートマトンと は!? この非決定性FSAにbaaを入力する a a ar b 形式言語とオートマト s a t 非決定性有限オートマトンと は!? この非決定性FSAにbaaを入力する a a ar b 形式言語とオートマト s a t 非決定性有限オートマトンと は!? 状態r 状態rの の時、 時、 aaが されると が入力 入力 されると この非決定性FSAに baa を入力する 2種の の遷移 遷移がある がある a2種 a ar b 形式言語とオートマト as a t どちらに遷移しても良い 非決定性有限オートマトンと は!? baaを入力すると、三種類の遷移がある。 a a r b 形式言語とオートマト s a t 非決定性有限オートマトンと は!? baaを入力すると、三種類の遷移がある。 ( r , baa ) ( r , aa ) ( r , a ) ( r , ) M M M ( r , baa ) ( r , aa ) ( r , a ) ( s, ) M M M ( r , baa ) ( r , aa ) ( s, a ) (t , ) M M M b ,a 受理状態であるtで遷移が終わって いるので、baaは受理される 形式言語とオートマト r a s a t 非決定性有限オートマトンと は!? この非決定性FSAにaabを入力する a a r b 形式言語とオートマト s a t 非決定性有限オートマトンと は!? この非決定性FSAにaabを入力する a a a r b 形式言語とオートマト s a t 非決定性有限オートマトンとは!? この非決定性FSAにaabを入力する a a ar b 形式言語とオートマト s a t 非決定性有限オートマトンとは!? この非決定性FSAにaabを入力する a a br b 形式言語とオートマト s a t 入力bで遷移できるのは 最終的にこの遷移のみ お疲れさまでした。 小テストです。 形式言語とオートマト
© Copyright 2024 ExpyDoc