(57)【要約】【課題】大きな記憶域を使用することなく、漸進的に決定性有限状態オートマトンの状態数を減少させることが可能な情報処理装置、方法及びプログラムを提供する。【解決手段】決定性有限オートマトンを構成する各状態を、出て行く遷移に付随する入力記号と終了性とが同じ状態毎に分類し、探索部が、各状態の遷移先状態の集合との積集合のサイズが１以下となるまで、この積集合に含まれる状態の遷移先状態の集合を新たな状態の集合とみなして前記積集合を算出し、前記探索部が辿った遷移方向とは逆向きに辿りながら互いに区別不可能な複数の状態を一の状態に併合する。【選択図】        図３
2010079723.tif 000002
【特許請求の範囲】
【請求項１】
決定性有限オートマトンを構成する各状態を、出て行く遷移に付随する入力記号と、終了状態か否かを表す終了性とが同じ状態毎に分類し、状態の集合を生成する状態分類部と、
前記状態の集合毎に、当該状態の集合に含まれる各状態から遷移する遷移先状態の集合との積集合を算出し、この積集合に含まれる要素の数が１以下となるまで、当該積集合に含まれる各状態の入力記号毎の遷移先状態の集合を新たな状態の集合とみなして、前記積集合の算出を繰り返し実行する探索部と、
前記積集合に含まれる要素数が１以下となった状態から、前記探索部が辿った遷移方向とは逆向きに辿りながら互いに区別不可能な複数の状態を一の状態に併合する状態併合部と、
を備えたことを特徴とする情報処理装置。
【請求項２】
前記状態併合部は、前記積集合の要素に含まれる状態のうち、入力記号に対する遷移先状態が同一となる状態又は遷移先状態が存在しない状態を、一の状態に併合することを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記探索部は、処理の対象とした前記状態の集合に含まれる各状態をスタックに記憶し、前記繰り返し処理時において得られる積集合の要素が前記スタックに存在するか否かで循環経路の判定を行い、
前記状態併合部は、前記探索部により循環経路と判定された状態から、前記探索部が辿った遷移方向と逆向きに辿りながら互いに区別不可能な複数の状態を一の状態に併合することを特徴とする請求項１又は請求項２に記載の情報処理装置。
【請求項４】
前記探索部は、前記循環経路上に存在する状態のうち、この循環経路の開始状態に当該開始状態以外の他の状態を前記スタックに関連付けて記憶し、
前記状態併合部は、前記開始状態に相当する状態を一の状態に併合するのに伴い、当該開始状態に関連付けて前記スタックに記憶された他の状態を一の状態に併合することを特徴とする請求項３に記載の情報処理装置。
【請求項５】
前記探索部は、決定性有限オートマトンを構成する各状態を、出て行く遷移に付随する入力記号と、終了状態か否かを表す終了性と、終了状態の種類とが同じ状態毎に分類することを特徴とする請求項１乃至請求項４の何れか１項に記載の情報処理装置。
【請求項６】
前記終了状態の種類は、終了状態に付与された重みであることを特徴とする請求項５に記載の情報処理装置。
【請求項７】
処理の中断を受け付ける受付手段と、
前記受付手段により処理の中断が受け付けられたタイミングにおける、前記状態分類部、前記探索部及び前記状態併合部での処理の実行箇所を判定し、中断可能な箇所と判定した場合のみ当該処理を中断する制御手段と、
を更に備えたことを特徴とする請求項１乃至請求項６の何れか１項に記載の情報処理装置。
【請求項８】
前記制御手段は、前記中断不可能な箇所と判定した場合、中断可能な箇所に到達まで処理を継続し、この中断可能な箇所に到達した時点で処理を中断することを特徴とする請求項７に記載の情報処理装置。
【請求項９】
状態分類部が、決定性有限オートマトンを構成する各状態を、出て行く遷移に付随する入力記号と、終了状態か否かを表す終了性とが同じ状態毎に分類し、状態の集合を生成する状態分類工程と、
探索部が、前記状態の集合毎に、当該状態の集合に含まれる各状態から遷移する遷移先状態の集合との積集合を算出し、積集合に含まれる要素の数が１以下となるまで、当該積集合に含まれる各状態の入力記号毎の遷移先状態の集合を新たな状態の集合とみなして、前記積集合の算出を繰り返し実行する探索工程と、
状態併合部が、前記積集合に含まれる要素数が１以下になった状態から、前記探索部が辿った遷移方向とは逆向きに辿りながら互いに区別不可能な複数の状態を一の状態に併合する状態併合工程と、
を含むことを特徴とする情報処理方法。
【請求項１０】
コンピュータに、
決定性有限オートマトンを構成する各状態を、出て行く遷移に付随する入力記号と、終了状態か否かを表す終了性とが同じ状態毎に分類し、状態の集合を生成する状態分類工程と、
前記状態の集合毎に、当該状態の集合に含まれる各状態から遷移する遷移先状態の集合との積集合を算出し、この積集合に含まれる要素の数が１以下となるまで、当該積集合に含まれる各状態の入力記号毎の遷移先状態の集合を新たな状態の集合とみなして、前記積集合の算出を繰り返し実行する探索工程と、
前記積集合に含まれる要素数が１以下となった状態から、前記探索工程で辿った遷移方向とは逆向きに辿りながら互いに区別不可能な複数の状態を一の状態に併合する状態併合工程と、
を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、決定性有限状態オートマトンの状態数削減に係る情報処理装置、情報処理方法及びプログラムに関する。
【背景技術】
【０００２】
有限個の状態と遷移と動作の組み合わせを表す有限状態オートマトン（Finite  State  Automaton：ＦＳＡ）は、有限オートマトン（Finite  Automaton）や有限状態機械（Finite  State  Machine：ＦＳＭ）と呼ばれ、さまざまな分野で利用されている。また、この有限状態オートマトンにおいて、入力記号が与えられたときに遷移先の状態が一意に決まるものを決定性有限状態オートマトン（Deterministic  Finite  state  Automaton：ＤＦＡ）と呼んでいる。なお、各状態からの出て行く遷移（outgoing  transition）が全ての入力記号に対して存在するＤＦＡだけでなく、入力記号の一部に対してのみ出て行く遷移が存在するものをもＤＦＡに含めることとする。
【０００３】
ＤＦＡを用いた例として、例えば音声認識の分野では、認識できる単語の音素列を記録した辞書をＤＦＡで表すことが行われている。この場合、ＤＦＡが表す状態数を小さくすることで、処理の効率化を図ることができる。また、他の適用例としては、テキスト検索が挙げられる。テキスト中から複数のキーワードを検索したいときに、複数のキーワードからＤＦＡを作成し、終了状態に到達したときに、複数のキーワードのうちの何れかが発見されたことを通知するような使い方ができる。このような処理をする場合でも、ＤＦＡの状態数を小さくすることで、処理の効率化を図ることができる。
【０００４】
また、上記ＤＦＡでは、あるＤＦＡが与えられたときに状態数が最小のものが存在することが知られており、この状態数が最小となるＤＦＡを求める方法が種々提案されている。この従来の方法として、HopcroftとUllmanの方法（例えば、非特許文献１参照）やAhoらの方法（例えば、非特許文献２参照）、Hopcroftの方法（例えば、非特許文献３参照）が知られている。
【０００５】
しかし、上記非特許文献１〜３の方法では状態数の最小化に係る処理を途中で中断すると途中結果を得ることができない。つまり、最小化処理に多くの時間を要するような、規模の大きいＤＦＡの状態数削減を漸進的に行えないという問題がある。そのため、従来、この問題を解決する方法としてWatsonらの方法が知られている（例えば、非特許文献４、５参照）。この方法を用いることで、状態数の削減に係る処理を中断したときに、その中断した時点でのＤＦＡを得ることができ、また、処理が完了すれば状態数が最小化されたＤＦＡを得ることができる。
【０００６】
Watsonらの方法が、処理を中断することが可能な理由は、二つの状態の区別可能性（distinguishability）を、全ての組み合わせについて一つ一つ漸進的に調べていく方法であるためである。例えば、ある状態ｐから終了状態へと導く入力記号列全体を言語Ｌ（ｐ）と定義すると、二つの状態ｐ、ｑが区別可能であるとは、Ｌ（ｐ）≠Ｌ（ｑ）であることをいう。同様に、区別不可能であるとは、Ｌ（ｐ）＝Ｌ（ｑ）であることをいう。二つの状態が区別不可能であることが分かれば、その時点で一方の状態を同様とみなし削除することができるため、処理を中断した場合でも、それまでの処理で区別不可能であると判断され、状態数を削減したＤＦＡを得ることができる。
【０００７】
【非特許文献１】オートマトン言語理論計算論Ｉ［第２版］、Ｊ．ホップクロフト、Ｒ．モトワニ、Ｊ．ウルマン共著、野崎昭弘、高橋正子、町田元、山崎秀記  共訳、サイエンス社、ＩＳＢＮ４−７８１９−１０２６−２、１７４-１８８頁
【非特許文献２】Alfred  V.  Aho,  Ravi  Sethi,  Jeffrey  D.  Ullman,  Compilers  Principles,  Techniques,  and  Tools,  1985，pp.142-143
【非特許文献３】J.  E.  Hopcroft,  An n  log  n  algorithm  for minimizing  the  states  in  a  finite  automaton,  Theory  of  Machines  and  Computations,  Academic  Press,  New  York,  1971,  pp.189-196
【非特許文献４】Bruce  W.  Watson,  An  incremental  DFA minimization  algorithm,  Workshop  on  Finite  State  Method  in  Natural  Language  Processing  (FSMNLP  '01),  2001
【非特許文献５】Bruce.  W.  Watson,  Jan.  Daciuk,  An  efficient  incremental  DFA  minimization  algorithm,  Natural  Language  Engineering,  9  (1),  2003,  pp.49-64
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら，非特許文献４に記載の方法では二つの状態の区別可能性を全ての組み合わせについて調べ、区別不可能な状態を１つにまとめていく処理を行うため、状態数が増えると処理量が急速に増大するという問題がある。また、非特許文献５に記載の方法では、処理時間を短くするため、区別可能であると判明した状態の２つ組を記憶する必要があり、状態数が多い場合には最大で状態数の２乗に比例する記憶域が必要となるため、大きな記憶域を要するという問題がある。
【０００９】
本発明は、上記に鑑みてなされたものであって、大きな記憶域を使用することなく、漸進的に決定性有限状態オートマトンの状態数を減少させることが可能な情報処理装置、方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上述した課題を解決し、目的を達成するために、本発明は、決定性有限オートマトンを構成する各状態を、出て行く遷移に付随する入力記号と、終了状態か否かを表す終了性とが同じ状態毎に分類し、状態の集合を生成する状態分類部と、前記状態の集合毎に、当該状態の集合に含まれる各状態から遷移する遷移先状態の集合との積集合を算出し、この積集合に含まれる要素の数が１以下となるまで、当該積集合に含まれる各状態の入力記号毎の遷移先状態の集合を新たな状態の集合とみなして、前記積集合の算出を繰り返し実行する探索部と、前記積集合に含まれる要素数が１以下となった状態から、前記探索部が辿った遷移方向とは逆向きに辿りながら互いに区別不可能な複数の状態を一の状態に併合する状態併合部と、を備える。
【発明の効果】
【００１１】
本発明によれば、決定性有限オートマトン（ＤＦＡ）を構成する状態のうち、区別不可能な状態を漸進的に一つの状態に併合することができるため、大きな記憶域を使用することなく、漸進的に決定性有限状態オートマトンの状態数を減少させることができる。
【発明を実施するための最良の形態】
【００１２】
以下、添付図面を参照して、本発明にかかる情報処理装置の実施形態を詳細に説明する。
【００１３】
まず、以下に説明する各実施形態で用いる記号、用語等について説明する。決定性有限状態オートマトン（以下、ＤＦＡと表記する）は５つ組（5-tuple）、ＤＦＡ＝（Ｑ,Σ,Ｅ,ｑ0,Ｆ）で表される。ここで、Ｑは状態の集合、Σは入力記号の集合、Ｅは遷移の集合、ｑ0は初期状態である。Ｆは終了状態の集合であり、Ｆ⊆Ｑを満たす。遷移ｅ∈Ｅに関してｐ（ｅ）は遷移元の状態（以下、遷移元状態という）を表し、n（ｅ）は遷移先の状態（以下、遷移先状態という）を表し、ｌａｂｅｌ（ｅ）はその遷移に割り当てられている入力記号を表す。
【００１４】
なお、遷移に割り当てられているものは全て入力記号であると見なすことで、入力記号とともに出力記号が付随している有限状態トランスデューサや、重みが付随している重み付き有限状態オートマトン等の有限状態オートマトンから派生したモデルを用いる場合においても、以下に説明する実施形態の手法を適用することができる。
【００１５】
プログラム等で集合を表現するときは、集合の要素を格納でき、集合内に重複した要素が発生しなければどのように表現してもよく、例えば、配列、リンクリスト、二分木、ハッシュテーブル等が挙げられる。空集合はφ又は｛｝で表す。集合Ｘのサイズは｜Ｘ｜と表す。例えば状態の集合Ｑに含まれる状態数は｜Ｑ｜で表される。
【００１６】
入力記号の集合Σのクリーネ閉包（Kleene  closure）をΣ*で表す。つまり、Σ*は集合Σに含まれる入力記号で構成される入力記号列全てと空入力記号列（空文字列，空列とも呼ばれる）とを含む集合ということである。
【００１７】
ある状態ｑに入力記号σ∈Σを入力したときの遷移先状態をδ（ｑ,σ）と表す。同様に、入力記号列ｗ∈Σ*を入力したときの遷移先の状態をδ（ｑ,ｗ）と表す。また、状態の集合に関しても同様の記法を用いる。状態の集合ｓに入力記号σ∈Σを入力したときの遷移先状態の集合をδ（ｓ,σ）と表す。さらに、入力記号列ｗ∈Σ*を入力したときの遷移先状態の集合をδ（ｓ,ｗ）と表す。
【００１８】
状態ｑ∈Ｑから出て行く遷移に割り当てられている入力記号の集合をΣqとする。同様に、状態の集合ｓから出て行く遷移に割り当てられている入力記号の集合をΣsとする。
【００１９】
後述する経路番号や状態ｘ等に値や集合等を関連付けるためのテーブルをＤとするとき、このテーブルＤに関連付けられた値や集合を得るときはＤ［ｘ］と記載する。例えばＤ［ｘ］←ｒは、テーブルＤ中のｘに値ｒを関連付ける処理を表している。また、Ｄ［ｘ］＝ｙであるとき、これに対応するテーブルＤの要素は（ｘ,ｙ）のように表すこととする。また、テーブルＤに含まれる全ての要素について処理する擬似コードを記載する場合には、ｆｏｒｅａｃｈ文を用いて、foreach（ｘ,ｙ）∈Ｄのように表す。
【００２０】
後述する各擬似コード内の変数については特に説明のない限り局所変数であるとする。つまり、その擬似コードの範囲内で処理されているときのみ有効な変数であるとする。なお、再帰呼び出しする場合は、個々の呼び出し毎に変数が作成され、異なる呼び出しの間で変数の内容が共有されることはない。一方、全ての擬似コードの間で共有される変数、つまりグローバルな変数については個々に説明する。なおＤＦＡを構成する状態の集合Ｑ、入力記号の集合Σ、遷移の集合Ｅ、初期状態ｑ0、終了状態の集合Ｆは、グローバル変数であるとする。
【００２１】
ある状態ｑに対して、δ（ｑ,ｗ）＝ｑが成り立つようなｗ∈Σ*＼{ε}が存在する場合、状態ｑは循環経路上にあるという。また、このようなｗによって通過することになる経路のことを循環経路と呼ぶ。なお、ｗ∈Σ*＼{ε}は、空入力記号列εを含まない入力記号列全てから構成される集合を意味する。
【００２２】
ｗiをｗの先頭からｉ番目までの記号で構成される記号列とする。例えば、ｗ＝ａｂｃならｗ1＝ａ，ｗ2＝ａｂ，ｗ3＝ａｂｃとなる。状態ｑ∈Ｑから入力記号列ｗ∈Σ*＼{ε}の入力によって通過する経路上にある状態をＱwとすると、Ｑw＝｛ｑ,δ（ｑ,ｗ1）,δ（ｑ,ｗ2）,・・・,δ（ｑ,ｗ）｝のように定義できる。状態δ（ｑ,ｗ）から入力記号σ∈Σによって遷移した先の状態δ（ｑ,ｗσ）がＱwに含まれるとき、状態δ（ｑ,ｗσ）を循環経路の開始状態と呼ぶ。ｑをどの状態とするかで循環経路の開始状態は変化する。例えば、後述する図３では、ステップＮ１０３で選ばれる集合ｇに含まれる状態が、ここでのｑに対応する。
【００２３】
ある状態ｐから終了状態へと導く入力記号列全体の言語をＬ（ｑ）＝｛ｗ∈Σ*｜δ（ｑ,ｗ）∈Ｆ｝と定義するとき、２つの状態ｐ、ｑが区別可能であるとは、Ｌ（ｐ）≠Ｌ（ｑ）であることをいう。同様に、区別不可能であるとはＬ（ｐ）＝Ｌ（ｑ）であることをいう。３個以上の状態数の場合に拡張すると、状態の集合ｓに含まれる状態が互いに区別不可能であるとは、全ての入力記号列ｗ∈Σ*に対してδ（ｓ,ｗ）⊆Ｆ又はδ（ｓ,ｗ）⊆Ｑ＼Ｆが成り立つことをいう。また、循環経路を考慮する場合、他の状態が区別不可能であれば区別不可能になる状態も考えられる。このような状態を区別不可能候補と呼ぶこととする。
【００２４】
依存関係とは、区別不可能候補である状態を依存元状態とし、依存元状態が区別不可能な状態となるか否かを判断するための状態を依存先状態とするとき、依存元状態と依存先状態との関係を表す情報である。具体的には、循環経路の開始状態である状態のうちの何れかが依存先状態となる。
【００２５】
状態の集合をｓとするとき、ｓに含まれる状態が互いに区別可能であるとは、全てのｐ∈ｓ,ｑ∈ｓ,ｐ≠ｑに対して、ｐとｑとが区別可能であることをいう。同様にｓに含まれる状態が互いに区別不可能であるとは、ｐとｑとが区別不可能であることをいう。
【００２６】
状態の終了性（finality）とは、状態ｑ∈Ｑが終了状態の集合Ｆに含まれているか否かを表している。ｑ∈Ｆであれば状態の終了性は真であり、¬（ｑ∈Ｆ）であれば状態の終了性は偽である。終了性と出て行く遷移の入力記号の集合が同じ状態を分類したもの、言い換えると、それらが同じ状態を夫々集合とし、その集合を要素とする集合をＧとする。したがって、集合Ｇは状態の集合の集合となる。集合ηも状態の集合を要素とする集合とし、集合ηを要素とする集合を集合Ｈとする。
【００２７】
また、後述する実施形態では、循環経路の判定のためにスタック（スタックＳ）を利用するが、スタックの実装方法は特に問わないものとする。例えば、配列やリンクリストで構成することとしてもよい。ただし、スタックに記録している要素の内容と、そのスタック内での格納位置を調べることが可能であるものとする。
【００２８】
［第１の実施形態］
図１は、第１の実施形態に係る情報処理装置のハードウェア構成の一例を示したブロック図である。同図に示したように、情報処理装置１００は、ＣＰＵ（Central  Processing  Unit）１、操作部２、表示部３、ＲＯＭ（Read  Only  Memory）４、ＲＡＭ（Random  Access  Memory）５、記憶部６等を備え、各部はバス７により接続されている。
【００２９】
ＣＰＵ１は、ＲＡＭ５の所定領域を作業領域として、ＲＯＭ４又は記憶部６に予め記憶された各種制御プログラムとの協働により各種処理を実行し、情報処理装置を構成する各部の動作を統括的に制御する。また、ＣＰＵ１は、ＲＯＭ４又は記憶部６に予め記憶された所定のプログラムとの協働により、後述する各機能部の機能を実現させる。
【００３０】
操作部２は、マウスやキーボード等の入力デバイスであって、ユーザから操作入力された情報を指示信号として受け付け、その指示信号をＣＰＵ１に出力する。
【００３１】
表示部３は、ＬＣＤ（Liquid  Crystal  Display）等の表示装置により構成され、ＣＰＵ１からの表示信号に基づいて、各種情報を表示する。
【００３２】
ＲＯＭ４は、情報処理装置の制御にかかるプログラムや各種設定情報等を書き換え不可能に記憶する。ＲＡＭ５は、ＳＤＲＡＭ等の揮発性の記憶媒体であって、ＣＰＵ１の作業エリアとして機能し、具体的には、後述する状態数削減処理時において生成される各種変数やパラメータの値等を一時記憶するバッファの役割を果たす。
【００３３】
記憶部６は、磁気的又は光学的に記録可能な記憶媒体を有し、情報処理装置の制御にかかるプログラムや各種設定情報等を書き換え可能に記憶する。また、記憶部６は後述する状態数削減処理を実行する各機能部を実現するためのプログラムや、状態数削減処理の対象となるＤＦＡ等、各種の情報を予め記憶する。
【００３４】
図２は、図１に示した情報処理装置の機能的構成を示したブロック図である。同図に示したように、情報処理装置は、ＣＰＵ１とＲＯＭ４又は記憶部６に予め記憶された所定のプログラムとの協働により実現される機能部として、状態数削減処理部１０を備えている。
【００３５】
状態数削減処理部１０は、状態分類部１１と、探索部１２とを有し、これら機能部との協働により後述する状態数削減処理を実行し、処理対象となるＤＦＡを構成する状態数を漸進的に削減する。
【００３６】
状態分類部１１は、処理の対象となるＤＦＡに含まれる各状態を、その状態の終了性（finality）と、出て行く遷移（outgoing  transition）に付随する入力記号の種別とが同じ状態毎に分類する。ここで、各分類は状態の集合として表すことができる。また、分類全体は分類から構成されるので、分類の集合、つまり、状態の集合を要素とする集合で表すことができる。そこで、以下では、状態分類部１１が分類した状態の集合をｇと表記し、このｇを要素とする分類全体の集合をＧと表記する。なお、状態分類部１１は、分類に含まれる状態数が１の場合には、その分類を集合Ｇに含めないものとする。即ち、全てのｇ∈Ｇに対して、｜ｇ｜＞１であるものとする。
【００３７】
また、状態分類部１１は、集合Ｇが空集合φであるか否かを判定し、空集合φと判定した場合、処理対象のＤＦＡを構成する状態の数が最小と判断する。一方、集合Ｇが空集合φでないと判定した場合、集合Ｇの要素となる集合ｇの一つを選択し、探索部１２に引き渡す。なお、要素の選択順序は特に問わず、例えばｇのサイズが小さいものから選んでもよいし、大きいものから選んでもよい。
【００３８】
探索部１２は、図２に示したように、状態併合部１２１と、遷移先集合生成部１２２と、区別不可能集合生成部１２３と、区別不可能候補集合生成部１２４とを有している。探索部１２は、これら各機能部との協働により、集合ｇに含まれる状態のうち、区別不可能な状態同士を一つの状態に併合し、この併合した集合ｇを集合Ｇから除去する。なお、探索部１２の動作の詳細については後述する。
【００３９】
以下、本実施形態の状態数削減処理部１０により実行される状態数削減処理について説明する。図３は、状態数削減処理の概要を示したフローチャートである。なお、図中ステップＮ１１０で示す各ステップ（ステップＮ１１１〜Ｎ１１９）が、探索部１２により実行される処理内容を表している。
【００４０】
まず、状態分類部１１は、処理対象となったＤＦＡについて、当該ＤＦＡを構成する各状態を、その状態の終了性と、出て行く遷移に付随する入力記号の種別とについて分類する（ステップＮ１０１）。
【００４１】
次いで、状態分類部１１は、ステップＮ１０１で分類した集合ｇを要素とする集合Ｇが、空集合φか否かを判定する（ステップＮ１０２）。ここで、集合Ｇが空集合φでないと判定した場合（ステップＮ１０２；Ｎｏ）、状態分類部１１は集合Ｇに含まれる集合ｇを一つ選択し、探索部１２に処理を渡す（ステップＮ１０３）。
【００４２】
探索部１２では、ステップＮ１０３で選択された集合ｇに含まれる各状態について、出て行く遷移に付随する入力記号の集合Σgを生成する（ステップＮ１１１）。
【００４３】
続いて、探索部１２は、ステップＮ１１２〜Ｎ１１５のループ処理（ループ１）を実行する。まず、ステップＮ１１２では、集合Σgに含まれる各入力記号について、ステップＮ１１３、Ｎ１１４の処理が完了したか否かを判定する。次いで、探索部１２は、集合Σgから一の入力記号を選択すると、この入力記号により遷移する集合ｇに含まれる状態の遷移先状態の集合ｇnを導出する（ステップＮ１１３）。
【００４４】
そして、探索部１２は、集合ｇnと集合Ｇの各要素ｇ′（ｇ′∈Ｇ）との積集合（ｇn∩ｇ′）を求め、このサイズが２以上である場合のみ（｜ｇn∩ｇ′｜＞１）、この積集合を集合ｇと見なして、ステップＮ１１１〜Ｎ１１９までの処理を再帰的に行う（ステップＮ１１４）。
【００４５】
ステップＮ１１２〜Ｎ１１５のループ処理が完了すると、再帰処理によって遷移先状態のうち互いに区別可能な状態は一つにまとめられている。探索部１２は、これを前提として集合ｇに含まれる各状態のうちで、互いに区別不可能な状態の集合を夫々一つの状態に併合する（ステップＮ１１６）。なお、ステップＮ１１４の再帰処理中に生成された後述する依存関係の情報があり、さらに併合すべき状態があれば、それらについても一の状態に併合する。
【００４６】
続いて、探索部１２は、集合ｇが循環経路にあるか否かを判定し、循環経路にある場合には、この集合ｇの依存先となる状態集合についての情報を記録する（ステップＮ１１７）。なお、集合ｇが循環経路にあると判定した場合であっても、現時点では区別不可能と決められないものに関しては、その集合ｇを依存元とし、この循環経路の開始状態を依存先とした依存関係の情報を記録する。この場合、依存先の状態集合が区別不可能であると判定したときに、一つの状態に併合する。ここで、循環経路の開始状態とは、前記定義により、その循環経路上の状態のうち最初に処理する状態を意味する。
【００４７】
また、探索部１２は、集合ｇに含まれている状態が何れも循環経路上になければ、この集合ｇに一致する集合Ｇの要素を集合Ｇから除去する（ステップＮ１１８）。さらに、探索部１２は、区別不可能と判定し、一つの状態に併合する過程で削除した状態を集合Ｇから除去し（ステップＮ１１９）、ステップＮ１０２の処理に再び戻る。
【００４８】
ステップＮ１０２において、集合Ｇが空集合であると判定した場合（ステップＮ１０２；Ｙｅｓ）、状態分類部１１は処理対象のＤＦＡの状態数が最小化されていると判断し、本処理を終了する。
【００４９】
ステップＮ１１０が実行される度に、区別不可能な状態がまとめられることで状態が削減される。そのため、本処理が完了する前に処理が中断されても、この途中の時点でのＤＦＡを得ることができる。なお、上記処理では再帰的な処理が発生するが、局所変数、つまりステップＮ１１０の処理が呼び出される度に、この処理により生成される変数をスタックに記録する一般的な方法により、繰り返し処理へと変換できることは言うまでもない。
【００５０】
以下、上述した状態数削減処理を実現する具体的な手法の一例について説明する。図４は、上述した状態数削減処理のメインプログラムとなる“ｓｉｍｉｎ”の擬似コードの一例を示した図である。なお、括弧内の“Ａ”は、引数となる処理対象のＤＦＡを意味している。
【００５１】
まず、状態数削減処理部１０は、状態と経路番号との２つ組の集合を記憶しておくためのスタックＳを空にするとともに、状態の依存関係を記憶しておくためのテーブルＤを空集合にする（ステップＮ２０１）。なお、スタックＳとテーブルＤはグローバル変数とする。つまり、後述する各擬似コードから、同じスタックＳと、テーブルＤとが参照できるものとする。
【００５２】
次いで、状態数削減処理部１０は、状態分類部１１を用いて、終了性と出て行く遷移の入力記号とで、処理対象のＤＦＡを構成する各状態を分類し、その結果を集合Ｇに代入する（ステップＮ２０２）。具体的には、ある状態から出て行く全ての遷移に付随する入力記号から構成される集合と、その状態の終了性とが同じ条件のものを一つの集合ｇに集約し、それらの集合をＧとする。遷移や終了性のパターンが複数あると、この集合ｇが複数個生成されるが、要素が１つの集合ｇはＧに含めない。形式的に表すと、∀ｇ∈Ｇ,｜ｇ｜＞１である。これらの処理を行うのが、ステップＮ２０２に記述したサブプログラム“ｃｒｅａｔｅ＿ｃｌａｓｓ”である。なお、“ｃｒｅａｔｅ＿ｃｌａｓｓ”については後述する。
【００５３】
ステップＮ２０２で得られる集合Ｇの内容は、全てのｇ∈Ｇに関して任意の状態ｑ1,ｑ2∈ｇを考えたとき、｛ｌａｂｅｌ（ｅ）｜ｅ∈Ｅ, ｐ（ｅ）＝ｑ1｝=｛ｌａｂｅｌ（ｅ）｜ｅ∈Ｅ,ｐ（ｅ）＝ｑ2｝、且つ、ｑ1,ｑ2∈Ｆ∨¬（ｑ1,ｑ2∈Ｆ）を満たすものとなっている。このステップＮ２０２が、図３に示したステップＮ１０１の処理に対応している。
【００５４】
以下、図５を参照して、ステップＮ２０２のサブプログラム“ｃｒｅａｔｅ＿ｃｌａｓｓ”について説明する。ここで、図５は“ｃｒｅａｔｅ＿ｃｌａｓｓ”の擬似コードの一例を示した図である。
【００５５】
まず、状態分類部１１は、状態の集合ｇを要素とする集合Ｇを空集合φで初期化するとともに、状態の終了性と集合Σｑとの２つ組に状態の集合ｇを関連付けて記憶するためのテーブルＣを空集合φで初期化する（ステップＮ２１１）。
【００５６】
続いて、状態分類部１１は、ステップＮ２１２のｆｏｒｅａｃｈ文に従い、処理対象のＤＦＡを構成する状態の集合Ｑに含まれる各状態ｑについて、ステップＮ２１３、Ｎ２１４の処理を実行する。ステップＮ２１３において、状態分類部１１は、状態ｑから出て行く遷移の入力記号の集合を生成し集合Σqに代入する。また、ステップＮ２１４において、状態分類部１１は、状態ｑの終了性と集合Σｑとの２つ組をテーブルＣに登録し、この２つ組みの条件に関連付けた集合ｇに当該条件に該当する状態ｑを追加する。なお、ステップＮ２１４の“ｑ∈Ｆ”は、状態ｑが終了状態であれば真となり，そうでなければ偽となる演算を意味している。
【００５７】
続く、ステップＮ２１５は、状態分類部１１がテーブルＣに登録した各要素に対して、ステップＮ２１６、Ｎ２１７の処理を実行することを表している。ここで、状態分類部１１は、状態の終了性と集合Σｑとの２つ組に関連付けられている状態の集合ｇのみをステップＮ２１６、Ｎ２１７で使用する。ステップＮ２１６において、状態分類部１１は、集合ｇのサイズが２以上（｜ｇ｜＞１）であるか否かを判定し、２以上であればステップＮ２１７で集合Ｇに集合ｇを追加する。
【００５８】
なお、ステップＮ２１６において、集合ｇのサイズが１以下（｜ｇ｜≦１）と判定した場合、テーブルＣに登録されている次の要素についてステップＮ２１５を実行する。また、全ての要素についてステップＮ２１６、Ｎ２１７の処理が完了した場合には、ステップＮ２１８の処理に移行する。
【００５９】
次いで、状態分類部１１は、上述した処理で得られた集合Ｇを、“ｃｒｅａｔｅ＿ｃｌａｓｓ”の処理結果としてメインプログラム“ｓｉｍｉｎ”に返し（ステップＮ２１８）、“ｃｒｅａｔｅ＿ｃｌａｓｓ”の処理を終了する。
【００６０】
図４に戻り、状態数削減処理部１０は、集合Ｇが空集合φになるまでステップＮ２０４、Ｎ２０５の処理を繰り返し実行する（ステップＮ２０３）。このステップＮ２０３が、図３に示したステップＮ１０２の処理に対応する。ステップＮ２０４において、状態数削減処理部１０は、集合Ｇから任意の要素（集合ｇ）を一つ選択する。なお、要素の選択順序は特に問わず、例えばｇのサイズが小さいものから選んでもよいし、大きいものから選んでもよい。
【００６１】
続くステップＮ２０５において、状態数削減処理部１０は、探索部１２を用いることで、集合ｇに含まれる状態と、これら各状態からの遷移先状態とのうち、区別不可能な状態を一つの状態に併合する。上記したステップＮ２０４、Ｎ２０５の処理が、それぞれ図３に示したステップＮ１０３、Ｎ１１０の処理に対応している。
【００６２】
また、サブプログラム“ｓｅａｒｃｈ＿ｅｑｕｉｖ”の引数の生成に係るサブプログラム“ａｄｄ＿ｐａｔｈ＿ｉｎｄｅｘ”では、集合ｇの要素に１から順に番号を付与した集合を生成する処理が行われる。この番号を経路番号（path  index）と呼ぶこととし、経路番号が割り振られた状態の集合をγで表す。ここで、集合γの要素は（状態，経路番号）で構成される２つ組であるとする。集合ｇに含まれる状態の夫々に固有の番号を関連付けられればよいので、実際のプログラムとして実装する場合には、集合ｇに含まれる状態を要素とする配列やリンクリストなどを用いることとしてもよい。なお、ステップＮ２０５の処理を行うサブプログラム“ｓｅａｒｃｈ＿ｅｑｕｉｖ”については後述する。
【００６３】
ステップＮ２０４、Ｎ２０５を実行する度に状態を併合する処理が完結するため、集合Ｇが空集合φになる前に処理を中断しても、その中断した時点でのＤＦＡが得られる。また、後述するサブプログラム“ｓｅａｒｃｈ＿ｅｑｕｉｖ”やそこから呼び出されるサブプログラムは、一部を除き、処理の途中で中断することも可能である。これらの点において漸進的な処理になっていることが分かる。なお、中断するとその時点でのＤＦＡを得ることができない箇所については後述する。
【００６４】
以下、図６−１及び図６−２を参照して、ステップＮ２０５のサブプログラム“ｓｅａｒｃｈ＿ｅｑｕｉｖ”について説明する。ここで、図６−１及び図６−２は“ｓｅａｒｃｈ＿ｅｑｕｉｖ”の擬似コードの一例を示した図である。なお、“ｓｅａｒｃｈ＿ｅｑｕｉｖ”は、図３に示したステップＮ１１０（ステップＮ１１１〜Ｎ１１９）の処理に対応する。
【００６５】
まず、探索部１２は、引数として渡された集合γの各要素から経路番号を取り除いた状態の集合を集合ｇに代入する（ステップＮ２２１）。なお、配列やリンクリストのような各要素に順序がある記憶方法で集合γが構成されており、さらに順序を無視して集合演算を行えるように構成されている場合には、ステップＮ２２１のような経路番号を取り除く処理は必要なく、そのまま集合ｇとして使用してもよい。
【００６６】
次いで、探索部１２は、集合ｇに含まれる各状態から出て行く遷移に付随する入力記号の集合を作成し、それをΣgとする（ステップＮ２２２）。なお、集合ｇに含まれている状態に関しては全て同じ集合Σgとなるので、ステップＮ２２２のように集合ｇに含まれる状態全てについて出て行く遷移の入力記号を調べなくてもよく、集合ｇに含まれる状態のうち一つのみについて取り扱えば十分である。このステップＮ２２２の処理が、図３に示したステップＮ１１１の処理に対応する。
【００６７】
続いて、探索部１２は、後の処理で使用する集合Ψscを空集合φとした後（ステップＮ２２３）、集合Σgが空集合φであるか否かを判定する（ステップＮ２２４）。ここで、集合Σgが空集合φであれば、ステップＮ２２５の処理を実行する。集合Σgが空集合φということは遷移先が存在していないということであるため、集合ｇに含まれる状態は互いに区別不可能である。つまり一つの状態に併合することができるので、探索部１２は、状態併合部１２１を用いてサブプログラム“ｍｅｒｇｅ＿ｓｔａｔｅｓ”を実行することで、集合ｇに含まれる状態を一つの状態に併合する（ステップＮ２２５）。また、遷移先がある場合には｜Σg｜＞０となるので、探索部１２は、ステップＮ２２６に移行し、ステップＮ２２７からステップＮ２６７までの処理を行うこととなる。なお、サブプログラム“ｍｅｒｇｅ＿ｓｔａｔｅｓ”については後述する。
【００６８】
ステップＮ２２７において、探索部１２は、集合Ｈを空集合φにするとともに、集合Ｙscを空集合φとする（ステップＮ２２７）。続いて、探索部１２は、現在の集合γの値をスタックＳに格納する（ステップＮ２２８）。そして、探索部１２は、ステップＮ２２９のｆｏｒｅａｃｈ文に従い、集合Σgの要素σ毎にステップＮ２３０〜Ｎ２５４までの処理を行う。なお、ステップＮ２２９〜Ｎ２５４までの処理が、図３に示したステップＮ１１２〜Ｎ１１５の処理に対応している。
【００６９】
ステップＮ２３０において、探索部１２は、このループ内で使用する集合Ψsc，集合Ψnsc，集合ηを空集合φとする（ステップＮ２３０）。次いで、探索部１２は、遷移先集合生成部１２２を用いてサブプログラム“ｎｅｘｔ＿ｇａｍｍａ”を実行することで、集合γに含まれる各状態からの入力記号σによる遷移先状態の集合を経路番号とともに集合γnに記録する（ステップＮ２３１）。なお、サブプログラム“ｎｅｘｔ＿ｇａｍｍａ”については後述する。
【００７０】
｜γ｜＝｜γn｜の場合には経路番号は遷移元に対応する番号でなければならない。一方、状態が同じで経路番号が異なる２つ組が存在する場合には、｜γ｜＞｜γn｜となるので、集合γnに含まれる経路番号が互いに異なっていればどのような経路番号を割り当ててもよい。例えば、状態が同じで経路番号だけが異なる２つ組に関して、その中で最も小さい経路番号を割り当てるようにしてもよい。
【００７１】
｜γ｜＞｜γn｜の場合に、経路番号を割り当て直してもよい理由は次の通りである。循環経路を発見するために経路番号を用いている。循環経路と判定されるにはスタックＳに集合γnが存在する必要がある。もし｜γ｜＞｜γn｜であるなら、全てのγs∈Ｓに対して、｜γs｜＞｜γn｜が成立する。これは、｜γ｜＞｜γn｜のとき集合γnがスタックＳに存在しないことを意味する。したがって、集合γnの経路番号は集合γの経路番号とは無関係に定めることができる。
【００７２】
探索部１２は、スタックＳに集合γnが記憶されているか否かを判定し(ステップＮ２３２)、スタックＳに集合γnが記憶されていない場合、ステップＮ２３３〜Ｎ２４８までの処理を実行する。
【００７３】
スタックＳに集合γnが記憶されていない場合、探索部１２は、ステップＮ２３３のｆｏｒｅａｃｈ文に従い、集合Ｇに含まれる状態の集合ｇ′の全てについて、ステップＮ２３４〜Ｎ２３７までの処理を行う。ステップＮ２３４では、集合γnの要素のうち、集合ｇ′に含まれる状態のみを選択し、集合γniに代入する（ステップＮ２３４）。言い換えると、集合γnに含まれる２つ組（状態，経路番号）に記録されている状態から構成される状態の集合と、集合ｇ′との積集合を、経路番号を維持したまま求め、それを集合γniとするということである。なお、本擬似コードでは経路番号を常に維持するようにしているが、｜γ｜＞｜γni｜の場合は経路番号を維持する必要はないため、この場合には新たに経路番号を振りなおしてもよい。
【００７４】
集合γや集合γn,集合γniを先頭のインデックスが固定の配列とし、配列のインデックスを経路番号に、その要素を状態とすることで、記憶域を無駄に使用せずに集合γなどを表現することができる。要素数が減れば経路番号は振りなおせるので、常に集合γや集合γn，集合γniのサイズ分だけ配列のサイズを用意すればよい。
【００７５】
ところで、本擬似コードでは、ステップＮ２３３において集合Ｇに含まれる全ての要素についてステップＮ２３４の処理を行うこととしたが、多くの場合集合ｇ′に関して集合γnとの積集合の演算を行うとγni＝φとなることから、次に述べるように、一部の要素についてのみステップＮ２３４の処理を行うこととし、さらに効率よく動作させるようにしてもよい。その動作とは、サブプログラム“ｃｒｅａｔｅ＿ｃｌａｓｓ”で集合Ｇを求める際に、各状態が集合Ｇのどの要素に含まれているのかを対応付けるテーブルを生成しておくというものである。これにより、集合Ｇの要素のうち、集合γnに含まれる状態を含む集合Ｇの要素についてのみステップＮ２３３〜Ｎ２３７を処理することが効率よくできるようになり、その結果、集合γniのサイズは１以上のものしか生成されないようになる。
【００７６】
続くステップＮ２３５において、探索部１２は、集合γniのサイズが１より大きいか否かを判定し、集合γniのサイズが１より小さい場合には、ステップＮ２３３に再び戻る。また、ステップＮ２３５において、集合γniのサイズが１より大きい場合には、続くステップＮ２３６にて“ｓｅａｒｃｈ＿ｅｑｕｉｖ”を再帰的に呼び出す。この結果、集合Ｇが更新される。なお、集合ＧはステップＮ２３３の判定処理で使用しているが、その時点までに処理した要素について再度処理しなおす必要はない。また、集合Ψnsctには、集合γniに含まれる状態に後述する区別不可能候補が存在したときに、その依存関係が記録される。探索部１２は、集合Ψnsctの要素を集合Ψnscに追加する（ステップＮ２３７）。
【００７７】
続いて、探索部１２は、入力記号σを伴う集合ｇの遷移先となる状態の集合ｇnを取得する（ステップＮ２３８）。この理由は、サブプログラム“ｓｅａｒｃｈ＿ｅｑｕｉｖ”の再帰呼び出しによって、処理対象のＤＦＡの状態数｜Ｑ｜が減少しているかもしれないためである。ただし、｜γn｜より｜ｇn｜が大きくなることはない。
【００７８】
また、探索部１２は、ステップＮ２３９のｆｏｒｅａｃｈ文に従い、遷移先が同じ状態を一つの状態に併合するため、集合ｇnに含まれる状態全てについて、ステップＮ２４０〜Ｎ２４３までの処理を実行する。
【００７９】
ステップＮ２４０において、探索部１２は、集合ｇに含まれる状態のうち、入力記号σによる遷移先が同じ状態の集合を集合ｇsに代入する。なお、ステップＮ２３６の再帰呼び出しで集合ｇに含まれている状態がなくなっている可能性があるが、そのような状態はｐ（ｅ）に現われることはないので問題はない。
【００８０】
次いで、探索部１２は、集合ｇsのサイズが１よりも大きいか否かを判定し（ステップＮ２４１）、１以下の場合にはステップＮ２４４の処理に移行する。また、ステップＮ２４１において、集合ｇsのサイズが１よりも大きいと判定した場合、探索部１２は集合ｇsに含まれる状態は入力記号σによって同じ状態へと遷移するということになるため、集合ｇsに含まれる状態は入力記号σに関しては区別不可能である。したがって、探索部１２は、入力記号毎の区別不可能な状態の集合を記憶するための集合ηに集合ｇsを要素として追加する（ステップＮ２４２）。
【００８１】
さらに、探索部１２は、集合ｇsを区別不可能候補としても記録しておくため、依存先状態を自分自身とした２つ組（ｑ,ｑ）の集合と、この集合を記録したスタックＳでの格納位置、つまりスタックＳのサイズ｜Ｓ｜とを集合Ψscに追加する（ステップＮ２４３）。なお、スタックＳの格納位置を表すインデックスは１から始まるものとする。
【００８２】
また、探索部１２は、ステップＮ２４４のｆｏｒｅａｃｈ文に従い、集合Ψnscの各要素に関して、ステップＮ２４５〜Ｎ２４８の処理を実行する。このとき、集合ｇの遷移先状態が区別不可能候補である場合、依存関係の情報が集合ψnscに記録されているので、探索部１２は、その依存先の状態を現在処理中の集合ｇに含まれる状態の依存先とし、集合ｇに含まれる区別不可能候補である状態の依存関係を集合ψscに代入する（ステップＮ２４５）。
【００８３】
続いて、探索部１２は、依存先が格納されたスタックＳの格納位置ｘlevelが、現在参照中のスタックＳの｜Ｓ｜と等しいか否かを判定する（ステップＮ２４６）。ここで、一致しない場合には、ステップＮ２４８の処理に直ちに移行する。なお、ｘlevelはψscの依存先状態のスタックＳ上での格納位置を表す。
【００８４】
一方、ステップＮ２４６において一致したと判定した場合、探索部１２は、集合ψscに含まれる２つ組（依存元状態，依存先状態）の依存元状態から入力記号σによる遷移を含む循環経路が入力記号σに関しては区別不可能であることが分かるので、集合ψscに含まれる依存元状態を集合ηに追加する（ステップＮ２４７）。なお、ｘlevel＞｜Ｓ｜のケースは発生しない。
【００８５】
続くステップＮ２４８では、探索部１２が、集合ψscとその依存先状態が格納されたスタックＳの格納位置ｘlevelとの２つ組を、区別不可能候補として集合Ψscに追加する（ステップＮ２４８）。
【００８６】
ステップＮ２４９〜Ｎ２５３は、ステップＮ２３２の判定時において、スタックＳに集合γnが記憶されている場合、つまり循環経路が発見された場合に実行される処理である。ステップＮ２５０において、探索部１２は、依存関係を表す２つ組（依存元状態，依存先状態）の集合ψscを生成する。ここで、依存元状態とは、集合ｇに含まれる状態を意味し、依存先状態とは、依存元状態から入力記号σによって到達できる状態を意味する。
【００８７】
続くステップＮ２５１では、探索部１２が、集合ψscとその依存先状態の集合が記録されているスタックＳでの格納位置ｌｅｖｅｌ（Ｓ,γn）との２つ組を集合Ψscに追加する。続いて、探索部１２は、γ＝γnか否か、即ち、自己遷移か否かを判定する（ステップＮ２５２）。ここで、自己遷移と判定した場合には、集合ｇに含まれる状態は区別不可能であるので、集合ηに集合ｇを追加する（ステップＮ２５３）。なお、ステップＮ２３２での条件の評価と同時に、位置ｌｅｖｅｌ（Ｓ,γn）を取得しておいてもよい。
【００８８】
前述したように、スタックＳのインデックスは１から始まるものとしているので、集合γnがスタックＳの一番底に格納されている場合、ｌｅｖｅｌ（Ｓ,γn）＝１となる。以上の処理により、集合ｇに含まれる状態のうち、どの状態が互いに区別不可能な状態なのか、どの状態が区別不可能候補なのかが入力記号σに関して判明するので、ステップＮ２５４ではステップＮ２３０〜Ｎ２５３で得られた集合Ψscと集合ηとを夫々集合Ｙscと集合Ｈに追加する。
【００８９】
続くステップＮ２５５とＮ２５６とが、図３に示したステップＮ１１６に対応する。集合Σgに含まれる入力記号全てについて処理が終わるとステップＮ２５５以降の処理が行われる。ステップＮ２５５以降の処理では、ステップＮ２５４までに各入力記号について求めた集合ηを使って、集合ｇに含まれる状態の区別不可能性を判定し、互いに区別不可能な状態を一つの状態に併合する。さらにステップＮ２５４までに各入力記号について求めた集合Ψscを使って、集合ｇの状態のうち区別不可能候補となる状態を特定する。
【００９０】
ステップＮ２５５では、探索部１２が、互いに区別不可能な状態の集合を要素にもつ集合を取得する。ここで集合ηは、集合Ｈに含まれる要素のうち何れか一つを選択すればよく、例えば、集合Ｈのうちで一番サイズの小さい要素を選ぶなどしてもよい。
【００９１】
具体的に、探索部１２は、集合ηに含まれる状態の集合ｇs毎に、第１引数を集合ｇs、第２引数を集合Ｈから集合ηを除いた集合（Ｈ＼｛η｝）として、区別不可能集合生成部１２３を用いて、サブプログラム“ｓｅａｒｃｈ＿ｓｈａｒａｂｌｅ＿ｓｔａｔｅ”を実行し、この実行により得られる戻り値の和集合をＧshareとする。なお、サブプログラム“ｓｅａｒｃｈ＿ｓｈａｒａｂｌｅ＿ｓｔａｔｅ”については後述する。
【００９２】
ステップＮ２５６では、探索部１２が、状態併合部１２１を用いてサブプログラム“ｍｅｒｇｅ＿ｓｔａｔｅｓ”を実行することで、ステップＮ２５５で検出した互いに区別不可能な状態を、一つの状態に併合する。同時に、区別不可能な状態に依存している状態もひとつにまとめられる。また、探索部１２は、ステップＮ２５６において併合により不要となり削除された状態を集合ｇeraseに代入する。なお、サブプログラム“ｍｅｒｇｅ＿ｓｔａｔｅｓ”は、ステップＮ２３１と同様であり、詳細については後述する。
【００９３】
続くステップＮ２５７〜Ｎ２６６の処理が、図３に示したステップＮ１１７の処理に対応する。ステップＮ２５７では、探索部１２が、集合ｇに含まれる区別不可能候補の依存関係を記録している集合Ｙscから、ステップＮ２５６での状態の併合処理により削除した状態に関する情報を除去する。
【００９４】
続くステップＮ２５８では、探索部１２が区別不可能候補集合生成部１２４を用いて、集合Ψの要素（ψ,ｘlevel）毎にサブプログラム“ｓｅａｒｃｈ＿ｓｈａｒａｂｌｅ＿ｓｔａｔｅ＿ｃａｎｄｉｄａｔｅ”を実行することで、区別不可能候補を見つける。ここで集合Ψは、集合Ｙscに含まれる要素のうち何れか一つを選択すればよく、例えば、集合Ｙscに含まれる要素のうちで一番サイズの小さい要素を選ぶなどしてもよい。
【００９５】
サブプログラム“ｓｅａｒｃｈ＿ｓｈａｒａｂｌｅ＿ｓｔａｔｅ＿ｃａｎｄｉｄａｔｅ”の第１引数はψ、第２引数はｘlevel、第３引数は集合Ｙscから集合Ψを取り除いた集合となる。“ｓｅａｒｃｈ＿ｓｈａｒａｂｌｅ＿ｓｔａｔｅ＿ｃａｎｄｉｄａｔｅ”は実行する度にその結果が戻り値として返ってくるので、探索部１２は、それらの和集合をΨscとする。なお、サブプログラム“ｓｅａｒｃｈ＿ｓｈａｒａｂｌｅ＿ｓｔａｔｅ＿ｃａｎｄｉｄａｔｅ”については後述する。
【００９６】
続いて、探索部１２は、ｘlevelが｜Ｓ｜以上の要素を集合Ψscから取り除く（ステップＮ２５９）。ここで、集合Ψscから取り除く理由は、自分自身や処理済みの状態へと依存することはないためである。
【００９７】
探索部１２は、ステップＮ２６０のｆｏｒｅａｃｈ文に従い、集合Ψscに含まれる各要素（ψsc，ｘlevel）について、ステップＮ２６１の処理を行う。ステップＮ２６１では、探索部１２が、区別不可能候補の依存関係をグローバル変数であるテーブルＤに記録する。
【００９８】
続いて、探索部１２は、ステップＮ２６２のｆｏｒｅａｃｈ文に従い、集合Ψscに含まれる各要素（ψscとｘlevel）について、ステップＮ２６３の処理を行う。また、探索部１２は、ステップＮ２６３のｆｏｒｅａｃｈ文に従い、Ｄ［｜Ｓ｜］の各要素ｄについて、ステップＮ２６４とＮ２６５の処理を行う。
【００９９】
ステップＮ２６４では、探索部１２が、ψscに含まれる各要素（ｑs,ｑd）に対して、ｑsを依存先の状態とするようなｄの要素を見つけ、それに対応している依存元の状態ｑ′sの依存先の状態をｑdへと変更した２つ組（ｑ′s,ｑd）の集合を生成し、それら全ての集合の和集合をｄpとする。続くステップＮ２６５では、探索部１２が、Ｄ［ｘlevel］にｄpを追加する。これら、ステップＮ２６２〜Ｎ２６５の処理で、集合ｇに含まれる区別不可能候補に依存している状態の依存先状態の付け替えが行われる。
【０１００】
次いで、探索部１２は、スタックＳでの｜Ｓ｜の格納位置に対応する依存関係を削除し（ステップＮ２６６）、スタックＳから今処理していた状態の集合γを取り除く（ステップＮ２６７）。
【０１０１】
次に、探索部１２は、集合Ψscが空集合φか否かを判定する（ステップＮ２６８）。空集合φでないと判定した場合には、ステップＮ２７０の処理に直ちに移行する。一方、空集合φであれば、集合ｇに含まれている状態は区別不可能候補となることはない。互いに区別不可能な状態があれば、ステップＮ２５６の処理によってそれらは既に一つにまとめられている。また、区別可能なら再度調べる必要はない。そこで、探索部１２は、集合Ｇの要素のうち集合ｇと一致する要素を集合Ｇから取り除く（ステップＮ２６９）。なお、ステップＮ２６８、Ｎ２６９の処理が、図３に示したステップＮ１１８の処理に対応している。
【０１０２】
また、集合ｇeraseに含まれる状態は既に削除済みであるので処理される必要はない。そこで、探索部１２は、ステップＮ２７０において、集合Ｇの要素である状態の集合から集合ｇeraseに含まれる状態を削除したものを集合Ｇ′とする（ステップＮ２７０）。ここで、集合Ｇ′の要素である状態の集合のサイズが１以下となるものは集合Ｇ′には含めないものとする。なお、ステップＮ２７０の処理が、図３に示したステップＮ１１９の処理に対応している。
【０１０３】
最後に、更新した集合Ｇ′と区別不可能候補の依存関係が記録された集合Ψscとで構成される２つ組を戻り値としてメインプログラム“ｓｉｍｉｎ”に返し（ステップＮ２７１）、“ｓｅａｒｃｈ＿ｅｑｕｉｖ”の処理を終了する。
【０１０４】
次に、図７を参照して、上述したステップＮ２３１のサブプログラム“ｎｅｘｔ＿ｇａｍｍａ”について説明する。図７は、サブプログラム“ｎｅｘｔ＿ｇａｍｍａ”の擬似コードの一例を示した図である。
【０１０５】
まず、遷移先集合生成部１２２は、遷移先状態と経路番号との２つ組（ｑn，ｉ）を記憶するための集合γnを空集合φとして初期化する（ステップＮ２８１）。
【０１０６】
続いて、遷移先集合生成部１２２は、ステップＮ２８２のｆｏｒｅａｃｈ文に従い、集合γに含まれる各要素についてステップＮ２８３を実行する。なお、ここで処理の対象となる集合γの各要素を（ｑ,ｉ）とすると、遷移元状態がｑであり、遷移に付随する入力記号がσである遷移の遷移先状態ｑnに関して、状態ｑnが集合γnに含まれていなければ、（ｑn，ｉ）の２つ組を集合γnに追加する（ステップＮ２８３）。
【０１０７】
集合γに含まれる全ての要素についてステップＮ２８３の処理が終了すると、遷移先集合生成部１２２は、その結果得られた集合γnをこのサブプログラム“ｎｅｘｔ＿ｇａｍｍａ”の戻り値として探索部１２に返す（ステップＮ２８４）。
【０１０８】
なお、図７で説明した疑似プログラムでは、遷移先状態が同じで経路番号が異なる２つ組がある場合に、最初にステップＮ２８３で処理された経路番号が残るようにしている。しかしながら、経路番号が異なるだけの２つ組が存在する場合には、｜γ｜＞｜γn｜となるので、他の集合γnに含まれる２つ組の経路番号と重複さえしなければ、どのような経路番号を付与してもよい。
【０１０９】
次に、図８を参照して、上述したステップＮ２５５のサブプログラム“ｓｅａｒｃｈ＿ｓｈａｒａｂｌｅ＿ｓｔａｔｅ”について説明する。図８は、サブプログラム“ｓｅａｒｃｈ＿ｓｈａｒａｂｌｅ＿ｓｔａｔｅ”の擬似コードの一例を示した図である。
【０１１０】
まず、区別不可能集合生成部１２３は、集合Ｈが空集合φか否かを判定する（ステップＮ２９１）。ここで、集合Ｈが空集合φである場合、全ての入力記号に関して積集合演算を終えたということを意味しているので、ステップＮ２９２の処理に移行する。また、集合Ｈが空集合φでない場合には、ステップＮ２９３の処理に移行する。
【０１１１】
ステップＮ２９２では、探索部１２から引数として与えられた集合ｇstartに含まれる状態を互いに区別不可能として確定することになるので、区別不可能集合生成部１２３は、集合ｇstartを集合Ｇsに追加するために、集合ｇstartのみを要素した集合を戻り値として返し（ステップＮ２９２）、“ｓｅａｒｃｈ＿ｓｈａｒａｂｌｅ＿ｓｔａｔｅ”を終了する。
【０１１２】
一方、ステップＮ２９３では、区別不可能集合生成部１２３が、状態の集合を要素とする集合を集合Ｈから一つ選択し、それを集合ηとする（ステップＮ２９３）。引数として渡された集合Ｈに含まれている限り、どの入力記号に対応するものを選択してもよい。例えば、集合Ｈの要素のうちでサイズが最も小さいものを選択することとしてもよい。
【０１１３】
次いで、区別不可能集合生成部１２３は、区別不可能な状態の集合を記録するために使用する集合Ｇsを空集合φとして初期化すると（ステップＮ２９４）、ステップＮ２９５のｆｏｒｅａｃｈ文に従い、集合ηに含まれる状態の集合ｇ′の全てについてステップＮ２９６〜Ｎ２９８の処理を繰り返し実行する。
【０１１４】
ステップＮ２９６では、区別不可能集合生成部１２３が、引数で渡された状態の集合ｇstartと集合ｇ′との積集合をｇisとする。次いで、区別不可能集合生成部１２３は、集合ｇisのサイズが２以上か否かを判定し（ステップＮ２９７）、集合ｇisのサイズが２以上の場合には、ステップＮ２９８の処理を実行する。なお、集合ｇisのサイズが１以下の場合には、区別不可能な状態が集合ｇisに存在せず、ステップＮ２９８の処理に寄与しないためステップＮ２９９の処理に直ちに移行する。
【０１１５】
ステップＮ２９８では、区別不可能集合生成部１２３が積集合演算で求めた集合ｇisと、集合Ｈから今処理している集合ηを除いたもの（Ｈ＼｛η｝）とを引数として、再帰的に“ｓｅａｒｃｈ＿ｓｈａｒａｂｌｅ＿ｓｔａｔｅ”を実行し、この再帰呼び出しの結果得られる区別不可能な状態の集合を集合Ｇsに追加する。
【０１１６】
そして、区別不可能集合生成部１２３は、全ての集合ｇ′について処理を終えると、得られた集合Ｇsを戻り値として返し（ステップＮ２９９）、“ｓｅａｒｃｈ＿ｓｈａｒａｂｌｅ＿ｓｔａｔｅ”を終了する。
【０１１７】
なお、探索部１２では、上述したようにステップＮ２５５において、集合Ｈから一つ選択した集合ηに含まれる状態の集合の全てに対して“ｓｅａｒｃｈ＿ｓｈａｒａｂｌｅ＿ｓｔａｔｅ”を実行し、その結果（戻り値）の和集合をとったものを区別不可能な状態の集合を要素とする集合Ｇshareとする。
【０１１８】
次に、図９を参照して、上述したステップＮ２２５及びＮ２５６のサブプログラム“ｍｅｒｇｅ＿ｓｔａｔｅｓ”について説明する。図９は、サブプログラム“ｍｅｒｇｅ＿ｓｔａｔｅｓ”の擬似コードの一例を示した図である。
【０１１９】
互いに区別不可能な状態を一つに併合するには、その中から代表とする状態を１つ選択し、入ってくる遷移（incoming  transition）をその代表状態へ遷移するように変更する。さらに代表状態以外の状態から出て行く遷移（outgoing  transition）を除去すればよい。言い換えると、２つの状態が互いに区別不可能な状態であるとし、代表状態つまり併合後に残留対象となる状態をｒ、残りの状態つまり削除対象の状態をｑe、遷移（遷移元状態、遷移先状態、入力記号）の集合Ｅで表すとき、入ってくる遷移については
Ｅ←｛（ｑs,ｒ,σ）∈Ｅ｜（ｑs,ｑd,σ）∈Ｅ,ｑd＝ｑe｝∪｛（ｑs,ｑd,σ）∈Ｅ｜ｑd≠ｑe｝のような操作をすればよく、出て行く遷移については、
Ｅ←｛（ｑs,ｑd,a）∈Ｅ｜ｑs≠ｑe｝のような操作をすればよい。
【０１２０】
そして、最後に状態の集合Ｑから状態ｑeを除去する。これらの処理を行うサブプログラムを“ｍｅｒｇｅ”とする。なお、“ｍｅｒｇｅ（ｒ,ｑe）”で集合Ｑからｑeを除去せず、メインプログラム“ｓｉｍｉｎ”が完了した後に、集合Ｑから状態ｑeをまとめて削除するように構成してもよい。
【０１２１】
サブプログラム“ｍｅｒｇｅ”の実行中に処理が中断されると、それまでの処理により状態数が削減されたＤＦＡを得ることができなくなる。併合する状態に依存している区別不可能候補の状態も併合する必要がある。これには上述した依存元状態、依存先状態の２つ組の集合を要素とした集合と同等の構造を持つ依存関係の情報を利用すればよい。
【０１２２】
まとめると、互いに区別不可能な状態と、それらに依存している互いに区別不可能候補である状態をと併合するアルゴリズム、即ち、サブプログラム“ｍｅｒｇｅ＿ｓｔａｔｅｓ”は図９に示したようになる。なお、図９では、ステップＮ２５６での“ｍｅｒｇｅ＿ｓｔａｔｅｓ”を前提に説明を進めるが、ステップＮ２３２の“ｍｅｒｇｅ＿ｓｔａｔｅｓ”についても引数が異なるのみで同様の処理が行われる。
【０１２３】
まず、状態併合部１２１は、集合Ｑeを空集合φとする（ステップＮ３０１）。続いて、状態併合部１２１は、ステップＮ３０２のｆｏｒｅａｃｈ文に従い、集合Ｇshareの各要素ｇsに関してステップＮ３０３〜Ｎ３１３までの処理を繰り返し実行する。
【０１２４】
ステップＮ３０３では、状態併合部１２１が、集合ｇsから何れか一つの状態を選択し、それを代表状態ｒとする。ここで、代表状態ｒは何れの状態であってもよいが、例えば状態番号が一番小さな状態を選択することとしてもよい。
【０１２５】
続いて、状態併合部１２１は、ステップＮ３０４のｆｏｒｅａｃｈ文に従い、状態の集合ｇsから状態ｒを除いた集合（ｇs＼｛ｒ｝）に含まれる各状態ｑeに対して、ステップＮ３０５とＮ３０６の処理を実行する。ステップＮ３０５において、状態併合部１２１は、代表状態ｒに集合ｑeに含まれる状態を併合する。続くステップＮ３０６において、状態併合部１２１は、ステップＮ３０５での併合により不要となった状態を集合Ｑeに追加する。
【０１２６】
次に、状態併合部１２１は、ステップＮ３０７のｆｏｒｅａｃｈ文に従い、Ｄ［｜Ｓ｜］に対応するＤelmに含まれる各要素ψに対して、ステップＮ３０８〜Ｎ３１３の処理を繰り返し実行する。
【０１２７】
ステップＮ３０８では、状態併合部１２１が、依存先状態が集合ｇsに含まれるような依存元の状態を集約し、それを集合ｇに追加する。次いで、状態併合部１２１は、集合ｇのサイズ｜ｇ｜が２以上か否かを判定する（ステップＮ３０９）。ここで集合ｇのサイズが２以上ならば、それらの状態は併合することが可能である。そのため、状態併合部１２１は、集合ｇから何れか一つの状態を選択し、それを代表状態ｒ′とする（ステップＮ３１０）。ここで、代表状態ｒ′は何れの状態であってもよいが、例えば状態番号が一番小さな状態を選択することとしてもよい。
【０１２８】
続いて、状態併合部１２１は、ステップＮ３１１のｆｏｒｅａｃｈ文に従い、集合ｇから状態ｒ′を除いた集合（ｇ＼｛ｒ′｝）に含まれる各状態ｑeに対して、ステップＮ３１２とＮ３１３の処理を実行する。ステップＮ３１２において、状態併合部１２１は、代表状態ｒ′に各状態ｑeを併合する。続くステップＮ３１３において、状態併合部１２１は、ステップＮ３１２での併合により不要となった状態を集合Ｑeに追加する。
【０１２９】
続いて、状態併合部１２１は、これまでの処理で得られた集合Ｑe、即ち、不要になった状態の集合を戻り値として探索部１２に返し、“ｓｅａｒｃｈ＿ｅｑｕｉｖ”の処理に再び戻る。なお、ステップＮ３０４〜Ｎ３１３の処理中に処理を中断すると、それまでの処理により状態数が削減されたＤＦＡを得ることはできない。そのため、後述する第５の実施形態のように、ステップＮ３０４〜Ｎ３１３の処理中に処理が中断されないよう制御する構成としてもよい。
【０１３０】
次に、図１０を参照して、上述したステップＮ２５８のサブプログラム“ｓｅａｒｃｈ＿ｓｈａｒａｂｌｅ＿ｓｔａｔｅ＿ｃａｎｄｉｄａｔｅ”について説明する。図１０は、サブプログラム“ｓｅａｒｃｈ＿ｓｈａｒａｂｌｅ＿ｓｔａｔｅ＿ｃａｎｄｉｄａｔｅ”の擬似コードの一例を示した図である。
【０１３１】
なお、図１０において、要素ψ及び要素ψstartは（依存元状態，依存先状態）の２つ組の集合に対応し、集合Ψは(ψ，依存先状態のスタックＳ上での位置)の２つ組の集合に対応し、集合Ｙは集合Ψを要素とする集合であって、各要素が各入力記号による結果に対応している。また、ｘstartはψstartの依存先状態のスタックＳ上での格納位置を表す。
【０１３２】
まず、区別不可能候補集合生成部１２４は、集合Ｙが空集合φか否かを判定し（ステップＮ３２１）、空集合φであればステップＮ３２２の処理を実行する。集合Ｙが空集合φであるということは、もう処理するべき要素が集合Ｙには残っていないということなので、要素ψstartに含まれる状態は集合Σgに含まれる全ての入力記号に対して区別不可能候補となる。したがって、区別不可能候補集合生成部１２４は、区別不可能候補の２つ組（ψstart,ｘstart）を本擬似コードの処理結果である集合Ψsに追加するために戻り値として返す（ステップＮ３２２）。
【０１３３】
続くステップＮ３２３では、区別不可能候補集合生成部１２４が、集合Ｙから任意の要素を一つ取り出してそれを集合Ψとする。ここでは、いずれの要素を取り出してもよく、例えば、サイズが最も小さい要素から取り出すこととしてもよい。
【０１３４】
続いて、区別不可能候補集合生成部１２４は、処理結果である区別不可能候補を記憶しておくための集合Ψsを空集合φとすると（ステップＮ３２４）、ステップＮ３２５のｆｏｒｅａｃｈ文に従って、集合Ψに含まれる各要素（ψ,ｘlevel）に対して、ステップＮ３２６〜Ｎ３３２までの処理を実行する。
【０１３５】
ステップＮ３２６では、区別不可能候補集合生成部１２４が、ｘstartとｘlevelとの大小関係を比較することで、依存先状態が要素ψに含まれる状態となるか、要素ψstartに含まれる状態となるかを判定する。依存先が複数あるときは常にスタックＳの底側、つまり循環経路の開始状態に近い側の状態が優先されるので、スタックＳ上での位置の値が小さいほうの状態が優先されることになる。したがって、区別不可能候補集合生成部１２４は、ｘstart＜ｘlevelのときは要素ψstartに含まれる依存先状態を採用する（ステップＮ３２７）。一方、ｘstart≧ｘlevelのときは、ステップＮ３２８に移行し、要素ψに含まれる依存先状態が優先される（ステップＮ３２９）。なお、ｘstart＝ｘlevelのときは、要素ψの状態ｑdも要素ψstartの状態ｑdも同じであるためどちらで処理しても良いが、ここではステップＮ３２９に含めている。
【０１３６】
区別不可能候補は要素ψstartと要素ψの両方に含まれなければならないので、ステップＮ３２７もＮ３２９も依存元状態に関しては積集合をとったものになる。その結果要素ψisには、区別不可能候補である依存元状態が要素ψstartと要素ψとの両方に含まれ、その依存先がスタックＳのより底側にある状態の２つ組に含まれることとなる。この要素ψisのサイズが１以下なら区別不可能候補になることはありえないので、区別不可能候補集合生成部１２４は、要素ψisのサイズが２以上の場合のみさらに以下処理を行うことになる（ステップＮ３３０）。
【０１３７】
ステップＮ３３１では、区別不可能候補集合生成部１２４が、後述するｘisに含まれる依存先状態のスタックＳ上での格納位置を求める。依存先状態はスタックＳ上での格納位置が小さいほうが選択されているので、ｘstartとｘlevelのうち小さいほうの値となる。この値をｘisとする。
【０１３８】
続いて、区別不可能候補集合生成部１２４は、ステップＮ３３１で処理した要素ψisを第１引数に、ｘisを第２引数に、集合ＹからステップＮ３２３で選択した集合Ψを除去した集合（Ｙ＼｛Ψ｝）を第３引数とし、サブプログラム“ｓｅａｒｃｈ＿ｓｈａｒａｂｌｅ＿ｓｔａｔｅ＿ｃａｎｄｉｄａｔｅ”を再帰的に実行し、そして得られた結果を集合Ψsに追加する（ステップＮ３３２）。そして、区別不可能候補集合生成部１２４は、これまでの処理で得られた結果となる集合Ψsを戻り値として返し（ステップＮ３３３）、“ｓｅａｒｃｈ＿ｓｈａｒａｂｌｅ＿ｓｔａｔｅ＿ｃａｎｄｉｄａｔｅ”の処理を終了する。
【０１３９】
なお、“ｓｅａｒｃｈ＿ｓｈａｒａｂｌｅ＿ｓｔａｔｅ＿ｃａｎｄｉｄａｔｅ”では、区別不可能な状態を明示的に取り扱ってはいないが、それらの状態は依存先が自分自身である区別不可能候補としてψに含めて処理すればよい。そうすることで区別不可能な状態が区別可能な状態として扱われることなく、区別不可能候補を見つけることができるようになる。この処理は例えば、“ｓｅａｒｃｈ＿ｅｑｕｉｖ”のステップＮ２４３に見られる。また、区別不可能か否かは“ｓｅｒａｃｈ＿ｓｈａｒａｂｌｅ＿ｓｔａｔｅ”で判明するので、両方を使えば区別可能、区別不可能、区別不可能候補の３種類を扱えることになる。
【０１４０】
以下、状態数削減処理部１０の動作について、具体例を示しながら説明する。
【０１４１】
まず、図１１に示したような、循環経路を有さないＤＦＡを処理対象とした場合の状態数削減処理部１０の動作について説明する。ここで、図１１は、ＤＦＡの一例を示した図であって、各円が状態を表しており、円内に記された数値が各状態を識別するための状態番号を表している。また、各円のうち太線の円が初期状態を表しており、二重線の円が終了状態を表している。図中、矢印は遷移を表しており、各矢印に付随する記号が入力記号を表している。
【０１４２】
状態数削減処理部１０は、図１１に示した処理対象となるＤＦＡに対し、メインプログラム“ｓｉｍｉｎ”を実行する。以下、各プログラムでの主要な処理内容について説明する。
【０１４３】
まず、状態数削減処理部１０は、スタックＳとテーブルＤとを空集合φで初期化する（ステップＮ２０１）。続いて、状態分類部１１を用いてサブプログラム“ｃｒｅａｔｅ＿ｃｌａｓｓ”を実行し、状態の終了性と出て行く遷移の入力記号の集合とが同一の状態毎に、処理対象のＤＦＡを構成する各状態を分類する（ステップＮ２０２）。この結果、状態０と、状態１、２、３、４と、状態５、６、７と、状態８とに分類されることが分かる。ここで、状態数が１個の分類は不要とするため、Ｇ＝｛｛１,２,３,４｝,｛５,６,７｝｝となる。
【０１４４】
図１２は、図１１に示したＤＦＡの状態分類後の構成を示した図である。ここで、破線で囲った部分が夫々の分類であり、状態１、２、３、４が１つの分類に、状態５、６、７がもう１つの分類になっていることが分かる。
【０１４５】
このとき、集合Ｇは空集合φではないので、状態数削減処理部１０はステップＮ２０３の条件を満たすと判定し、集合Ｇに含まれる任意の要素を一つ選択する（ステップＮ２０４）。ここで、状態数削減処理部１０は、ｇ＝｛１,２,３,４｝を選択したとする。
【０１４６】
次いで、状態数削減処理部１０は、サブプログラム“ａｄｄ＿ｐａｔｈ＿ｉｎｄｅｘ”を実行し、集合ｇの各要素に経路番号を付与し、その結果をγ＝｛（１,１）,（２,２）,（３,３）,（４,４）｝としてサブプログラム“ｓｅａｒｃｈ＿ｅｑｕｉｖ”の第１引数として使用する。上述したとおり、集合γの要素である２つ組は（状態，経路番号）で構成されているため、（１,１）は状態の名前（状態番号）が１、経路番号が１であることを意味している。
【０１４７】
探索部１２では、状態数削減処理部１０からの指示に応じ、サブプログラム“ｓｅａｒｃｈ＿ｅｑｕｉｖ”の処理に入る。まず、探索部１２は、ステップＮ２２１において、集合γから状態番号のみを取り出すため、その結果はｇ＝｛１,２,３,４｝となり、続くステップＮ２２２ではΣg＝｛a｝となる。
【０１４８】
続いて、探索部１２は、集合Ψscを空集合φとすると（ステップＮ２２３）、このときの集合Σgが、Σg≠φであるため、ステップＮ２２７で集合Ｈ、集合Ｙscを空集合φとし、ステップＮ２２８でスタックＳに集合γを格納する。
【０１４９】
図１３は、スタックＳの状態を模式的に示した図であって、上述したステップＮ２２８直後の状態を表している。同図に示したように、γ＝｛（１,１）,（２,２）,（３,３）,（４,４）｝がスタックＳに格納される。なお、集合γの左部に示す数値は、スタックＳの底から数えた集合γの格納位置を表している。
【０１５０】
続いて、探索部１２は、ステップＮ２２９のｆｏｒｅａｃｈ文に従い、σの各値についてステップＮ２３０〜Ｎ２５４を処理することになるが、Σg＝｛ａ｝であるため、σ＝ａについて一度だけ処理することになる（ステップＮ２２９）
【０１５１】
ここで、探索部１２は、遷移先集合生成部１２２を用いてステップＮ２３１の“ｎｅｘｔ＿ｇａｍｍａ”を実行すると、その結果として、γn＝｛（５,１）,（６,２）,（７,３）,（８,４）｝が得られる。具体的には、状態１の遷移先が状態５であり、状態１の経路番号が１であるため、状態５の経路番号は１となる。他の要素についても同様である。
【０１５２】
このとき、図１３に示したように、スタックＳには、γ＝{（１,１）,（２,２）,（３,３）,（４,４）}が記録されているのみであるため、集合γnはスタックＳには存在しない。したがって、探索部１２は、ステップＮ２３３以降の処理を行うことになる。
【０１５３】
続く、ステップＮ２３４〜Ｎ２３７までの処理では、探索部１２が、各集合ｇ′と集合γnに含まれる状態の集合との積集合γniに対して処理を行う。ステップＮ２３５の条件にあるように、｜γni｜＞１が成り立つのはｇ′＝｛５,６,７｝の場合のみであり、このときγni＝｛（５,１）,（６,２）,（７,３）｝である。
【０１５４】
続くステップＮ２３６において、探索部１２は、サブプログラム“ｓｅａｒｃｈ＿ｅｑｕｉｖ”を再帰的に実行するため、γ＝｛（５,１）,（６,２）,（７,３）｝としてステップＮ２２１から処理を行っていくことになる。この再帰処理時におけるステップＮ２２１の処理では、ｇ＝｛５,６,７｝となる。また、ステップＮ２２２の処理でΣg＝φとなるため、探索部１２は、ステップＮ２２５の処理を実行することになり、集合γに含まれる状態、つまり、状態５、６、７を一つの状態に併合する。
【０１５５】
ここでは、状態５を残し、状態６、７を状態５へ併合することにすると、図１２で示したＤＦＡは図１４のようになる。この場合、ステップＮ２２５で導出される集合ｇeraseは、ｇerase＝｛６,７｝となる。なお、図１４は、図１１に示したＤＦＡの状態併合後の構成を示した図である。
【０１５６】
また、Ψsc＝φであるので、探索部１２は、ステップＮ２６８の条件を満たすと判定し、ステップＮ２６９の処理を実行する。今、ｇ＝｛５,６,７｝、Ｇ＝｛｛１,２,３,４｝,｛５,６,７｝｝であるので、集合Ｇの要素に集合ｇが存在する。したがって、ステップＮ２６９の処理で、Ｇ＝｛｛１,２,３,４｝｝となる。
【０１５７】
また、ステップＮ２７０では、探索部１２が、集合ｇeraseに含まれる状態、つまり削除された状態を含む集合Ｇの各要素から削除したものを集合Ｇ′とする。このとき、集合ｇeraseに含まれる状態６と７は、ステップＮ２６９の処理で集合Ｇから既に削除されているので、Ｇ′＝｛｛１,２,３,４｝｝となる。また、Ψsc＝φであるため、（｛｛１,２,３,４｝｝,φ）が戻り値となる。
【０１５８】
探索部１２は、ステップＮ２３６で再帰的に実行したサブプログラム“ｓｅａｒｃｈ＿ｅｑｕｉｖ”の戻り値を、集合Ｇと集合Ψnsctとに夫々代入する。さらに、探索部１２は、集合Ψnsctに含まれる全ての要素を集合Ψnscに追加する（ステップＮ２３７）。この場合、Ψnsct＝φであるため、追加する要素は何もない。
【０１５９】
続くステップＮ２３８において、探索部１２は、集合γに含まれる遷移先状態の集合を再度作成する。先ほどの再帰呼び出しによって、遷移先状態５、６、７は一つの状態５になっているので、ｇn＝｛５,８｝となる。続いて、探索部１２は、ステップＮ２４０〜Ｎ２４３の処理を集合ｇnに含まれる全ての要素ｑnについて実行する（ステップＮ２３９）。
【０１６０】
ここで、まずｑn＝５の場合を考える。探索部１２は、ステップＮ２４０で状態５の遷移元状態を集合ｇsに代入するので、ｇs＝｛１,２,３｝となる。これにより、｜ｇs｜＝３となるため、探索部１２は、ステップＮ２４１の条件を満たすと判定し、ステップＮ２４２の処理を実行すると、η＝｛｛１,２,３｝｝となる。また、探索部１２は、ステップＮ２４３を実行すると、｜Ｓ｜＝１であるので、Ψsc＝｛（｛（１,１）,（２,２）,（３,３）｝,１）となる。
【０１６１】
次に、ｑn＝８の場合を考える。この場合、ステップＮ２４０で得られる集合ｇsはｇs＝｛４｝であるので、｜ｇs｜＝１となる。したがって、探索部１２は、ステップＮ２４１の条件を満たさないと判定するため、ステップＮ２４２とＮ２４３の処理は実行されない。また、Ψnsc＝φなので、ステップＮ２４４〜Ｎ２４８の処理も実行されない。そして、探索部１２は、ステップＮ２５４の処理を実行することで、Ｙsc＝｛｛（｛（１,１）,（２,２）,（３,３）｝,１）｝｝と、Ｈ＝｛｛｛１,２,３｝｝｝とを取得する。
【０１６２】
これで集合Σgに含まれる全ての入力記号について処理が完了したので、次はステップＮ２５５が実行される。ここでは、η＝｛｛１,２,３｝｝であり、集合ηの要素は一つのみであるため、探索部１２は、ｇs＝｛１,２,３｝、Ｈ＼｛η｝＝φを引数とし、区別不可能集合生成部１２３を用いて、サブプログラム“ｓｅａｒｃｈ＿ｓｈａｒａｂｌｅ＿ｓｔａｔｅ”を実行すると、｛｛１，２,３｝｝が結果として返る。他に“ｓｅａｒｃｈ＿ｓｈａｒａｂｌｅ＿ｓｔａｔｅ”を実行する集合ηの要素はないので、Ｇshare＝｛｛１,２,３｝｝となる。
【０１６３】
続いて、探索部１２は、ステップＮ２５６において、状態併合部１２１を用いてサブプログラム“ｍｅｒｇｅ＿ｓｔａｔｅｓ”を実行することで、集合Ｇshareに含まれる状態を一つに併合する。このとき、依存関係の情報であるＤ［｜Ｓ｜］は空集合φなので、状態併合部１２１は、単に集合Ｇshareに含まれる状態の集合を一つの状態に併合するだけである。
【０１６４】
ここでは、状態１のみを残し、状態２、３を削除することとすると、図１４に示したＤＦＡは図１５のようになる。この場合、ステップＮ２５６で導出される集合ｇeraseは、ｇerase＝｛２,３｝となる。なお、図１５は、図１４に示したＤＦＡの状態併合後の構成を示した図である。
【０１６５】
続くステップＮ２５７において、探索部１２は集合ｇeraseに含まれる状態を集合Ｙscから削除するが、今の場合、集合Ｙscの要素は空集合φのみであるため変化しない。また、ステップＮ２５８も同様で、Ψsc＝φとなる。さらに、ステップＮ２５９〜Ｎ２６５までは何も起きず、ステップＮ２６６においても、この処理を実行する以前からＤ［｜Ｓ｜］＝φであるため、Ｄ［｜Ｓ｜］に変化はない。
【０１６６】
続くステップＮ２６７において、探索部１２が、スタックＳの一番上の要素（つまり、格納位置１のγ）を破棄すると、スタックＳ＝φとなる。
【０１６７】
また、探索部１２は、Ψsc＝φであるため、ステップＮ２６８の条件を満たすと判定すると、ｇ＝｛１,２,３,４｝、Ｇ＝｛｛１,２,３,４｝｝であるので、ステップＮ２６９の処理結果はＧ＝φとなる。続くステップＮ２７０で探索部１２は、集合ｇeraseに含まれる状態を集合Ｇから除くのだが、今の場合、既に集合Ｇは空集合であるので集合Ｇ′は空集合φとなる。したがって、ステップＮ２５１の戻り値は（φ,φ）となる。
【０１６８】
メインプログラム“ｓｉｍｉｎ”に戻り、状態数削減処理部１０は、サブプログラムの“ｓｅａｒｃｈ＿ｅｑｕｉｖ”からの戻り値を集合Ｇに代入すると、Ｇ＝φとなる。ステップＮ２０３に再び戻り、状態数削減処理部１０は、条件文を評価するとＧ≠φの条件を満たさないので、メインプログラム“ｓｉｍｉｎ”の処理を終了する。以上の処理により、処理対象としたＤＦＡの状態数は最小化されることになる。
【０１６９】
次に、図１６に示したような、循環経路を有するＤＦＡを処理対象とした場合の状態数削減処理部１０の動作について説明する。ここで、図１６は、ＤＦＡの一例を示した図である。記法は図１１と同じである。
【０１７０】
状態数削減処理部１０は、図１６に示した処理対象となるＤＦＡに対し、メインプログラム“ｓｉｍｉｎ”を実行する。以下、各プログラムでの主要な処理内容について説明する。
【０１７１】
まず、状態数削減処理部１０は、スタックＳとテーブルＤとを空集合φで初期化する（ステップＮ２０１）。続いて、状態分類部１１を用いてサブプログラム“ｃｒｅａｔｅ＿ｃｌａｓｓ”を実行し、状態の終了性と出て行く遷移に付随する入力記号の集合とに基づいて、処理対象のＤＦＡを構成する各状態を分類する（ステップＮ２０２）。この結果、状態０と、状態１、２、３、７と、状態４、５、６と、状態８とに分類されることが分かる。ここで、状態数が１個の分類は不要とするため、Ｇ＝｛｛１,２,３,７｝,｛４,５,６｝｝となる。
【０１７２】
図１７は、図１６に示したＤＦＡの状態分類後の構成を示した図である。ここで、破線で囲った部分が夫々の分類を表しており、状態１、２、３、７が１つの分類に、状態４、５、６がもう１つの分類になっていることが分かる。
【０１７３】
ここで、状態の集合｛１,２,３,７｝は全て終了状態でなく、出て行く遷移の入力記号から成る集合も全て｛ａ｝である。また、状態の集合｛４,５,６｝も全て終了状態でなく、出て行く遷移の入力記号から成る集合も全て｛ｂ，ｃ｝である。以下ではまず、｛４,５,６｝についてのサブプログラム“ｓｅａｒｃｈ＿ｅｑｕｉｖ”の実行時について説明する。
【０１７４】
探索部１２が、ステップＮ２２３まで実行した時点では、γ＝｛（４,１）,（５,２）,（６,３）｝、ｇ＝｛４,５,６｝、Σg＝｛ｂ,ｃ｝となる。
【０１７５】
ここで、Σg≠φなのでステップＮ２２７以降の処理が実行されることになり、ステップＮ２２８でＳ＝｛｛（４,１）,（５,２）,（６,３）｝｝となる。ここで、図１８は、スタックＳの状態を模式的に示した図であって、上述したステップＮ２２８直後の状態を表している。なお、同図では、スタックＳに記録された要素（集合γ）を矩形で表している。また、各要素に含まれる状態番号と経路番号との２つ組の個数を、その個数に応じた小領域に区分けすることで表している。この例では、スタックＳの要素に状態番号と経路番号との２つ組が３つ含まれているので、この要素を３つに区分けしている。
【０１７６】
各小領域上に示した数値は、この小領域に対応する２つ組に含まれる状態番号を表しており、各小領域の下部に示した数値は、この小領域に対応する２つ組に含まれる経路番号を表している。また、要素の左部に示す数値は、スタックＳの底から数えた要素の位置であり、スタックＳ上での格納位置を表している。
【０１７７】
探索部１２は、ステップＮ２２９からの処理について、例えば、σ＝ｂから処理を開始すると、ステップＮ２３１の処理により、入力記号ｂによる集合γの遷移先状態の集合γnを得る。具体的には、入力記号ｂによる状態４の遷移先は状態１であり、状態５は状態２に、状態６は状態３に遷移するが、状態数は減少しないので、経路番号は維持されなければならない。そのため状態１の経路番号には状態４の経路番号である１が割り当てられる。他の状態も同様に処理すると、γn＝｛（１,１）,（２,２）,（３,３）｝となる。
【０１７８】
続くステップＮ２３２において、探索部１２は、集合γnがスタックＳには存在しないと判定するため、ステップＮ２３３以降の処理を実行することになる。ここで、ステップＮ２３５の｜γni｜＞１となるような集合γniは、γni＝｛（１,１）,（２,２）,（３,３）｝のみであるため、探索部１２は、この集合γniについてサブプログラム“ｓｅａｒｃｈ＿ｅｑｕｉｖ”を再帰的に実行する。
【０１７９】
再帰処理時におけるステップＮ２２１の処理で、ｇ＝｛１,２,３｝が得られる。今、引数として渡されている集合γは、γ＝｛（１,１）,（２,２）,（３,３）｝であるからである。また、ステップＮ２２２の処理でΣg＝｛ａ｝が得られる。このとき、Σg≠φであるため、探索部１２は、ステップＮ２２７の処理に移行し、ステップＮ２２８において集合γをスタックＳに格納する。即ち、スタックＳは、Ｓ＝｛｛（４,１）,（５,２）,（６,３）｝,｛（１,１）,（２,２）,（３,３）｝｝となる。なお、スタックＳの左側の要素ほどスタックの底側にある要素であるとしている。このときのスタックＳの状態を図示すると、図１９のようになる。ここで、図１９は、スタックＳの状態を模式的に示した図であって、再帰処理時におけるステップＮ２２８直後の状態を表している。
【０１８０】
また、集合Σgは入力記号ａのみを含んでいるので、探索部１２は、σ＝ａとしてステップＮ２３０以降を実行することになる。ステップＮ２３１において、探索部１２は、γn＝｛（４,１）,（５,２）,（６,３）｝を得る。そのため、ステップＮ２３２において、探索部１２は、集合γnがスタックＳに存在すると判定するため、ステップＮ２４９以降の処理を実行することになる。
【０１８１】
ステップＮ２５０において、探索部１２は、ψsc＝｛（１,４）,（２,５）,（３,６）｝を取得する。ここで、各２つ組の１番目は依存元の状態を、２番目は依存先の状態を表している。そして、探索部１２は、続くステップＮ２５１の処理により、Ψsc＝｛（｛（１,４）,（２,５）,（３,６）｝,１）｝を取得する。つまり、依存元状態が集合γに含まれる状態１、２、３であり、夫々に対応する遷移先状態である依存先状態が状態４、５、６ということである。また、最後の値が１なのは、集合γnが見つかったスタックＳでの格納位置がスタックの底、つまり１だからである。
【０１８２】
また、このときγ≠γn、つまり自己遷移ではないため、探索部１２はステップＮ２５３の処理を実行せず、ステップＮ２５４の処理を実行することで、Ｙsc＝｛｛（｛（１,４）,（２,５）,（３,６）｝,１）｝｝、Ｈ＝｛｛｝｝を取得する。
【０１８３】
続くステップＮ２５５において、探索部１２は、区別不可能集合生成部１２３を用いて“ｓｅａｒｃｈ＿ｓｈａｒａｂｌｅ＿ｓｔａｔｅ”を実行することで、集合Ｈの要素から区別不可能な状態を探索するが、この場合、集合Ｈの要素は空集合のみであるため、Ｇshare＝φとなる。そのため、ステップＮ２５６の処理では、その状態も併合することができず、ｇerase＝φとなる。
【０１８４】
また、ｇerase＝φであるため、探索部１２がステップＮ２５７を実行しても集合Ｙscに変化はない。集合Ｙscのサイズは１であるため、ステップＮ２５８で実行されるサブプログラム“ｓｅａｒｃｈ＿ｓｈａｒａｂｌｅ＿ｓｔａｔｅ＿ｃａｎｄｉｄａｔｅ”は、ステップＮ３２１、Ｎ３２２だけが実行され、その結果、Ψsc＝｛（｛（１,４）,（２,５）,（３,６）｝,１）｝が得られる。
【０１８５】
続いて、探索部１２は、ステップＮ２５９を実行する。このとき、集合Ψscの要素は一つであり、その要素がｘlevel＝１、｜Ｓ｜＝２であるので、ｘlevel＜｜Ｓ｜となり集合Ψscは変化しない。そして、探索部１２は、ステップＮ２６０とＮ２６１で、集合Ψscで表されている依存関係を、テーブルＤに記録する。その結果、Ｄ［１］＝｛｛（１,４）,（２,５）,（３,６）｝｝となる。これは、図示すると図２０のようになる。
【０１８６】
ここで図２０は、テーブルＤの状態を模式的に示した図であって、（依存元状態，依存先状態）の２つ組を円で囲んで表している。また、これら２つ組を要素とする集合をハッチングを施した領域で表しており、更に、それを要素とする集合をハッチング領域を囲む矩形領域で表している。
【０１８７】
ところで、Ｄ［２］＝φであるので、探索部１２がステップＮ２６２〜Ｎ２６６を実行しても変化は生じない。続くステップＮ２６７において、探索部１２は、スタックＳの一番上の要素を取り除くと、Ｓ＝｛｛{（４,１）,（５,２）,（６,３）}｝となる。このとき、集合Ψscは空集合φではないので、探索部１２は、ステップＮ２６８の条件を満たさないと判定し、ステップＮ２６９の処理を実行しない。
【０１８８】
また、ステップＮ２７０では、ｇerase＝φであるため集合Ｇに変化はない。したがって、Ｇ′＝｛｛１,２,３,７｝,｛４,５,６｝｝となる。そして、探索部１２は、再帰処理により求めた集合Ｇ′と集合Ψscとを戻り値として返す。ステップＮ２３６の再帰処理から戻ると、Ｇ＝｛｛１,２,３,７｝,｛４,５,６｝｝、Ψnsct＝｛（｛（１,４）,（２,５）,（３,６）｝,１）｝となる。つまり、集合Ｇに変化はない。
【０１８９】
次いで、探索部１２は、ステップＮ２３７にてΨnsc＝｛（｛（１,４）,（２,５）,（３,６）｝,１）｝を取得する。他に処理すべき集合ｇ′はないので、ステップＮ２３８の処理へと移行する。なお、ステップＮ２３６の再帰処理時に一つにまとめられた状態はないので、遷移先状態の集合はｇn＝｛１,２,３｝となる。そのため、ステップＮ２３９〜Ｎ２４３の処理では変化は生じない。なぜならば、集合ｇnに含まれる各状態の入力記号ｂに対応する遷移元状態の数は全て１であるからである。
【０１９０】
次に、探索部１２は、ステップＮ２４４〜Ｎ２４８の処理を行うことになる。集合Ψnscの要素数は１なので、このループ内の処理はψnsc＝｛（１,４）,（２,５）,（３,６）｝、ｘlevel＝１として１回だけ行われることになる。
【０１９１】
ステップＮ２４５で集合ｇに含まれる状態の依存情報が作成されることになり、ψsc＝｛（４,４）,（５,５）,（６,６）｝となる。このとき、｜Ｓ｜＝１であるため、ステップＮ２４６の条件が満たされることになり、探索部１２は、ステップＮ２４７でη＝｛｛４,５,６｝｝を取得する。そして、探索部１２は、ステップＮ２４８の処理で、Ψsc＝｛（｛（４,５）,（５,５）,（６,６）｝,１）｝を取得する。そして、ステップＮ２５４において、探索部１２は、Ｙsc＝｛｛（｛（４,４）,（５,５）,（６,６）｝,１）｝｝と、Ｈ＝｛｛｛４,５,６｝｝｝とを取得する。
【０１９２】
現在、Σg＝｛ｂ,ｃ｝であり、先ほど入力記号ｂに関する処理は終了したので、今度は入力記号ｃに関する処理を行う。すると、ステップＮ２３１では、γn＝｛（７,１）,（８,２）｝となる。経路番号が変わっているが、これは、サイズが｜γ｜より減っており、経路番号の付け替えが可能であるためである。なお、理由はサブプログラム“ｓｅａｒｃｈ＿ｅｑｕｉｖ”の説明の際に述べたとおりである。
【０１９３】
今、Ｇ＝｛｛１，２，３，７｝，｛４,５,６｝｝であるので、これと集合γnの要素である２つ組のうち、左側の値として記録されている状態との積集合をとっても、サイズが２以上になるものはない。したがって、ステップＮ２３３〜Ｎ２３７では変化は生じない。そして、ステップＮ２３８の処理結果は、ｇn＝｛７,８｝となる。
【０１９４】
ステップＮ２３９〜Ｎ２４３のループにおいて、ｑn＝７の場合は遷移元状態が一つのみなので、ｑn＝８の場合のみを考えればよい。ｑn＝８のときステップＮ２４０でｇs＝｛４,５｝となる。このとき、｜ｇs｜＝２となるので、これは１よりも大きい。したがって、ステップＮ２４１が満たされ、ステップＮ２４２へと処理が移行する。続くステップＮ２４２でη＝｛｛４,５｝｝となり、ステップＮ２４３でΨsc＝｛（｛（４,４）,（５,５）｝,１）｝となる。
【０１９５】
次いで、ステップＮ２４４〜Ｎ２４８の処理は集合Ψnscが空集合φなので、何も処理されない。これは、σ＝ｃに対応するループの最初の行であるステップＮ２３０の処理で、集合Ψnscが空集合φになっているからである。
【０１９６】
続いて、探索部１２がステップＮ２５４を実行すると、Ｙsc＝｛｛（｛（４,４）,（５,５）,（６,６）｝,１）｝,｛（｛（４,４）,（５,５）｝,１）｝｝と、Ｈ＝｛｛｛４,５,６｝｝,｛｛４,５｝｝｝のようになる。これで集合Σgに含まれる入力記号に対する処理を全て終えたので、ステップＮ２５５の処理に移行する。
【０１９７】
続くステップＮ２５５では、探索部１２が集合Ｈから要素を一つ選択して集合ηに設定する。なお、ここではη＝｛｛４,５,６｝｝を選択したとする。この場合、集合ηに含まれる要素は一つであるため、探索部１２は、区別不可能集合生成部１２３を用いて、ｇs＝｛４,５,６｝に対してサブプログラム“ｓｅａｒｃｈ＿ｓｈａｒａｂｌｅ＿ｓｔａｔｅ”を実行する。なお、Ｈ＼｛η｝＝｛｛｛４,５｝｝｝である。
【０１９８】
サブプログラム“ｓｅａｒｃｈ＿ｓｈａｒａｂｌｅ＿ｓｔａｔｅ”が実行されると、引数として集合ｇsとＨ＼｛η｝とが渡されているので、ｇstart＝｛４,５,６｝、Ｈ＝｛｛｛４,５｝｝｝となる。集合Ｈは空集合φではないので、ステップＮ２９３から実行されることになる。
【０１９９】
区別不可能集合生成部１２３は、ステップＮ２９３において、集合Ｈから任意の要素を一つ取り出す。いま、集合Ｈには一つしか要素がないので、η＝｛｛４,５｝｝となる。さらに集合ηの要素は一つなので、ステップＮ２９６〜Ｎ２９８の処理はｇ′＝｛４,５｝に対して一度だけ実行されることになる。
【０２００】
続いて、区別不可能集合生成部１２３は、ステップＮ２９６の処理を実行すると、ｇis＝｛４,５,６｝∩｛４,５｝＝｛４,５｝となる。このとき｜ｇis｜＝２であるため、区別不可能集合生成部１２３は、ステップＮ２９７の条件を満たすと判定し、ステップＮ２９８の処理を実行する。次いで、区別不可能集合生成部１２３は、ステップＮ２９８で再帰的にサブプログラム“ｓｅａｒｃｈ＿ｓｈａｒｅｄ＿ｓｔａｔｅ”を実行する。再帰的に呼び出されたとき、引数はｇstart＝｛４,５｝、Ｈ＝φである。したがって、ステップＮ２９１の条件が満たされ、ステップＮ２９２で｛｛４,５｝｝が戻り値として返されることになる。この再帰呼び出しから戻ると、ステップＮ２９８でその結果が集合Ｇsに追加され、Ｇs＝｛｛４,５｝｝となる。そして、ステップＮ２９９でこの集合Ｇsが戻り値として返される。
【０２０１】
サブプログラム“ｓｅａｒｃｈ＿ｓｈａｒｅｄ＿ｓｔａｔｅ”が完了すると、ステップＮ２５５に処理が戻る。集合ηの要素は一つなので、これ以上“ｓｅａｒｃｈ＿ｓｈａｒｅｄ＿ｓｔａｔｅ”を実行する必要はない。したがって、Ｇshare＝｛｛４,５｝｝となる。
【０２０２】
続くステップＮ２５６において、探索部１２は集合Ｇshareに含まれる要素を夫々併合する。今、｜Ｓ｜＝１であるため、Ｄ［１］＝｛｛（１,４）,（２,５）,（３,６）｝｝である。ここで、探索部１２は、状態併合部１２１を用いてサブプログラム“ｍｅｒｇｅ＿ｓｔａｔｅｓ”を実行すると、このときの引数はＧshare＝｛｛４,５｝｝、Ｄelm＝｛｛（１,４）,（２,５）,（３,６）｝｝となる。集合Ｇshareのサイズは１なので、状態併合部１２１は、ステップＮ３０２でｇs＝｛４,５｝を選択する。
【０２０３】
状態併合部１２１は、ステップＮ３０３で集合ｇsから任意の要素を一つ取り出し、ｒに代入する。ここで取り出した状態は、一つにまとめられる状態の集合の代表（代表状態）であり、削除されずに残ることになる。ここでｒ＝４とすると、状態併合部１２１は、ステップＮ３０４〜Ｎ３０６において、ｇs＼｛ｒ｝に含まれる状態をｒ＝４に併合する。今の場合はｑe＝５であるため、状態５を状態４へと併合すると、図１６に示したＤＦＡは図２１となる。なお、図２１は、図１６に示したＤＦＡの状態併合後の構成を示した図である。
【０２０４】
図２１に示したように、状態５は併合により不要となり削除対象となるので、状態併合部１２１は、ステップＮ３０６において、ｑe＝５をＱeに追加する。したがって、Ｑe＝｛５｝となる。
【０２０５】
続いて、状態併合部１２１は、Ｄelmに含まれる各要素について、ステップＮ３０７〜Ｎ３１３の処理を実行する。今はＤelmに含まれる要素は一つであるため、ψ＝｛（１,４）,（２,５）,（３,６）｝の場合のみを処理すればよい。ステップＮ３０８では、集合ｇsに含まれる状態を依存先の状態ｑdとするようなψに含まれる２つ組の依存元状態ｑsから構成される集合を得ることになる。
【０２０６】
ｇs＝｛４,５｝であるため、ψに含まれる要素である２つ組の２番目の要素（依存先状態）が４であるような１番目の要素（依存元状態）の値は１であり、同様に２番目の要素（依存先状態）が５であるような１番目の要素（依存元状態）の値は２である。したがって、ｇ＝｛１,２｝となる。｜ｇ｜＝２であるためステップＮ３０９の条件を満たし、状態併合部１２１は、ステップＮ３１０以降の処理を実行することになる。
【０２０７】
ステップＮ３１０では、状態併合部１２１が、代表状態を選択する。ここでは状態１を選択することにする。集合ｇに含まれる状態のうち、残りは状態２だけとなるため、図２２に示したように、ステップＮ３１２で状態１と状態２とを併合する。なお、図２２は、図２１に示したＤＦＡの状態併合後の構成を示した図である。
【０２０８】
図２２に示したように、状態２は併合により不要となり削除対象となるので、状態併合部１２１は、ステップＮ３１３において、ｑe＝２をＱeに追加する。その結果、 Ｑe＝｛２,５｝となる。そして、状態併合部１２１は、他に処理する要素が集合Ｇshareに含まれないと判定するため、ステップＮ３１４に処理が移り、削除された状態の集合Ｑeを戻り値として返す。また、サブプログラム“ｍｅｒｇｅ＿ｓｔａｔｅｓ”の処理が終了したので、ステップＮ２５６の処理に戻る。なお、戻り値は集合ｇeraseに代入されるので、ｇerase＝｛２,５｝となる。
【０２０９】
ステップＮ２５７では、探索部１２が削除された状態を含む２つ組を、集合Ｙscから除去する。ここで、ステップＮ２５７の処理前では、Ｙsc＝｛｛（｛（４,４）,（５,５）,（６,６）｝,１）｝,｛（｛（４,４）,（５,５）｝,１）｝｝であるが、処理後はＹsc＝｛｛（｛（４,４）,（６,６）｝,１）｝,｛（｛（４,４）｝,１）｝となる。
【０２１０】
また、探索部１２は、ステップＮ２５８を実行するため、集合Ｙscから要素を一つ取り出し集合Ψとする。ここでは、Ψ＝｛（｛（４,４）｝,１）｝とする。さらに、その要素である２つ組からψ＝｛（４,４）｝となる。しかし、ψは要素を一つしか含んでいないので、サブプログラム“ｓｅａｒｃｈ＿ｓｈａｒａｂｌｅ＿ｓｔａｔｅ＿ｃａｎｄｉｄａｔｅ”を実行しても、ステップＮ３３０が満たされることがないので、結局、Ψsc＝φとなる。さらに、探索部１２がステップＮ２５９を実行しても、Ψsc＝φとなるため、ステップＮ２６０〜Ｎ２６５の処理は実行されない。
【０２１１】
Ｄ［１］＝｛｛（１,４）,（２,５）,（３,６）｝｝であるが、この情報はもう不要であるため、探索部１２は、ステップＮ２６４の処理でＤを空集合φへと置き換える。続くステップＮ２６７で、探索部１２は、スタックＳに格納された一番上の要素を削除し、ステップＮ２６８の処理に移行する。このとき、Ψsc＝φであるのでステップＮ２６８の条件は満たされ、ステップＮ２６９へと処理が移行する。具体的には、ｇ＝｛４,５,６｝、Ｇ＝｛｛１,２,３,７｝,｛４,５,６｝｝であるため、Ｇ＝｛｛１,２,３,７｝｝となる。
【０２１２】
また、ｇerase＝｛２,５｝であるため、探索部１２は、ステップＮ２７０において集合Ｇの各要素から集合ｇeraseに含まれている状態を取り除くと、Ｇ′＝｛｛１,３,７｝｝となる。そのため、ステップＮ２７１の戻り値は（｛｛１,３,７｝｝,φ）となり、“ｓｉｍｉｎ”のステップＮ２０５に戻る。ステップＮ２０５において、状態数削減処理部１０は“ｓｅａｒｃｈ＿ｅｑｕｉｖ”の戻り値を集合Ｇに代入する。その結果、Ｇ＝｛｛１,３,７｝｝となるため、ステップＮ２０３の条件を満たし、状態数削減処理部１０がステップＮ２０４の処理を実行することでｇ＝｛１,３,７｝となる。
【０２１３】
続くステップＮ２０５において、状態数削減処理部１０は、これまでと同様に探索部１２を用いｇ＝｛１,３,７｝について“ｓｅａｒｃｈ＿ｅｑｕｉｖ”を実行する。なお、ｇ＝｛１,３,７｝の場合、“ｓｅａｒｃｈ＿ｅｑｕｉｖ”のステップＮ２３５の条件を満たすことはなく、また、ステップＮ２４１の条件を満たすこともない。一方、ステップＮ２６８の条件を満たすため、探索部１２は、集合Ｇからｇ＝｛１,３,７｝が取り除かれ、集合Ｇは空集合φとなる（ステップＮ２６９）。
【０２１４】
そして、“ｓｅａｒｃｈ＿ｅｑｕｉｖ”の戻り値はＧ′＝（φ,φ）となり、“ｓｉｍｉｎ”のステップＮ２０５に再び戻る。ステップＮ２０５において、状態数削減処理部１０は“ｓｅａｒｃｈ＿ｅｑｕｉｖ”の戻り値を集合Ｇに代入する。その結果、Ｇ＝φであるため、ステップＮ２０３の条件を満たさなくなり、処理が終了する。以上の処理により、処理対象としたＤＦＡの状態数は最小化されることになる。
【０２１５】
次に、依存情報の付け替えが発生する場合の状態数削減処理部１０の動作について説明する。図２３は、ＤＦＡの一例を示した図である。記法は図１１と同じである。以下、図２３に示したＤＦＡを処理対象として説明を進める。
【０２１６】
まず、状態数削減処理部１０は、図２３に示した処理対象となるＤＦＡに対し、メインプログラム“ｓｉｍｉｎ”を実行していく。まず、ＤＦＡを構成する状態を分類すると、Ｇ＝｛｛１,２｝,｛３,４｝,｛５,６｝｝が得られる。図２４は、図２３に示したＤＦＡの状態分類後の構成を示した図である。ここで、破線で囲った部分が夫々の分類を表しており、状態１、２と、状態３、４と、状態５、６とが夫々１つの分類になっていることが分かる。
【０２１７】
ここではまず、｛１,２｝についてサブプログラム“ｓｅａｒｃｈ＿ｅｑｕｉｖ”が実行されたとする。ステップＮ２２１〜ステップＮ２２８までの処理で、γ＝｛（１,１）,（２,２）｝、ｇ＝｛１,２｝、Σg＝｛ａ｝、Ｓ＝｛｛（１,１）,（２,２）｝｝が得られる。続くステップＮ２２９の処理でσ＝ａとなり、ステップＮ２３１の処理でγn＝｛（３,１）,（４,２）｝となる。この集合γnはスタックＳには存在しないので、ステップＮ２３３〜ステップＮ２４８の処理が行われる。
【０２１８】
ステップＮ２３３〜ステップＮ２３７の処理のうちで、ステップＮ２３５の条件を満たすのは、γni＝｛（３,１）,（４,２）｝のみである。そのため、探索部１２は、この集合γniについてサブプログラム“ｓｅａｒｃｈ＿ｅｑｕｉｖ”を再帰的に実行する。この再帰処理時のステップＮ２２１〜ステップＮ２２８までの処理で、γ＝｛（３,１）,（４,２）｝、ｇ＝｛３,４｝、Σg＝｛ａ,ｂ｝、Ｓ＝｛｛（１,１）,（２,２）｝,｛（３,１）,（４,２）｝｝が得られる。
【０２１９】
続くステップＮ２２９からの処理について、まずσ＝ａとして処理をしていく。すると、ステップＮ２３１でγn＝｛（５,１）,（６,２）｝となる。この集合γnもスタックＳには存在しないので、ステップＮ２３３〜ステップＮ２４８の処理が行われる。
【０２２０】
ステップＮ２３３〜ステップＮ２３７の処理のうちで、ステップＮ２３５の条件を満たすのは、γni＝｛（５,１）,（６,２）｝のみである。そのため、探索部１２は、この集合γniについてサブプログラム“ｓｅａｒｃｈ＿ｅｑｕｉｖ”をさらに再帰的に実行する。この再帰処理時のステップＮ２２１〜ステップＮ２２８までの処理で、γ＝｛（５,１）,（６,２）｝、ｇ＝｛５,６｝、Σg＝｛ｂ｝、Ｓ＝｛｛（１,１）,（２,２）｝,｛（３,１）,（４,２）｝,｛（５,１）,（６,２）｝｝が得られる。
【０２２１】
続くステップＮ２２９からの処理は、σ＝ｂとして行われる。すると、ステップＮ２３１でγn＝｛（３,１）,（４,２）｝となる。この集合γnはスタックＳに存在するのでステップＮ２４９以降の処理が行われる。ステップＮ２５０でψsc＝｛（５,３）,（６,４）｝、ステップＮ２５１でΨsc＝｛（｛（５,３）,（６,４）｝,２）｝となる。ステップＮ２５２の条件は満たさないので、次はステップＮ２５４が処理される。
【０２２２】
ステップＮ２５４では、Ｙsc＝｛｛（｛（５,３）,（６,４）｝,２）｝｝、Ｈ＝｛｛｝｝となる。他に処理する入力記号は集合Σgに含まれていないので、次はステップＮ２５５が処理されることになる。集合Ｈには空の集合が一つ含まれるのみであるため、ステップＮ２５５の処理結果はＧshare＝φとなる。したがって、ステップＮ２５６で一つにまとめられる状態はなく、ｇerase＝φとなる。また、ｇerase＝φであるため、ステップＮ２５７の処理で集合Ｙscに変化は生じない。
【０２２３】
続くステップＮ２５８では、Ψsc＝｛（｛（５,３）,（６,４）｝,２）｝となる。今、｜Ｓ｜＝３であるため、ステップＮ２５９で集合Ψscに変化は生じない。また、ステップＮ２６０とＮ２６１との処理で、Ｄ［２］＝｛｛（５,３）,（６,４）｝｝となる。Ｄ［３］＝φであるので、ステップＮ２６４とＮ２６５の処理が実行されることはない。また、ステップＮ２６６の実行でＤ［３］が変化することはなく、空集合φのままである。
【０２２４】
ステップＮ２６７でスタックＳの一番上の要素が取り除かれ、Ｓ＝｛｛（１,１）,（２,２）｝,｛（３,１）,（４,２）｝｝となる。集合Ψscは空集合ではないのでステップＮ２６８の条件は満たされず、ステップＮ２６９の処理が実行されることはない。また、集合ｇeraseは空集合であるので、ステップＮ２７０ではＧ′＝｛｛１,２｝,｛３,４｝,｛５,６｝｝が得られる。そして、ステップＮ２７１で戻り値として集合Ｇ′と集合Ψscとが返る。
【０２２５】
ステップＮ２３６に戻ってくるので、得られた戻り値によりＧ＝｛｛１,２｝,｛３,４｝,｛５,６｝｝、Ψnsct＝｛（｛（５,３）,（６,４）｝,２）｝となる。また、ステップＮ２３７でΨnsc＝｛（｛（５,３）,（６,４）｝,２）｝となり、ステップＮ２３８でｇn＝｛５,６｝となる。
【０２２６】
ステップＮ２３９〜Ｎ２４３の処理では、ステップＮ２４１の条件が満たされることがないので、ステップＮ２４２とＮ２４３の処理が行われることはない。集合Ψnscには要素が一つ含まれているので、ステップＮ２４４でψnsc＝｛（５,３）,（６,４）｝、ｘlevel＝２となり、これについてステップＮ２４５〜Ｎ２４８の処理が行われる。
【０２２７】
ステップＮ２４５の処理では、ψsc＝｛（３,３）,（４,４）｝となる。｜Ｓ｜＝２であるため、ステップＮ２４６の条件を満たし、ステップＮ２４７でη＝｛｛３,４｝｝となる。ステップＮ２４８では、Ψsc＝｛（｛（３,３）,（４,４）｝,２）｝となる。また、ステップＮ２５４では、Ｙsc＝｛｛（｛（３,３）,（４,４）｝,２）｝｝、Ｈ＝｛｛｛３,４｝｝｝となる。
【０２２８】
Σg＝｛ａ,ｂ｝のうち、ａについては処理が終わったので、次はσ＝ｂとしてステップＮ２３０〜Ｎ２５４までの処理を行う。ステップＮ２３１でγn＝｛（１,１）,（２,２）｝となる。このとき、スタックＳに集合γnは存在するので、ステップＮ２３２の条件は満たされず、ステップＮ２５０からの処理が実行される。
【０２２９】
ステップＮ２５０では、ψsc＝｛（３,１）,（４,２）｝となる。また、ステップＮ２５１では、Ψsc＝｛（｛（３,１）,（４,２）｝,１）｝となる。ステップＮ２５２の条件は満たさないので、ステップＮ２５３は実行されない。続くステップＮ２５４で、Ｙsc＝｛｛（｛（３,３）,（４,４）｝,２）｝,｛（｛（３,１）,（４,２）},１｝）、Ｈ＝｛｛｛３,４｝｝,｛｝｝となる。
【０２３０】
集合Σgに含まれる全ての入力記号について処理が完了したので、次はステップＮ２５５が実行される。ステップＮ２５５では、Ｇshare＝φとなる。そのため、ステップＮ２５６でまとめられる状態はなく、ｇerase＝φとなる。ｇerase＝φであるため、ステップＮ２５７で集合Ｙscに変化が生じることはない。
【０２３１】
続くステップＮ２５８では、まず集合Ｙscから要素が一つ選択される。ここでは、Ψ＝｛（｛（３,３）,（４,４）｝,２）が選択されたとする。そして、探索部１２は、ψ＝｛（３,３）,（４,４）｝、ｘlevel＝２、Ｙsc＼｛Ψ｝＝｛｛（｛（３,１）,（４,２）｝,１）｝｝を夫々第１、第２、第３引数として、区別不可能候補集合生成部１２４を用いて“ｓｅａｒｃｈ＿ｓｈａｒａｂｌｅ＿ｓｔａｔｅ＿ｃａｎｄｉｄａｔｅ”を実行する。
【０２３２】
“ｓｅａｒｃｈ＿ｓｈａｒａｂｌｅ＿ｓｔａｔｅ＿ｃａｎｄｉｄａｔｅ”では、ステップＮ３２１の条件を満たさないため、ステップＮ３２２の処理は実行されず、続くステップＮ３２３で集合Ｙから要素が一つ選択される。今、集合Ｙの要素は一つしかない。したがって、Ψ＝｛（｛（３,１）,（４,２）｝,１）｝となる。集合Ψのサイズは１であるため、ステップＮ３２５ではψ＝｛（３,１）,（４,２）｝、ｘlevel＝１となる。また、ｘstart＝２であるため、ステップＮ３２６の条件は満たされない。したがって、ステップＮ３２９の処理が実行される。このとき、ψstart＝｛（３,３）,（４,４）｝であるので、ψis＝｛（３,１）,（４,２）｝となる。
【０２３３】
また、｜ψis｜＝２であるため、ステップＮ３３１の処理が実行され、ｘis＝１となる。ステップＮ３３２で、“ｓｅａｒｃｈ＿ｓｈａｒａｂｌｅ＿ｓｔａｔｅ＿ｃａｎｄｉｄａｔｅ”が引数ψis＝｛（３,１）,（４,２）｝、ｘis＝１、Ｙ＼｛Ψ｝＝φで再帰的に実行される。すると、ステップＮ３２１の条件を満たすので、ステップＮ３２２で戻り値を｛（｛（３,１）,（４,２）｝,１）｝としてステップＮ３３２へと処理が移行する。その結果、Ψs＝｛（｛（３,１）,（４,２）｝,１）｝となる。他に処理する集合Ψの要素はないので、ステップＮ３３３が実行され、集合Ψsを戻り値として“ｓｅａｒｃｈ＿ｅｑｕｉｖ”のステップＮ２５８の処理に戻る。
【０２３４】
ステップＮ２５８では、他に処理すべき集合Ψの要素はないので、Ψsc＝｛（｛（３,１）,（４,２）｝,１）｝となる。｜Ｓ｜＝２であるため、ステップＮ２５９の処理では集合Ψscは変化しない。また、ステップＮ２６０とＮ２６１とにより、Ｄ［１］＝｛｛（３,１）,（４,２）｝｝となる。
【０２３５】
次に、ステップＮ２６２〜Ｎ２６５の処理が実行される。これらの処理によって、Ｄ［２］に記録されている依存関係の依存先状態が変更されることになる。Ψsc＝｛（｛（３,１）,（４,２）｝,１）｝であるので、ステップＮ２６２でψsc＝｛（３,１）,（４,２）｝、ｘlevel＝１となる。また、ステップＮ２６３でｄ＝｛（５,３）,（６,４）｝となり、ステップＮ２６４では、ｄp＝｛（５,１）,（６,２）｝となる。
【０２３６】
ここで、ｄに含まれる２つ組（５,３）を例に説明する。２つ組（５,３）は依存元状態が状態５、依存先状態が状態３である。この状態３を依存元状態とするψscの要素は（３,１）である。この２つ組の依存先状態は状態１である。したがって、ｄに含まれる２つ組（５,３）の依存先状態は状態１となり、ｄpに２つ組（５,１）が記録される。また、ｄpの残りの２つ組（６,２）についても同様である。
【０２３７】
続くステップＮ２６５では、Ｄ［１］＝｛｛（３,１）,（４,２）｝,｛（５,１）,（６,２）｝｝となる。他に処理すべき集合ΨscやＤ［２］の要素はないので、ステップＮ２６６が実行され、Ｄ［２］＝φとなる。また、ステップＮ２６７の処理により、Ｓ＝｛｛（１,１）,（２,２）｝｝となる。
【０２３８】
集合Ψscは空集合ではないので、ステップＮ２６８の条件を満たさず、ステップＮ２６９の処理は実行されない。また、削除された状態もないので、ステップＮ２７０の結果、Ｇ′＝｛｛１,２｝,｛３,４｝,｛５,６｝｝となる。続くステップＮ２７１では、戻り値として集合Ｇ′と集合Ψscとが返る。そして、ステップＮ２３６の処理に再び戻るので、得られた戻り値によりＧ＝｛｛１,２｝,｛３,４｝,｛５,６｝｝、Ψnsct＝｛（｛（３,１）,（４,２）｝,１）｝となる。
【０２３９】
次いで、ステップＮ２３７で、Ψnsc＝｛（｛（３,１）,（４,２）｝,１）｝となり、ステップＮ２３８で、ｇn＝｛３,４｝となる。また、ステップＮ２３９〜Ｎ２４３の処理では、ステップＮ２４１の条件を満たすことはないので、ステップＮ２４２とＮ２４３とが実行されることはない。
【０２４０】
集合Ψnscには要素が一つあるので、ステップＮ２４４〜Ｎ２４８の処理が行われる。ステップＮ２４５の処理により、ψsc＝｛（１,１）,（２,２）｝となる。今、ｘlevel＝１かつ｜Ｓ｜＝１であるため、ステップＮ２４６の条件を満たし、ステップＮ２４７でη＝｛｛１,２｝｝となる。ステップＮ２４８でΨsc＝｛（｛（１,１）,（２,２）｝,１）となる。また、ステップＮ２５４でＹsc＝｛｛（｛（１,１）,（２,２）｝,１）｝｝、Ｈ＝｛｛｛１,２｝｝｝となる。他に処理する集合Σgの要素は残っていないため、処理をステップＮ２５５へと移す。
【０２４１】
ステップＮ２５５が実行されることでＧshare＝｛｛１,２｝｝となる。続くステップＮ２５６で、探索部１２は、状態併合部１２１を用いてサブプログラム“ｍｅｒｇｅ＿ｓｔａｔｅｓ”を実行する。このとき、Ｇshare＝｛｛１,２｝｝、Ｄelm＝｛｛（３,１）,（４,２）｝,｛（５,１）,（６,２）｝｝である。
【０２４２】
“ｍｅｒｇｅ＿ｓｔａｔｅｓ”では、集合Ｇshareに一つ要素があるので、それがステップＮ３０２で選択されると、ｇs＝｛１,２｝となる。そしてステップＮ３０３〜Ｎ３１３までの処理が行われる。ステップＮ３０３では、集合ｇsに含まれる状態が一つ選択される。ここではｒ＝１が選択されたとする。集合ｇsに含まれるｒ以外の状態は状態２のみなので、これをステップＮ３０５の処理で状態ｒに併合する。不要になった状態２は、ステップＮ３０６でＱeに追加され、Ｑe＝｛２｝となる。
【０２４３】
また、Ｄelmのサイズが２なので、それぞれの要素についてステップＮ３０８〜Ｎ３１３の処理が実行される。ここではまず、ψ＝｛（３,１）,（４,２）｝から処理を行う。ステップＮ３０８でｇ＝｛３,４｝となるので、ステップＮ３０９の条件を満たす。そのため、続くステップＮ３１０で集合ｇから任意の要素が一つ選択される。ここではｒ′＝３とする。
【０２４４】
そして、ステップＮ３１２で、集合ｇからｒ′を除いた状態を、状態r′に併合する。このとき、ｑe＝４のみを考えればよいので、状態４は状態３へとまとめられることになる。続くステップＮ３１３では、Ｑe＝｛２,４｝となる。
【０２４５】
次にψ＝｛（５,１）,（６,２）｝として処理を行う。先ほどと同様に処理すると、ステップＮ３０８でｇ＝｛５,６｝となり、ステップＮ３１０でｒ′＝５とすると、ステップＮ３１２で状態６が状態５にまとめられる。また、ステップＮ３１３でＱe＝｛２,４,６｝となる。
【０２４６】
全ての集合ＧshareとＤelmについて処理が完了したので、ステップＮ３１４でＱeを戻り値として“ｓｅａｒｃｈ＿ｅｑｕｉｖ”のステップＮ２５６に戻る。これにより、ｇerase＝｛２,４,６｝となる。
【０２４７】
ステップＮ２５７で、集合ｇeraseに含まれる２つ組を集合Ｙscから取り除き、Ｙsc＝｛｛（｛（１,１）｝,１）｝となる。なお、状態を併合するには二つ以上の２つ組が必要なので、２つ組が一つしかない集合は不要であり、この時点で削除してしまってもよい。ステップＮ２５８でΨsc＝｛（｛（１,１）｝,１）｝となる。
【０２４８】
｜Ｓ｜＝１であるため、ステップＮ２５９でΨsc＝φとなる。したがって、ステップＮ２６０〜Ｎ２６５までの処理では何も変化しない。続くステップＮ２６６でＤ［１］＝φとし、ステップＮ２６７でＳ＝φとなる。集合Ψscは空集合φであるため、ステップＮ２６８の条件が満たされ、ステップＮ２６９の処理で集合Ｇから集合ｇに一致する要素が取り除かれる。今、ｇ＝｛１,２｝、Ｇ＝｛｛１,２｝,｛３,４｝,｛５,６｝｝であるので、Ｇ＝｛｛３,４｝,｛５,６｝｝となる。
【０２４９】
ステップＮ２７０で、Ｇ＝｛｛３,４｝,｛５,６｝｝からｇerase＝｛２,４,６｝に含まれる状態を取り除く。すると。｛｛３｝,｛５｝｝となるが、各要素のサイズが１以下のものは含めないので、結局、Ｇ′＝φとなる。そのため、ステップＮ２７１での戻り値は（φ,φ）となる。
【０２５０】
“ｓｉｍｉｎ”のステップＮ２０５に戻ると、Ｇ＝φとなる。これでステップＮ２０３の条件を満たさなくなるので処理は終了する。図２５は、図２３に示したＤＦＡの状態併合後の最終的な構成を示した図である。以上の処理により、処理対象としたＤＦＡの状態数は最小化されることになる。
【０２５１】
以上のように、本実施形態によれば、区別可能な状態の組合せを状態の２つ組の集合として持つ必要がないので、大きな記憶域を使用することがなく、さらにＤＦＡを構成する状態を段階的に併合することで、漸進的に決定性有限状態オートマトンの状態数を減少させることができる。
【０２５２】
さらに、他の全ての状態と区別可能であると判明した状態は、その時点で集合Ｇから取り除かれることになるので、区別可能であると判断された状態に対して、再度区別可能であるか否かの判定が行われることがなくなり、処理の効率化を図ることができる。
【０２５３】
［第２の実施形態］
上述した第１の実施形態の構成では、１つの循環経路上にある状態数が増加すると、処理に時間がかかるようになる。具体的には、区別不可能候補である状態の集合が集合Ｇから除去されないため、既に区別不可能候補であると判明していても、その状態の集合に対して何度も“ｓｅａｒｃｈ＿ｅｑｕｉｖ”が実行されることになる。そこで、第２の実施形態では、区別不可能候補であると判明した状態の集合に対して、処理が繰り返し行われないよう構成した形態について説明する。なお、第１の実施形態と同様の構成要素については、同一の符号を付与し説明を省略する。
【０２５４】
図２６は、第２の実施形態に係る情報処理装置の機能的構成を示したブロック図である。同図に示したように、情報処理装置は、ＣＰＵ１とＲＯＭ４又は記憶部６に予め記憶された所定のプログラムとの協働により実現される機能部として、状態数削減処理部２０を備えている。
【０２５５】
状態数削減処理部２０は、状態分類部１１と探索部２１とを有し、上述したメインプログラム“ｓｉｍｉｎ”を実行することで、処理対象となるＤＦＡの状態数を漸進的に削減する。
【０２５６】
探索部２１は、図２６に示したように、状態併合部１２１と、遷移先集合生成部１２２と、区別不可能集合生成部１２３と、区別不可能候補集合生成部１２４と、実行状態判定部２１１とを有している。探索部２１は、上述したサブプログラム“ｓｅａｒｃｈ＿ｅｑｕｉｖ”に対応する、後述するサブプログラム“ｓｅａｒｃｈ＿ｅｑｕｉｖ２”を実行することで、処理対象のＤＦＡに含まれる区別不可能な状態同士を一つの状態に併合する。なお、実行状態判定部２１１は、後述するサブプログラム“ｆｉｎｄ＿ｓｒｃ＿ｉｎ＿Ｄ”により実現される機能部である。実行状態判定部２１１の動作については後述する。
【０２５７】
図２７は、サブプログラム“ｓｅａｒｃｈ＿ｅｑｕｉｖ２”の擬似コードの一例を示した図である。ここで、ステップＮ４０１〜Ｎ４１１の処理は、“ｓｅａｒｃｈ＿ｅｑｕｉｖ”でのステップＮ２２１〜Ｎ２３１と同様である。
【０２５８】
ステップＮ４１２において、探索部２１は、後述するステップＮ４１８〜Ｎ４２０の処理の実行状態を記録するためのｂfoundを“ｆａｌｓｅ”に設定する。続いて、探索部２１は、遷移先状態の集合γnのサイズが集合γのサイズと同じであるか否かを判定し（ステップＮ４１３）、同じであればステップＮ４１４〜Ｎ４２１の処理を行う。
【０２５９】
ステップＮ４１４では、探索部２１が、実行状態判定部２１１を用いてサブプログラム“ｆｉｎｄ＿ｓｒｃ＿ｉｎ＿Ｄ”を実行し、集合γnに含まれる状態が依存元状態となる依存関係をテーブルＤから取得する。なお、“ｆｉｎｄ＿ｓｒｃ＿ｉｎ＿Ｄ”については後述する。
【０２６０】
次いで、探索部２１は、集合γに含まれる状態の依存先状態を決定する（ステップＮ４１５）。具体的には、集合γに含まれる状態、つまり集合ｇに含まれる状態をｑ、ｑの入力記号σによる遷移先をｑs、ｑsの依存先状態をｑd とするとき、ｑの依存先状態をｑdとする。探索部２１は、集合ｇに含まれている状態に対してそれぞれｑdを求め、２つ組（ｑ,ｑd）の集合を生成し、それをψとする。
【０２６１】
続いて、探索部２１は、集合γとψを用いて集合γの各要素に対応する依存先状態の集合γdを生成する（ステップＮ４１６）。探索部２１は、集合γdがスタックＳに存在するか否かを判定し（ステップＮ４１７）、存在すると判定した場合、ステップＮ４１８〜Ｎ４２０の処理を実行する。
【０２６２】
ステップＮ４１８では、探索部２１がψとｘlevelとの２つ組を集合Ψscに追加する。続いて、探索部２１は、ｘlevelがスタックＳのサイズと等しいか否かを判定し（ステップＮ４１９）、等しいときのみステップＮ４２０の処理を実行する。ステップＮ４２０では、探索部２１が、ψに含まれる依存元状態から成る状態の集合を集合ηに追加する。そして、探索部２１は、ステップＮ４１８〜Ｎ４２０の処理を実行したので、ｂfoundを“ｔｒｕｅ”に設定する（ステップＮ４２１）。
【０２６３】
続くステップＮ４２２において、探索部２１は、ｂfoundが“ｆａｌｓｅ”か否かを判定し、“ｆａｌｓｅ”と判定した場合には、第１の実施形態で説明した“ｓｅａｒｃｈ＿ｅｑｕｉｖ”のステップＮ２３２〜Ｎ２５３と同様の処理を実行する（ステップＮ４２３）。なお、“ｓｅａｒｃｈ＿ｅｑｕｉｖ”のステップＮ２３６では、“ｓｅａｒｃｈ＿ｅｑｕｉｖ”を再帰的に実行しているが、本実施形態では、“ｓｅａｒｃｈ＿ｅｑｕｉｖ２”を実行するようにする。
【０２６４】
ステップＮ４２４は、第１の実施形態で説明した“ｓｅａｒｃｈ＿ｅｑｕｉｖ”のステップＮ２５４と同様の処理であり、探索部２１は、第１の実施形態１で説明したように処理する。
【０２６５】
ステップＮ４２５は、第１の実施形態で説明した“ｓｅａｒｃｈ＿ｅｑｕｉｖ”のステップＮ２５５〜Ｎ２６７と同様の処理であり、探索部２１は、第１の実施形態１で説明したように処理する。なお、ステップＮ４２５は、ステップＮ４０４の条件判定で、集合Σgが空集合φでなかった場合のみ実行される処理群である。
【０２６６】
ステップＮ４２６は、第１の実施形態で説明した“ｓｅａｒｃｈ＿ｅｑｕｉｖ”のステップＮ２６８〜Ｎ２７１と同様の処理であり、探索部２１は、第１の実施形態１で説明したように処理する。
【０２６７】
次に、図２８を参照して、ステップＮ４１４のサブプログラム“ｆｉｎｄ＿ｓｒｃ＿ｉｎ＿Ｄ”について説明する。ここで、図２８は、サブプログラム“ｆｉｎｄ＿ｓｒｃ＿ｉｎ＿Ｄ”の擬似コードの一例を示した図である。
【０２６８】
まず、実行状態判定部２１１は、集合γnから経路番号を取り除いた状態の集合をｇnとする（ステップＮ４３１）。続いて、実行状態判定部２１１は、ステップＮ４３２のｆｏｒｅａｃｈ文に従い、テーブルＤに含まれている要素（ｘlevel,ｙ）毎にステップＮ４３３〜Ｎ４３６の処理を実行する。
【０２６９】
ステップＮ４３３において、実行状態判定部２１１は、ｆｏｒｅａｃｈ文に従い、ｙに含まれる要素ψ毎にステップＮ４３４〜Ｎ４３６の処理を実行する。ステップＮ４３４では、実行状態判定部２１１が、ψの要素である（依存元状態，依存先状態）の２つ組のうち、依存元状態のみを取り出し、それらを状態の集合ｇsとする。続いて、実行状態判定部２１１は、集合ｇnと集合ｇsとが等しいか否かを判定し（ステップＮ４３５）、等しいと判定した場合、そのときのψとｘlevelとの２つ組を戻り値として、“ｓｅａｒｃｈ＿ｅｑｕｉｖ２”のステップＮ４１４に戻る（ステップＮ４３６）。
【０２７０】
一方、ステップＮ４３２とＮ４３３による全ての繰り返しでステップＮ４３５の条件を満たさなければ、ステップＮ４３７の処理が実行されることになる。この場合、実行状態判定部２１１は、空集合と零の２つ組（φ,０）を戻り値として、“ｓｅａｒｃｈ＿ｅｑｕｉｖ２”のステップＮ４１４に戻る（ステップＮ４３７）。
【０２７１】
上述した処理により、既に循環経路上にあると判明している状態に対して再度アルゴリズム“ｓｅａｒｃｈ＿ｅｑｕｉｖ２”を実行する必要がないので、循環経路上の状態が多数存在する場合には、第１の実施形態に比べてより少ない処理量で状態数削減処理を行うことが可能できる。また、状態数削減処理を中断せず、最後まで実行すると状態数最小のＤＦＡを得ることができる。
【０２７２】
［第３の実施形態］
ＤＦＡの場合には、終了状態が複数あっても出て行く遷移の入力記号の集合が同じであれば、終了状態同士を一つの状態に併合することができる。しかしながら、重み付き有限状態オートマトンのように終了状態に重みが割り当てられている場合、異なる重みが割り当てられている終了状態同士は区別可能であるので、一つにまとめてはならない。その理由は、一つにまとめてしまうと、得られる重みが変わってしまう可能性があるためである。
【０２７３】
そこで、第３の実施形態では、終了状態に種類がある場合、言い換えると終了状態に付加情報がある場合に適用することが可能な構成について説明する。なお、第１の実施形態と同様の構成要素については、同一の符号を付与し説明を省略する。
【０２７４】
図２９は、第３の実施形態に係る情報処理装置の機能的構成を示したブロック図である。同図に示したように、情報処理装置は、ＣＰＵ１とＲＯＭ４又は記憶部６に予め記憶された所定のプログラムとの協働により実現される機能部として、状態数削減処理部３０を備えている。
【０２７５】
状態分類部３１は、処理の対象となるＤＦＡに含まれる各状態を、その状態の終了性と、出て行く遷移に付随する入力記号の種別と、終了状態の付加情報とが同じ状態毎に分類する。ここで付加情報は、例えば、上述した重みであってもよいし、距離やコスト等の数値で表すことができるものであってもよい。さらに文字や記号、文字列、記号列等であってもよい。
【０２７６】
本実施形態では、付加情報が複数ある場合をも考慮する必要があるため、状態ｑ∈Ｆの付加情報の集合をρ（ｑ）と表す。そして状態ｑが終了状態である場合は、終了状態の付加情報が割り当てられ、終了状態でない場合は、ρ（ｑ）＝φとする。このρ（ｑ）を用いるように変更した“ｃｒｅａｔｅ＿ｃｌａｓｓ”の擬似コードを図３０に示す。
【０２７７】
図３０は、サブプログラム“ｃｒｅａｔｅ＿ｃｌａｓｓ”の擬似コードの一例を示した図である。
【０２７８】
まず、状態分類部３１は、戻り値に使用する状態の集合を要素とする集合Ｇを空集合φで初期化するとともに、出て行く遷移の入力記号の集合と付加情報とから構成される２つ組に、状態の集合を関連付けて記憶するためのテーブルＣを空集合φで初期化する（ステップＮ５０１）。
【０２７９】
次いで、状態分類部３１は、ステップＮ５０２のｆｏｒｅａｃｈ文に従い、Ｑに含まれる各状態ｑについて、ステップＮ５０３とＮ５０４との処理を実行する。ステップＮ５０３では、状態分類部３１が、ｑから出て行く遷移に付随する入力記号の集合を生成し、集合Σqに代入する（ステップＮ５０３）。そして、状態分類部３１は、集合Σqと付加情報の集合ρ（ｐ）との２つ組に関連付けてテーブルＣに記憶されている状態の集合にｑを追加する（ステップＮ５０４）。
【０２８０】
続いて、状態分類部３１は、ステップＮ５０５のｆｏｒｅａｃｈ文に従い、テーブルＣに含まれる各要素に対して、ステップＮ５０６とＮ５０７との処理を実行する。ここで、状態分類部３１は、出て行く遷移の入力記号の集合と付加情報の集合との２つ組に関連付けられている状態の集合ｇのみを、ステップＮ５０６とＮ５０７との処理で使用する。
【０２８１】
ステップＮ５０６において、状態分類部３１は、集合ｇのサイズが２以上であるか否かを判定し、２以上と判定した場合、集合Ｇに集合ｇを追加する（ステップＮ５０７）。最後に、状態分類部３１は、この“ｃｒｅａｔｅ＿ｃｌａｓｓ”での処理結果として集合Ｇを返し、メインプログラム“ｓｉｍｉｎ”のステップＮ２０２に戻る。
【０２８２】
以下、図３１〜３３を参照し、本実施形態での状態数削減処理部３０の動作について説明する。図３１は、ＤＦＡの一例を示した図である。同図において各遷移に割り当てられている入力記号を“／”の左側に表し、重みを右側に表している。また、終了状態の“／”の左側に状態番号を表し、右側に終了状態の重みを表している。各状態の付加情報の集合は、ρ（０）＝φ、ρ（１）＝φ、ρ（２）＝φ、ρ（３）＝φ、ρ（４）＝｛１｝、ρ（５）＝｛１｝、ρ（６）＝｛２｝となる。
【０２８３】
図３１に示した重み付きＤＦＡに、入力記号列ｂａを入力すると、状態０、２、５と遷移するため、遷移に割り当てられている重みは３と２となり、終了状態の重みは１となる。重みを加算する場合には、３＋２＋１＝６となり、入力記号列ｂａをこの重み付きＤＦＡに入力すると、重み６が得られることになる。
【０２８４】
本実施形態での状態数最小化処理は、遷移に割り当てられている入力記号と重みとの組を、一つ入力記号とみなして処理を行うことになる。例えば、状態０から状態１への遷移に割り当てられている入力記号ならば、ａ／１を一つの入力記号とするということである。
【０２８５】
以下、本実施形態の状態数削減方法を用いて、図３１のＤＦＡの状態数を削減していく。まず、メインプログラム“ｓｉｍｉｎ”では、図３０で説明したサブプログラム“ｃｒｅａｔｅ＿ｃｌａｓｓ”が実行される。すると、Ｇ＝｛｛１,２,３｝,｛４,５｝｝となる。この状態を図示すると、図３２のようになる。ここで、図３２は、図３１に示したＤＦＡの状態分類後の構成を示した図である。ここで、破線で囲った部分が夫々の分類を表しており、状態１、２、３と、状態４、５とが夫々１つの分類になっていることが分かる。
【０２８６】
メインプログラム“ｓｉｍｉｎ”の残りの処理は、第１の実施形態と同様にすればよく、状態４と状態５とが一つにまとめられるとともに、状態１と状態２とが一つにまとめられることになる。その結果、図３１のＤＦＡは図３３のようになる。ここで、図３３は、図３１に示したＤＦＡの状態削減後の構成を示した図である。
【０２８７】
図３３からも明らかなように、最小化後のＤＦＡに入力記号列ｂａを入力すると、状態０、１、４と遷移し、その重みは３＋２＋１で計６となり、最小化前と同じ重みが得られることがわかる。
【０２８８】
以上のように、第３の実施形態によれば、重み付き有限状態オートマトンのように終了状態に種類が付加されている場合であっても、終了状態の種類が異なる状態は一つに併合しないようにしつつ、状態数を漸進的に削減することができる。
【０２８９】
［第４の実施形態］
第４の実施形態では、循環経路が存在しないＤＦＡ（非循環決定性有限オートマトン）を処理対象とした場合の形態について説明する。なお、第１の実施形態と同様の構成要素については、同一の符号を付与し説明を省略する。
【０２９０】
図３４は、第４の実施形態に係る情報処理装置の機能的構成を示したブロック図である。同図に示したように、本実施形態に係る情報処理装置は、ＣＰＵ１とＲＯＭ４又は記憶部６に予め記憶された所定のプログラムとの協働により実現される機能部として、状態数削減処理部４０を備えている。
【０２９１】
状態数削減処理部４０は、状態分類部１１と探索部４１とを有し、後述するメインプログラム“ｓｉｍｉｎ＿ａｃ”を実行することで、処理対象となる非循環決定性有限オートマトンの状態数を漸進的に削減する。ここで「非循環決定性有限オートマトン」とは、循環経路が存在しないＤＦＡのことを意味する。また。「循環経路が存在しない」とは、全ての状態ｑ∈Ｑに対して、δ（ｑ,ｗ）＝ｑを満たすような入力記号列ｗ∈Σ*＼｛ε｝が存在しないことをいう。なお、ｗ∈Σ*＼｛ε｝であるため、ｗに空入力記号列は含まれない。
【０２９２】
探索部４１は、図３４に示したように、状態併合部４１１と、遷移先集合生成部１２２と、区別不可能集合生成部１２３とを有している。探索部４１は、上述したサブプログラム“ｓｅａｒｃｈ＿ｅｑｕｉｖ”に対応する、後述するサブプログラム“ｓｅａｒｃｈ＿ｅｑｕｉｖ＿ａｃ”を実行することで、処理対象の非循環決定性有限オートマトンに含まれる区別不可能な状態同士を一つの状態に併合する。
【０２９３】
状態併合部４１１は、後述するサブプログラム“ｍｅｒｇｅ＿ｓｔａｔｅｓ＿ａｃ”により実現される機能部である。状態併合部４１１の動作については後述する。
【０２９４】
なお、本実施形態で処理の対象とする非循環決定性有限オートマトンには、循環経路が存在しないため、循環経路に関する処理は不要である。そのため、後述する“ｓｉｍｉｎ＿ａｃ”、“ｓｅａｒｃｈ＿ｅｑｕｉｖ＿ａｃ”及び“ｍｅｒｇｅ＿ｓｔａｔｅｓ＿ａｃ”は、第１の実施形態で説明した“ｓｉｍｉｎ”、“ｓｅａｒｃｈ＿ｅｑｕｉｖ”及び“ｍｅｒｇｅ＿ｓｔａｔｅｓ”から、循環経路に関する処理を除いたものとなっている。以下、順次説明する。
【０２９５】
図３５は、状態数削減処理部４０が実行するメインプログラム“ｓｉｍｉｎ＿ａｃ”の擬似コードの一例を示した図である。まず、状態数削減処理部４０は、第１の実施形態と同様、状態分類部１１を用いて、終了性と出て行く遷移の入力記号とで、処理対象の非循環決定性有限オートマトンに含まれる各状態を分類し、その結果を集合Ｇに代入する（ステップＮ６０１）。
【０２９６】
次いで、状態数削減処理部４０は、集合Ｇが空集合φになるまでステップＮ６０３、Ｎ６０４の処理を繰り返し実行する（ステップＮ６０２）。ステップＮ６０３では、状態数削減処理部４０が、集合Ｇから任意の要素を一つ選択し、それを集合ｇとする。なお、要素の選択順序は特に問わず、例えば集合ｇのサイズが小さいものから選択してもよいし、大きいものから選択してもよい。
【０２９７】
続くステップＮ６０４において、状態数削減処理部４０は、第１引数を集合ｇ、第２引数を集合Ｇとし、探索部１２を用いて、サブプログラム“ｓｅａｒｃｈ＿ｅｑｕｉｖ＿ａｃ”を実行する。サブプログラム“ｓｅａｒｃｈ＿ｅｑｕｉｖ＿ａｃ”の戻り値は、状態の集合の集合であり、状態数削減処理部４０は、この戻り値を集合Ｇに代入する。なお、第１の実施形態とは異なり、本実施形態ではスタックＳは不要である。また、経路番号も不要であるため、“ａｄｄ＿ｐａｔｈ＿ｉｎｄｅｘ”は使用する必要がない。
【０２９８】
次に、図３６を参照して、ステップＮ６０４で実行されるサブプログラム“ｓｅａｒｃｈ＿ｅｑｕｉｖ＿ａｃ”について説明する。図３６は、サブプログラム“ｓｅａｒｃｈ＿ｅｑｕｉｖ＿ａｃ”の擬似コードの一例を示した図である。
【０２９９】
まず、探索部４１は、集合ｇに含まれる状態から出て行く遷移に付随している入力記号を全て集め、それを集合Σgに代入する（ステップＮ６１１）。次いで、探索部４１は、集合Σgが空集合φであるか否かを判定し（ステップＮ６１２）、空集合φであればステップＮ６１３の処理を実行する。また、集合Σgが空集合φでないと判定した場合、探索部４１は、ステップＮ６１４以降の処理を実行する。
【０３００】
ステップＮ６１３において、探索部４１は、状態併合部４１１を用いてサブプログラム“ｍｅｒｇｅ＿ｓｔａｔｅｓ＿ａｃ”を実行することで、集合ｇに含まれる状態を一つの状態へと併合し、併合することで不要になった状態を集合ｇeraseへと代入する。なお、サブプログラム“ｍｅｒｇｅ＿ｓｔａｔｅｓ＿ａｃ”については後述する。
【０３０１】
一方、ステップＮ６１５では、探索部４１が、後の処理で使用する集合Ｈを空集合φとする。続いて、探索部４１は、ステップＮ６１６のｆｏｒｅａｃｈ文に従い、集合Σgに含まれる各入力記号に対して、ステップＮ６１７〜Ｎ６２８までの処理を実行する。
【０３０２】
ステップＮ６１７では、探索部４１が、状態の集合を要素とする集合ηを空集合φとする。次いで、探索部４１は、集合ｇに含まれる状態からの入力記号σによる遷移先状態の集合ｇnを取得する。つまり、ｇn＝δ（ｇ,σ）となる。
【０３０３】
続いて、探索部４１は、ステップＮ６１９のｆｏｒｅａｃｈ文に従い、集合Ｇの各要素に対して、ステップＮ６２０〜Ｎ６２２の処理を実行する。探索部４１は、ステップＮ６２０において、集合Ｇの要素ｇ′と集合ｇnとの積集合ｇniを算出し、この集合ｇniのサイズが２以上のときのみ、再帰的にサブプログラム“ｓｅａｒｃｈ＿ｅｑｕｉｖ＿ａｃ”を実行する（ステップＮ６２２）。なお、このときの第１引数には集合ｇniが、第２引数には集合Ｇが渡される。また、再帰処理から戻ってくると、探索部４１は、その戻り値を集合Ｇとする。
【０３０４】
サブプログラム“ｓｅａｒｃｈ＿ｅｑｕｉｖ＿ａｃ”の再帰処理中に状態がまとめられる可能性があるので、探索部４１は、ステップＮ６１８と同様にステップＮ６２３で集合ｇnを更新する。なお、ステップＮ６２２が実行されていない場合には、ステップＮ６２３を実行する必要はない。
【０３０５】
続いて、探索部４１は、ステップＮ６２４のｆｏｒｅａｃｈ文に従い、集合ｇnに含まれる各状態ｑn対して、ステップＮ６２５〜Ｎ６２７の処理を実行することで、入力記号σを伴う遷移に関して区別不可能な状態を見つける。
【０３０６】
探索部４１は、入力記号σでｑnへと遷移するような集合ｇに含まれる状態の集合を求め、それを集合ｇsとする（ステップＮ６２５）。次いで、探索部４１は、集合ｇsのサイズが２以上か否かを判定し（ステップＮ６２６）、集合ｇsに２以上の状態が含まれていると判定した場合、それを集合ηへと追加する（ステップＮ６２７）。
【０３０７】
集合ｇnに含まれる全ての状態に対し、ステップＮ６２５〜Ｎ６２７の処理が完了すると、探索部４１は、そのときの集合ηを集合Ｈに追加する（ステップＮ６２８）。また、集合Σgに含まれる全ての入力記号に対し、ステップＮ６１７〜Ｎ６２８の処理が完了すると、探索部４１は、区別不可能集合生成部１２３を用いてサブプログラム“ｓｅａｒｃｈ＿ｓｈａｒａｂｌｅ＿ｓｔａｔｅ”を実行することで、区別不可能な状態の集合を求め、それを集合Ｇshareとする（ステップＮ６２９）。
【０３０８】
続いて、探索部４１は、状態併合部４１１を用いて後述するサブプログラム“ｍｅｒｇｅ＿ｓｔａｔｅｓ＿ａｃ”を実行することで、区別不可能な状態を一つにまとめ、その結果不要になった状態を集合ｇeraseとする（ステップＮ６３０）。
【０３０９】
続くステップＮ６３１では、探索部４１が、次の２つの条件を満たす集合Ｇ′を集合Ｇから生成する。条件１：集合ｇに一致する集合Ｇの要素は集合Ｇ′には含めない。条件２：不要になった集合ｇeraseに含まれる状態を集合Ｇの要素から取り除き、その結果、要素のサイズが２以上になる要素のみを集合Ｇ′に含める。
【０３１０】
そして、探索部４１は、ステップＮ６３１で得られた集合Ｇ′を戻り値として、ステップＮ６０４の処理に返し、“ｓｅａｒｃｈ＿ｅｑｕｉｖ＿ａｃ”の処理を終了する。
【０３１１】
次に、図３７を参照して、ステップＮ６１３やステップＮ６３０で実行されるサブプログラム“ｍｅｒｇｅ＿ｓｔａｔｅｓ＿ａｃ”について説明する。図３７は、サブプログラム“ｍｅｒｇｅ＿ｓｔａｔｅｓ＿ａｃ”の擬似コードの一例を示した図である。
【０３１２】
まず、状態併合部４１１は、不要になった状態を記憶するためのＱeを空集合φにする（ステップＮ６４１）。続いて、状態併合部４１１は、ステップＮ６４２のｆｏｒｅａｃｈ文に従い、集合Ｇshareの各要素ｇsに対して、ステップＮ６４３〜Ｎ６４６の処理を実行する。
【０３１３】
状態併合部４１１は、ステップＮ６４３において、集合ｇsから一つの状態に併合する際に残留させる状態を代表状態ｒとして選択する。なお、選択する状態は特に問わず、例えば状態番号が最小の状態を残すように選択してもよい。
【０３１４】
続いて、状態併合部４１１は、ステップＮ６４４のｆｏｒｅａｃｈ文に従い、集合ｇsからステップＮ６４３で選択したｒを除いた各状態ｑeに対して、ステップＮ６４５、Ｎ６４６の処理を実行する。
【０３１５】
状態併合部４１１は、ステップＮ６４５において、ステップＮ６４３で選択したｒと、ｑeとを併合すると、続くステップＮ６４６において、この併合により不要となった状態ｑeをＱeに追加する。
【０３１６】
そして、集合Ｇshareの全ての要素についてステップＮ６４３〜Ｎ６４６の処理が完了すると、状態併合部４１１は、不要になった状態の集合Ｑeを戻り値として、呼び出し元へ処理を返し（ステップＮ６４７）、“ｍｅｒｇｅ＿ｓｔａｔｅｓ＿ａｃ”の処理を終了する。
【０３１７】
上記した処理で、非循環決定性有限状態オートマトンの状態数削減処理が完了することになる。このように、本実施形態によれば、循環経路のための処理を含まないため、非循環決定性有限状態オートマトンの状態数を、第１の実施形態より効率的に削減することができる。
【０３１８】
なお、第３の実施形態で説明した、終了状態に種類があるＤＦＡについても、そのＤＦＡに循環経路が存在しない場合には、本実施形態の構成を適用することができる。具体的には、メインプログラム“ｓｉｍｉｎ＿ａｃ”のステップＮ６０１で実行するサブプログラム“ｃｒｅａｔｅ＿ｃｌａｓｓ”を第３の実施形態説明したものと置き換えればよい。
【０３１９】
［第５の実施形態］
第５の実施形態では、ＤＦＡの状態数削減を任意の時点で中断することが可能な構成について説明する。なお、第１の実施形態と同様の構成要素については、同一の符号を付与し説明を省略する。
【０３２０】
図３８は、第５の実施形態に係る情報処理装置の機能的構成を示したブロック図である。同図に示したように、情報処理装置は、ＣＰＵ１とＲＯＭ４又は記憶部６に予め記憶された所定のプログラムとの協働により実現される機能部として、状態数削減処理部５０を備えている。
【０３２１】
状態数削減処理部５０は、状態分類部１１と探索部１２とを有し、上述したメインプログラム“ｓｉｍｉｎ”を実行することで、処理対象となるＤＦＡの状態数を漸進的に削減する。
【０３２２】
また、状態数削減処理部５０は、自己が実行するメインプログラム“ｓｉｍｉｎ”の実行状態を監視し、操作部２等を介して状態数削減処理の中断を受け付けた場合に、現在実行中の箇所が中断可能な箇所か否かを判定し、中断可能な箇所を実行中であれば状態数削減処理を中断する。ここで「中断可能な箇所」とは、状態数削減処理を中断した場合に、この中断が行われた時点でのＤＦＡを得ることが可能なステップ位置を意味する。
【０３２３】
具体的に、状態数削減処理部５０は、サブプログラム“ｍｅｒｇｅ＿ｓｔａｔｅｓ”のステップＮ３０４〜Ｎ３１３、又は、サブプログラム“ｍｅｒｇｅ”の実行時に、中断不可能な箇所と判定する。この場合、状態数削減処理部５０は、中断可能な箇所まで処理を継続し、この中断可能な箇所まで到達すると処理を中断し、そのときのＤＦＡを記憶部６に記録する。なお、上述した中断不可能な箇所以外では、どこで処理を中断しても、この中断が行われた時点でのＤＦＡを得ることが可能である。
【０３２４】
次に、図３９を参照して状態数削減処理部５０の動作について説明する。ここで、図３９は、状態数削減処理部５０が実行する中断制御処理の手順を示したフローチャートである。なお、本中断制御処理は、上述した状態数削減処理とは独立的に実行され、操作部２等を介して入力された状態数削減処理の中断指示による割り込み発生時に実行される処理である。
【０３２５】
操作部２等を介しユーザから記憶部６に記憶されているＤＦＡの状態数削減が指示されると、状態数削減処理部５０は、メインプログラム“ｓｉｍｉｎ”から始まる一連のプログラムを第１の実施形態で説明したように実行する。
【０３２６】
状態数削減処理部５０は、一連のプログラムが実行されている最中に、操作部２等を介して処理の中断指示を受け付けると（ステップＮ７０２）、現在実行している箇所が中断可能な箇所か否かを判定する（ステップＮ７０３）。ここで、中断可能な箇所を実行中と判定すると（ステップＮ７０３；Ｙｅｓ）、状態数削減処理部５０は直ちに処理を中断し（ステップＮ７０５）、ステップＮ７０６の処理に移行する。
【０３２７】
一方、ステップＮ７０３において、中断不可能な箇所を実行中と判定した場合（ステップＮ７０３；Ｎｏ）、状態数削減処理部５０は、中断可能な箇所まで処理を継続し（ステップＮ７０４）、中断可能な箇所まで到達した時点で処理を中断する（ステップＮ７０５）。
【０３２８】
続くステップＮ７０６において、状態数削減処理部５０は、処理を中断した時点でのＤＦＡを記憶部６に記録し（ステップＮ７０６）、本処理を終了する。
【０３２９】
以上のように、第５の実施形態によれば、状態数削減処理を任意のタイミングで中断でき、そのときまでに削減できた状態数のＤＦＡを得ることができるため、状態数の削減に時間制約があり、その制約のために最小化が完了できない場合においても、元の状態数より状態数を減少させたＤＦＡを得ることができる。
【０３３０】
なお、第２、第３の実施形態に対しても本実施形態と同様の構成を適用することにより、状態数削減処理を任意のタイミングで中断することができる。また、第４の実施形態に対しても本実施形態と同様の構成を適用することにより、状態数削減処理を任意のタイミングで中断することができる。ただし、中断不可能な箇所は、サブプログラム“ｍｅｒｇｅ＿ｓｔａｔｅｓ＿ａｃ”のステップＮ６４４〜Ｎ６４６、サブプログラム“ｍｅｒｇｅ”となる。
【０３３１】
また、本実施形態では、操作部２を介して入力される指示信号に応じて、状態数削減処理を中断する態様としたが、これに限らないものとする。例えば、図４０に示したように、情報処理装置に時間計時を行うタイマ部８を設け、このタイマ部からの信号に応じて、状態数削減処理を中断する態様としてもよい。ここで、図４０は、情報処理装置の他のハードウェア構成例を示したブロック図である。
【０３３２】
図４０の構成の場合、状態数削減処理を開始する前に処理時間の上限値をユーザが操作部２を通して指示し、それをタイマ部８に設定しておく。そして、ユーザがＤＦＡの状態数削減処理を指示すると、状態数削減処理部５０が、メインプログラム“ｓｉｍｉｎ”から始まる一連のプログラムの実行を開始するとともに、タイマ部８が計時を開始する。このとき、状態数削減処理が完了する前に設定時間を経過した旨の信号が、タイマ部８から状態数削減処理部５０に伝えられると、状態数削減処理部５０は、上述した中断制御処理を開始し、状態数削減処理を中断することになる。
【０３３３】
以上、本発明に係る実施形態について説明したが、これに限定されるものではなく、本発明の主旨を逸脱しない範囲での種々の変更、置換、追加などが可能である。
【０３３４】
例えば、上記した各実施形態の処理にかかるプログラムを、コンピュータで読み取り可能な記憶媒体に格納して提供することも可能である。記憶媒体としては、磁気ディスク、光ディスク（ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＤＶＤ等）、光磁気ディスク（ＭＯ等）、半導体メモリ等、プログラムを記憶でき、且つ、コンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であってもよい。
【０３３５】
また、上記した各実施形態の処理にかかるプログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成しても良い。
【図面の簡単な説明】
【０３３６】
【図１】第１の実施形態に係る情報処理装置のハードウェア構成の一例を示したブロック図である。
【図２】図１に示した情報処理装置の機能的構成を示したブロック図である。
【図３】状態数削減処理の概要を示したフローチャートである。
【図４】図３の示した状態数削減処理の擬似コードの一例を示した図である。
【図５】図４に示したサブプログラム“ｃｒｅａｔｅ＿ｃｌａｓｓ”の擬似コードの一例を示した図である。
【図６−１】図４に示したサブプログラム“ｓｅａｒｃｈ＿ｅｑｕｉｖ”の擬似コードの一例を示した図である。
【図６−２】図４に示したサブプログラム“ｓｅａｒｃｈ＿ｅｑｕｉｖ”の擬似コードの一例を示した図である。
【図７】図６−１に示したサブプログラム“ｎｅｘｔ＿ｇａｍｍａ”の擬似コードの一例を示した図である。
【図８】図６−２に示したサブプログラム“ｓｅａｒｃｈ＿ｓｈａｒａｂｌｅ＿ｓｔａｔｅ”の擬似コードの一例を示した図である。
【図９】図６−１、図６−２に示したサブプログラム“ｍｅｒｇｅ＿ｓｔａｔｅｓ”の擬似コードの一例を示した図である。
【図１０】図６−２に示したサブプログラム“ｓｅａｒｃｈ＿ｓｈａｒａｂｌｅ＿ｓｔａｔｅ＿ｃａｎｄｉｄａｔｅ”の擬似コードの一例を示した図である。
【図１１】ＤＦＡの一例を示した図であある。
【図１２】図１１に示したＤＦＡの状態分類後の構成を示した図である。
【図１３】スタックＳの状態を模式的に示した図である。
【図１４】図１１に示したＤＦＡの状態併合後の構成を示した図である。
【図１５】図１４に示したＤＦＡの状態併合後の構成を示した図である。
【図１６】ＤＦＡの一例を示した図である。
【図１７】図１６に示したＤＦＡの状態分類後の構成を示した図である。
【図１８】スタックＳの状態を模式的に示した図である。
【図１９】スタックＳの状態を模式的に示した図である。
【図２０】テーブルＤの状態を模式的に示した図である。
【図２１】図１６に示したＤＦＡの状態併合後の構成を示した図である。
【図２２】図２１に示したＤＦＡの状態併合後の構成を示した図である。
【図２３】ＤＦＡの一例を示した図である。
【図２４】図２３に示したＤＦＡの状態分類後の構成を示した図である。
【図２５】図２３に示したＤＦＡの状態併合後の最終的な構成を示した図である。
【図２６】第２の実施形態に係る情報処理装置の機能的構成を示したブロック図である。
【図２７】サブプログラム“ｓｅａｒｃｈ＿ｅｑｕｉｖ２”の擬似コードの一例を示した図である。
【図２８】図２７に示したサブプログラム“ｆｉｎｄ＿ｓｒｃ＿ｉｎ＿Ｄ”の擬似コードの一例を示した図である。
【図２９】第３の実施形態に係る情報処理装置の機能的構成を示したブロック図である。
【図３０】第３の実施形態に係るサブプログラム“ｃｒｅａｔｅ＿ｃｌａｓｓ”の擬似コードの一例を示した図である。
【図３１】重み付きＤＦＡの一例を示した図である。
【図３２】図３１に示した重み付きＤＦＡの状態分類後の構成を示した図である。
【図３３】図３１に示した重み付きＤＦＡの状態削減後の構成を示した図である。
【図３４】第４の実施形態に係る情報処理装置の機能的構成を示したブロック図である。
【図３５】図３４に示した状態数削減処理部４０が実行するメインプログラム“ｓｉｍｉｎ＿ａｃ”の擬似コードの一例を示した図である。
【図３６】図３５に示したサブプログラム“ｓｅａｒｃｈ＿ｅｑｕｉｖ＿ａｃ”の擬似コードの一例を示した図である。
【図３７】図３６に示したサブプログラム“ｍｅｒｇｅ＿ｓｔａｔｅｓ＿ａｃ”の擬似コードの一例を示した図である。
【図３８】第４の実施形態に係る情報処理装置の機能的構成を示したブロック図である。
【図３９】図３８に示した状態数削減処理部５０が実行する中断制御処理の手順を示したフローチャートである。
【図４０】情報処理装置の他のハードウェア構成例を示したブロック図である。
【符号の説明】
【０３３７】
１  ＣＰＵ
２  操作部
３  表示部
４  ＲＯＭ
５  ＲＡＭ
６  記憶部
７  バス
８  タイマ部
１０  状態数削減処理部
１１  状態分類部
１２  探索部
１２１  状態併合部
１２２  遷移先集合生成部
１２３  区別不可能集合生成部
１２４  区別不可能候補集合生成部
２０  状態数削減処理部
２１  探索部
２１１  実行状態判定部
３０  状態数削減処理部
３１  状態分類部
４０  状態数削減処理部
４１  探索部
４１１  状態併合部
５０  状態数削減処理部
【図１】
2010079723.tif 000003
【図２】
2010079723.tif 000004
【図３】
2010079723.tif 000005
【図４】
2010079723.tif 000006
【図５】
2010079723.tif 000007
【図６−１】
2010079723.tif 000008
【図６−２】
2010079723.tif 000009
【図７】
2010079723.tif 000010
【図８】
2010079723.tif 000011
【図９】
2010079723.tif 000012
【図１０】
2010079723.tif 000013
【図１１】
2010079723.tif 000014
【図１２】
2010079723.tif 000015
【図１３】
2010079723.tif 000016
【図１４】
2010079723.tif 000017
【図１５】
2010079723.tif 000018
【図１６】
2010079723.tif 000019
【図１７】
2010079723.tif 000020
【図１８】
2010079723.tif 000021
【図１９】
2010079723.tif 000022
【図２０】
2010079723.tif 000023
【図２１】
2010079723.tif 000024
【図２２】
2010079723.tif 000025
【図２３】
2010079723.tif 000026
【図２４】
2010079723.tif 000027
【図２５】
2010079723.tif 000028
【図２６】
2010079723.tif 000029
【図２７】
2010079723.tif 000030
【図２８】
2010079723.tif 000031
【図２９】
2010079723.tif 000032
【図３０】
2010079723.tif 000033
【図３１】
2010079723.tif 000034
【図３２】
2010079723.tif 000035
【図３３】
2010079723.tif 000036
【図３４】
2010079723.tif 000037
【図３５】
2010079723.tif 000038
【図３６】
2010079723.tif 000039
【図３７】
2010079723.tif 000040
【図３８】
2010079723.tif 000041
【図３９】
2010079723.tif 000042
【図４０】
2010079723.tif 000043