このディレクトリの索引

% 以下のサイトは # # プログラム14.14: 言語(*a*bcd)* を受理するNDFA # # # \+(a) # ------------ # | | # | | # | v a # ---- 状態集合_5 {5} ---------- # | # ^ | # \+(a) | | # | v # a \+(b) \+(b) # 状態集合_0 {0} ---------> 状態集合_1 {1} ---------> 状態集合_4 {4} --------- # | # ^ | | ^ | # | | | | | # | | b | b -------------- # d | | | # | | | # | v | # | # 状態集合_3 {3} <--------- 状態集合_2 {2} <------------ # c # # 図14.5: 非決定性有限オートマトン # '言語(*a*bcd)*を受理する非決定性有限オートマトン'(_入力記号ならび) :- '言語(*a*bcd)*初期状態'(_状態), '言語(*a*bcd)*を受理する非決定性有限オートマトン'(_状態,_入力記号ならび). '言語(*a*bcd)*を受理する非決定性有限オートマトン'(_状態,[_記号|R_1]) :- '言語(*a*bcd)*'(_状態集合,_記号,_状態集合_1), 状態集合(_状態集合,_状態), 状態集合(_状態集合_1,_状態_1), '言語(*a*bcd)*を受理する非決定性有限オートマトン'(_状態_1,R_1),!. '言語(*a*bcd)*を受理する非決定性有限オートマトン'(_状態,[]) :- '言語(*a*bcd)*受理状態'(_状態). '言語(*a*bcd)*初期状態'(0). '言語(*a*bcd)*受理状態'(0). '言語(*a*bcd)*'(状態集合_0,a,状態集合_1). '言語(*a*bcd)*'(状態集合_0,X,状態集合_5) :- \+(X = a). '言語(*a*bcd)*'(状態集合_1,b,状態集合_2). '言語(*a*bcd)*'(状態集合_1,X,状態集合_4) :- \+(X = b). '言語(*a*bcd)*'(状態集合_2,c,状態集合_3). '言語(*a*bcd)*'(状態集合_3,d,状態集合_0). '言語(*a*bcd)*'(状態集合_4,b,状態集合_2). '言語(*a*bcd)*'(状態集合_4,X,状態集合_4) :- \+(X = b). '言語(*a*bcd)*'(状態集合_5,a,状態集合_1). '言語(*a*bcd)*'(状態集合_5,X,状態集合_5) :- \+(X = a). 状態集合(状態集合_0,0). 状態集合(状態集合_1,1). 状態集合(状態集合_2,2). 状態集合(状態集合_3,3). 状態集合(状態集合_4,4). 状態集合(状態集合_5,5). % 以下のサイトは # # プログラム14.14: 言語(a*bcd)* を受理するNDFA # # # a \+(b) \+(b) # 状態集合_0 {0} --------------> 状態集合_1 {1} ---------> 状態集合_4 {4} --------- # | # ^ | | ^ | # | | | | | # | | b | b -------------- # d | | | # | | | # | v | # | # 状態集合_3 {3} <-------------- 状態集合_2 {2} <------------ # c # # 図14.5: 非決定性有限オートマトン # '言語(a*bcd)*を受理する非決定性有限オートマトン'(_入力記号ならび) :- '言語(a*bcd)*初期状態'(_状態), '言語(a*bcd)*を受理する非決定性有限オートマトン'(_状態,_入力記号ならび). '言語(a*bcd)*を受理する非決定性有限オートマトン'(_状態,[_記号|R_1]) :- '言語(a*bcd)*'(_状態集合,_記号,_状態集合_1), 状態集合(_状態集合,_状態), 状態集合(_状態集合_1,_状態_1), '言語(a*bcd)*を受理する非決定性有限オートマトン'(_状態_1,R_1),!. '言語(a*bcd)*を受理する非決定性有限オートマトン'(_状態,[]) :- '言語(a*bcd)*受理状態'(_状態). '言語(a*bcd)*初期状態'(0). '言語(a*bcd)*受理状態'(0). '言語(a*bcd)*'(状態集合_0,a,状態集合_1). '言語(a*bcd)*'(状態集合_1,b,状態集合_2). '言語(a*bcd)*'(状態集合_1,X,状態集合_4) :- \+(X = b). '言語(a*bcd)*'(状態集合_2,c,状態集合_3). '言語(a*bcd)*'(状態集合_3,d,状態集合_0). '言語(a*bcd)*'(状態集合_4,b,状態集合_2). '言語(a*bcd)*'(状態集合_4,X,状態集合_4) :- \+(X = b). 状態集合(状態集合_0,0). 状態集合(状態集合_1,1). 状態集合(状態集合_2,2). 状態集合(状態集合_3,3). 状態集合(状態集合_4,4). % 以下のサイトは # プログラム14.14: 言語(abcd)* を受理するNDFA # # a # --------------------------> # 状態集合_0 {0} 状態集合_1 {1} # # ^ | # | | # | | b # d | | # | | # | v # # 状態集合_3 {3} <-------------------- 状態集合_2 {2} # c # # 図14.5: 簡単なオートマトン # '言語(abcd)*を受理する非決定性有限オートマトン'(_入力記号ならび) :- '言語(abcd)*初期状態'(_状態), '言語(abcd)*を受理する非決定性有限オートマトン'(_状態,_入力記号ならび). '言語(abcd)*を受理する非決定性有限オートマトン'(_状態,[_記号|R]) :- '言語(abcd)*'(_状態集合,_記号,_状態集合_1), 状態集合(_状態集合,_状態), 状態集合(_状態集合_1,_状態_1), '言語(abcd)*を受理する非決定性有限オートマトン'(_状態_1,R). '言語(abcd)*を受理する非決定性有限オートマトン'(_状態,[]) :- '言語(abcd)*受理状態'(_状態). '言語(abcd)*初期状態'(0). '言語(abcd)*受理状態'(0). '言語(abcd)*'(状態集合_0,a,状態集合_1). '言語(abcd)*'(状態集合_1,b,状態集合_2). '言語(abcd)*'(状態集合_2,c,状態集合_3). '言語(abcd)*'(状態集合_3,d,状態集合_0). 状態集合(状態集合_0,0). 状態集合(状態集合_1,1). 状態集合(状態集合_2,2). 状態集合(状態集合_3,3). % 以下のサイトは # プログラム14.14: 言語(ab)* を受理するNDFA # # a # --------------------------> # 状態集合_0 {0} 状態集合_1 {1} # <-------------------------- # b # # 図14.5: 簡単なオートマトン # '言語(ab)*を受理する非決定性有限オートマトン'(_記号ならび) :- '言語(ab)*初期状態'(_状態), '言語(ab)*を受理する非決定性有限オートマトン'(_状態,_記号ならび). '言語(ab)*を受理する非決定性有限オートマトン'(_状態,[_記号|R]) :- '言語(ab)*'(_状態集合,_記号,_状態集合_1), 状態集合(_状態集合,_状態), 状態集合(_状態集合_1,_状態_1), '言語(ab)*を受理する非決定性有限オートマトン'(_状態_1,R). '言語(ab)*を受理する非決定性有限オートマトン'(_状態,[]) :- '言語(ab)*受理状態'(_状態). '言語(ab)*初期状態'(0). '言語(ab)*受理状態'(0). '言語(ab)*'(状態集合_0,a,状態集合_1). '言語(ab)*'(状態集合_1,b,状態集合_0). 状態集合(状態集合_0,0). 状態集合(状態集合_1,1). % 以下のサイトは % % a \+b % --------------------------> ---------------- % 状態_0 状態_1 | % <-------------------------- <--------------- % b % % 言語(a*b)*を受理する非決定性有限オートマトンの遷移 % '言語(a*b)*を受理する非決定性有限オートマトン'(_記号ならび) :- '言語(a*b)*初期状態'(_状態), '言語(a*b)*を受理する非決定性有限オートマトン'(_状態,_記号ならび). '言語(a*b)*を受理する非決定性有限オートマトン'(_状態,[_記号|R]) :- '言語(a*b)*'(_状態,_記号,_状態_1), '言語(a*b)*を受理する非決定性有限オートマトン'(_状態_1,R). '言語(a*b)*を受理する非決定性有限オートマトン'(_状態,[]) :- '言語(a*b)*終了状態'(_状態). '言語(a*b)*'(状態_0,a,状態_1). '言語(a*b)*'(状態_1,b,状態_0). '言語(a*b)*'(状態_1,C,状態_1) :- \+(C = b). '言語(a*b)*初期状態'(状態_0). '言語(a*b)*終了状態'(状態_0). % 以下のサイトは # # 有限アルファベット上の回文を受理する非決定性プッシュダウン・オートマトン # '有限アルファベット上の回文を受理する非決定性プッシュダウン・オートマトン'(_記号ならび) :- '有限アルファベット上の回文の初期状態'(_状態), '有限アルファベット上の回文を受理する非決定性プッシュダウン・オートマトン'(_状態,_記号ならび,[]). '有限アルファベット上の回文を受理する非決定性プッシュダウン・オートマトン'(_状態,[_記号|R],_記号ならび) :- '言語有限アルファベット上の回文'(_状態,_記号,_記号ならび,_状態_1,_記号ならび_1), '有限アルファベット上の回文を受理する非決定性プッシュダウン・オートマトン'(_状態_1,R,_記号ならび_1). '有限アルファベット上の回文を受理する非決定性プッシュダウン・オートマトン'(_状態,[],[]) :- '有限アルファベット上の回文の終了状態'(_状態). '有限アルファベット上の回文の初期状態'(q0). '有限アルファベット上の回文の終了状態'(q1). '言語有限アルファベット上の回文'(q0,X,S,q0,[X|S]). '言語有限アルファベット上の回文'(q0,X,S,q1,[X|S]). '言語有限アルファベット上の回文'(q0,X,S,q1,S). '言語有限アルファベット上の回文'(q1,X,[X|S],q1,S). % % 非決定性プッシュダウン・オートマトン(nodeterministic_pushdown_automaton)、 % 略してNPDAは、< Q,S,G,D,I,Z,F >なる7つの組みで表される。 % Q、S、I、Fは、さきほどのものと同じである。Gはスタックにプッシュダウンする % ことのできる記号のリストであり、Zはスタック上の開始記号である。 % Dは、内部状態ばかりでなく、スタックや現在の記号も考慮するよう変更されたdelta関数である。 % % 以下のサイトは # プログラム14.14: 言語(ab)* を受理するNDFA # # a # --------------------------> # 状態_0 状態_1 # <-------------------------- # b # # 図14.5: 簡単なオートマトン # '言語(ab)*を受理する非決定性有限オートマトン'(_記号ならび) :- '言語(ab)*初期状態'(_状態), '言語(ab)*を受理する非決定性有限オートマトン'(_状態,_記号ならび). '言語(ab)*を受理する非決定性有限オートマトン'(_状態,[_記号|R]) :- '言語(ab)*'(_状態,_記号,_状態_1), '言語(ab)*を受理する非決定性有限オートマトン'(_状態_1,R). '言語(ab)*を受理する非決定性有限オートマトン'(_状態,[]) :- '言語(ab)*終了状態'(_状態). '言語(ab)*初期状態'(状態_0). '言語(ab)*終了状態'(状態_0). '言語(ab)*'(状態_0,a,状態_1). '言語(ab)*'(状態_1,b,状態_0). % % 状態_0,状態_1 それぞれ状態集合のシンボルである。 % % 以下のサイトは # プログラム: 言語(a) を受理するNDFA # # a # ------------------------- # 状態_0 | # <------------------------ # # # 図 簡単なオートマトン # '次の文字列を非決定性有限オートマトンが言語(a)を受理するまで検索する'(_文字列,_前文字列,_受理された文字列,_後文字列) :- '文字列を、前・受理された・後文字ならび候補に分解する'(_文字列,_前文字ならび,_受理された文字ならび,_後文字ならび), '言語(a)を受理する非決定性有限オートマトン'(_受理された文字ならび), '各部文字ならびを文字列に変換する'(_前文字ならび,_受理された文字ならび,_後文字ならび,_前文字列,_受理された文字列,_後文字列). '文字列を、前・受理された・後文字ならび候補に分解する'(_文字列,_前文字ならび,_受理された文字ならび,_後文字ならび) :- atom_chars(_文字列,_文字ならび), append([_前文字ならび,_受理された文字ならび,_後文字ならび],_文字ならび), \+(_受理された文字ならび=[]). '各部文字ならびを文字列に変換する'(_前文字ならび,_受理された文字ならび,_後文字ならび,_前文字列,_受理された文字列,_後文字列) :- atom_chars(_前文字列,_前文字ならび), atom_chars(_受理された文字列,_受理された文字ならび), atom_chars(_後文字列,_後文字ならび). '言語(a)を受理する非決定性有限オートマトン'(_記号ならび) :- '言語(a)初期状態'(_状態), '言語(a)を受理する非決定性有限オートマトン'(_状態,_記号ならび). '言語(a)を受理する非決定性有限オートマトン'(_状態,[_記号|R]) :- '言語(a)'(_状態,_記号,_状態_1), '言語(a)を受理する非決定性有限オートマトン'(_状態_1,R). '言語(a)を受理する非決定性有限オートマトン'(_状態,[]) :- '言語(a)終了状態'(_状態). '言語(a)初期状態'(状態_0). '言語(a)終了状態'(状態_0). '言語(a)'(状態_0,a,状態_0).