(57)【要約】【課題】ε遷移の向きに依存せずにε除去を実行する。【解決手段】有限状態オートマトンに含まれる状態のうち、ε遷移を順方向および逆方向に辿って到達できる状態の集合を表す第１集合を生成する第１集合生成部１０１と、ε遷移でない遷移１本で接続されている複数の第１集合に含まれる状態の集合と、他の第１集合とε遷移でない遷移１本で接続されていない第１集合とを表す第２集合を生成する第２集合生成部１０２と、第２集合に含まれる各ε遷移に適用するε除去パターンの組み合わせのうち、ε除去後の遷移数が最小となる組み合わせを求める組み合わせ生成部１０３と、求められた組み合わせに含まれるε除去パターンで第２集合内のε遷移を除去する除去部１０４と、を備える。【選択図】図１
2011198126.tif 000002
【特許請求の範囲】
【請求項１】
有限状態オートマトンに含まれる状態のうち、ε遷移を順方向および逆方向に辿って到達できる状態の集合を表す第１集合を生成する第１集合生成部と、
複数の前記第１集合が相互にε遷移でない遷移１本で接続されている場合に、ε遷移でない遷移１本で接続されている複数の前記第１集合それぞれに含まれる状態の集合を生成し、生成した集合と、他の前記第１集合とε遷移でない遷移１本で接続されていない前記第１集合とを表す第２集合を生成する第２集合生成部と、
前記第２集合それぞれについて、ε遷移を除去する予め定められた複数の除去パターンのうち、前記第２集合に含まれる状態間のε遷移それぞれに適用する前記除去パターンの組み合わせを生成し、生成した前記組み合わせのうち、ε遷移を除去した後の前記第２集合内の遷移数が最小となる前記組み合わせを求める組み合わせ生成部と、
求められた前記組み合わせに含まれる前記除去パターンで前記第２集合内のε遷移を除去する除去部と、
を備えることを特徴とする情報処理装置。
【請求項２】
前記組み合わせ生成部は、前記第２集合それぞれについて、全ての前記除去パターンの組み合わせのうち一部の組み合わせを生成し、生成した前記組み合わせのうち、ε遷移を除去した後の前記第２集合内の遷移数が最小となる前記組み合わせを求めること、
を特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記組み合わせ生成部は、遺伝的アルゴリズムにより前記一部の組み合わせを生成すること、
を特徴とする請求項２に記載の情報処理装置。
【請求項４】
前記組み合わせ生成部は、前記第２集合内のε遷移それぞれに２つの前記除去パターンのうち一方の前記除去パターンを適用する組み合わせと、前記第２集合内のε遷移それぞれに２つの前記除去パターンのうち他方の前記除去パターンを適用する組み合わせとを生成し、生成した前記組み合わせのうち、ε遷移を除去した後の前記第２集合内の遷移数が最小となる前記組み合わせを求めること、
を特徴とする請求項２に記載の情報処理装置。
【請求項５】
前記有限状態オートマトンは、各遷移に重みが付与された重み付き有限状態オートマトンであり、
前記重み付き有限状態オートマトンに含まれる任意の状態間を結ぶ経路に含まれるε遷移の重みを、前記経路に含まれる各遷移に付与された重みに基づいて算出される前記経路の重みが変化しない特定値に変更する変更部をさらに備え、
前記第１集合生成部は、ε遷移の重みが変更された前記有限状態オートマトンに含まれる状態のうち、ε遷移を順方向および逆方向に辿って到達できる状態の集合を表す前記第１集合を生成すること、
を特徴とする請求項１に記載の情報処理装置。
【請求項６】
前記変更部は、前記重み付き有限状態オートマトンに含まれる状態間の遷移を変更せずに、前記経路に含まれるε遷移の重みを前記特定値に変更する第１変更処理を実行し、前記第１変更処理で重みが前記特定値に変更されないε遷移が存在する場合は、前記特定値に変更されないε遷移の遷移元として新たな状態を追加し、追加した状態に入る遷移の重みを前記特定値に変更されないε遷移の重みと置換する第２変更処理、または、前記特定値に変更されないε遷移の遷移先として新たな状態を追加し、追加した状態から出る遷移の重みを前記特定値に変更されないε遷移の重みと置換する第３変更処理を実行すること、
を特徴とする請求項５に記載の情報処理装置。
【請求項７】
前記有限状態オートマトンは、有限状態トランスデューサであり、
前記有限状態トランスデューサに含まれる任意の状態間を結ぶ経路に含まれるε遷移の出力記号を空記号に変更する変更部をさらに備え、
前記第１集合生成部は、ε遷移の出力記号が変更された前記有限状態トランスデューサに含まれる状態のうち、ε遷移を順方向および逆方向に辿って到達できる状態の集合を表す前記第１集合を生成すること、
を特徴とする請求項１に記載の情報処理装置。
【請求項８】
前記有限状態オートマトンは、各遷移に重みが付与された重み付き有限状態トランスデューサであり、
前記重み付き有限状態トランスデューサに含まれる任意の状態間を結ぶ経路に含まれるε遷移の重みを、前記経路に含まれる各遷移に付与された重みに基づいて算出される前記経路の重みが変化しない特定値に変更し、さらに前記有限状態トランスデューサに含まれる任意の状態間を結ぶ経路に含まれるε遷移の出力記号を空記号に変更する変更部をさらに備え、
前記第１集合生成部は、ε遷移の重みおよび出力記号が変更された前記重み付き有限状態トランスデューサに含まれる状態のうち、ε遷移の順方向および逆方向に辿って到達できる状態の集合を表す前記第１集合を生成すること、
を特徴とする請求項１に記載の情報処理装置。
【請求項９】
第１集合生成部が、有限状態オートマトンに含まれる状態のうち、ε遷移を順方向および逆方向に辿って到達できる状態の集合を表す第１集合を生成する第１集合生成ステップと、
第２集合生成部が、複数の前記第１集合が相互にε遷移でない遷移１本で接続されている場合に、ε遷移でない遷移１本で接続されている複数の前記第１集合それぞれに含まれる状態の集合を生成し、生成した集合と、他の前記第１集合とε遷移でない遷移１本で接続されていない前記第１集合とを表す第２集合を生成する第２集合生成ステップと、
組み合わせ生成部が、前記第２集合それぞれについて、ε遷移を除去する予め定められた複数の除去パターンのうち、前記第２集合に含まれる状態間のε遷移それぞれに適用する前記除去パターンの組み合わせを生成し、生成した前記組み合わせのうち、ε遷移を除去した後の前記第２集合内の遷移数が最小となる前記組み合わせを求める組み合わせ生成ステップと、
除去部が、求められた前記組み合わせに含まれる前記除去パターンで前記第２集合内のε遷移を除去する除去ステップと、
を含むことを特徴とする情報処理方法。
【請求項１０】
コンピュータを、
有限状態オートマトンに含まれる状態のうち、ε遷移を順方向および逆方向に辿って到達できる状態の集合を表す第１集合を生成する第１集合生成部と、
複数の前記第１集合が相互にε遷移でない遷移１本で接続されている場合に、ε遷移でない遷移１本で接続されている複数の前記第１集合それぞれに含まれる状態の集合を生成し、生成した集合と、他の前記第１集合とε遷移でない遷移１本で接続されていない前記第１集合とを表す第２集合を生成する第２集合生成部と、
前記第２集合それぞれについて、ε遷移を除去する予め定められた複数の除去パターンのうち、前記第２集合に含まれる状態間のε遷移それぞれに適用する前記除去パターンの組み合わせを生成し、生成した前記組み合わせのうち、ε遷移を除去した後の前記第２集合内の遷移数が最小となる前記組み合わせを求める組み合わせ生成部と、
求められた前記組み合わせに含まれる前記除去パターンで前記第２集合内のε遷移を除去する除去部、
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、情報処理装置、情報処理方法およびプログラムに関する。
【背景技術】
【０００２】
有限状態オートマトン（Ｆｉｎｉｔｅ  Ｓｔａｔｅ  Ａｕｔｏｍａｔｏｎ、ＦＳＡ）は、自然言語処理や音声認識等さまざまな分野で利用されている。例えば、文章中に表れる特定の文字列や文字列のパターンを検索するなどの用途がある。ＦＳＡは有限オートマトン（Ｆｉｎｉｔｅ  Ａｕｔｏｍａｔｏｎ、ＦＡ）や有限状態機械（Ｆｉｎｉｔｅ  Ｓｔａｔｅ  Ｍａｃｈｉｎｅ、ＦＳＭ）と呼ばれることもある。
【０００３】
ＦＳＡを拡張したモデル、例えば入力記号のほかに出力記号が存在し、ある入力記号が入力されるとそれに対応する出力記号を出力する有限状態トランスデューサ（Ｆｉｎｉｔｅ  Ｓｔａｔｅ  Ｔｒａｎｓｄｕｃｅｒ、ＦＳＴ）がある。ＦＳＴは、例えば音声認識における単語辞書に用いられることがある。そのような単語辞書は、発音を入力するとそれに対応する単語を出力するＦＳＴとして構成される。これ以外にも、入力記号のほかに確率や距離を取り扱うための重みが考慮されている重み付き有限状態オートマトン（Ｗｅｉｇｈｔｅｄ  Ｆｉｎｉｔｅ Ｓｔａｔｅ Ａｕｔｏｍａｔｏｎ、ＷＦＳＡ）や、ＦＳＴとＷＦＳＡの両方を含めたモデルである重み付き有限状態トランスデューサ（Ｗｅｉｇｈｔｅｄ  Ｆｉｎｉｔｅ  Ｓｔａｔｅ  Ｔｒａｎｓｄｕｃｅｒ、ＷＦＳＴ）がある。ＷＦＳＡやＷＦＳＴは、音声認識における言語モデルなどの音声認識に必要な辞書やモデルを表現するためのモデルとして用いられることや、統計的機械翻訳で用いられることがある。
【０００４】
以上で説明したＦＳＡやそれを拡張したモデルを実際にそれぞれの応用において用いるとき、必要な情報をＦＳＡやそれを拡張したモデルに変換する必要がある。このとき、入力が何も存在しなくても次の状態に遷移できるような遷移を用いると、この変換が容易になることがある。このような遷移はε遷移と呼ばれる。ε遷移には入力記号の代わりに空記号列（または空記号、空文字列、空入力などと呼ばれる）が割り当てられる。このような空記号列はεと書かれる。ある状態から０本以上のε遷移によってのみ到達可能な状態の集合はε閉包（ε−ｃｌｏｓｕｒｅ）と呼ばれている。ε遷移を除去する処理はε除去（ε−ｒｅｍｏｖａｌ）と呼ばれている。ε除去は、不要な遷移の数を減少させて処理時間を低減させることなどを目的に実行される。また、メモリ量および処理時間低減等のためには、ε除去後の遷移の数ができるだけ少なくなるように処理することが望ましい。
【０００５】
特許文献１には、ＷＦＳＡ、ＦＳＴ、およびＷＦＳＴに含まれるε遷移を除去する技術が提案されている。特許文献１を含む従来の方法では、ε除去は、ある状態ｑのε閉包を求め、そのε閉包に含まれる状態から出て行く遷移（ｏｕｔｇｏｉｎｇ  ｔｒａｎｓｉｔｉｏｎ）を、状態ｑから出て行く遷移とすることで実現している。遷移に重みや出力記号が割り当てられている場合は、状態ｑから出て行く遷移のうちε除去によって新たに作成される遷移の重みや出力記号をε遷移上にある重みや出力記号を考慮したものにする。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】米国特許第７，０２７，９８８号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、従来のε除去の方法では処理方向に依存性がある。すなわち、処理対象とするオートマトンの遷移の向きを全て逆にして従来の方法を用いると、逆にする前の結果と同じ結果が得られるとは限らない。ε閉包に含まれる状態が変化するためである。従来の方法を用いてε除去を行うときに、できる限り遷移の数を少なくするために、両方の向きについてε除去を行った上で、遷移の数が少ないほうを選ぶ方法も考えられる。この場合は両方の向きでそれぞれε除去を行う必要があるので処理時間が増加する。したがって、ε遷移の向きに依存せずにε除去を行うことが望ましい。
【０００８】
本発明は、上記に鑑みてなされたものであって、ε遷移の向きに依存せずにε除去を実行することができる情報処理装置、情報処理方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明は、有限状態オートマトンに含まれる状態のうち、ε遷移を順方向および逆方向に辿って到達できる状態の集合を表す第１集合を生成する第１集合生成部と、複数の前記第１集合が相互にε遷移でない遷移１本で接続されている場合に、ε遷移でない遷移１本で接続されている複数の前記第１集合それぞれに含まれる状態の集合を生成し、生成した集合と、他の前記第１集合とε遷移でない遷移１本で接続されていない前記第１集合とを表す第２集合を生成する第２集合生成部と、前記第２集合それぞれについて、ε遷移を除去する予め定められた複数の除去パターンのうち、前記第２集合に含まれる状態間のε遷移それぞれに適用する前記除去パターンの組み合わせを生成し、生成した前記組み合わせのうち、ε遷移を除去した後の前記第２集合内の遷移数が最小となる前記組み合わせを求める組み合わせ生成部と、求められた前記組み合わせに含まれる前記除去パターンで前記第２集合内のε遷移を除去する除去部と、を備えることを特徴とする。
【００１０】
また、本発明は、上記装置で実行することができる方法およびプログラムである。
【発明の効果】
【００１１】
本発明によれば、ε遷移の向きに依存せずにε除去を実行することができるという効果を奏する。
【図面の簡単な説明】
【００１２】
【図１】第１の実施の形態にかかる情報処理装置の機能ブロック図。
【図２】第１の実施の形態におけるε除去処理の全体の流れを示すフローチャート。
【図３】無向ε閉包を得るための擬似コードの一例を示す図。
【図４】無向ε閉包の一例を示す図。
【図５】連結無向ε閉包を得るための擬似コードの一例を示す図。
【図６】連結無向ε閉包の一例を示す図。
【図７】ε遷移の一例を示す図。
【図８】ε除去パターンの一例を示す図。
【図９】ε除去パターンの一例を示す図。
【図１０】連結無向ε閉包ψに含まれるε組を全て取得する擬似コードの一例を示す図。
【図１１】関数ｆｎｕｍの擬似コードの一例を示す図。
【図１２】関数ｍａｋｅ−ｔｒａｎｓｉｔｉｏｎの擬似コードの一例を示す図。
【図１３】ε除去の擬似コード（ＣＵＥＣ-ε−ｒｅｍｏｖａｌ）の一例を示す図。
【図１４】有限状態オートマトンに含まれる全てのε遷移を取り除く方法の擬似コードの一例を示す図。
【図１５】ε除去前のＦＳＡを示す図。
【図１６】従来法によってε除去を行った結果を示す図。
【図１７】遷移の向きを反転させた後に従来法によってε除去を行った結果を示す図。
【図１８】第１の実施の形態で述べた方法によってε除去を行った結果を示す図。
【図１９】第１の実施の形態の情報処理装置のハードウェア構成図。
【図２０】第２の実施の形態にかかる情報処理装置の機能ブロック図。
【図２１】重みを移動させる方法の擬似コード（ｐｕｓｈ−ｗｅｉｇｈｔ）の一例を示す図。
【図２２】プッシュパターンの一例を示す図。
【図２３】ε除去パターン配列ｘの一例を示す図。
【図２４】関数ｇｎｕｍの擬似コードの一例を示す図。
【図２５】関数ｍａｋｅ−ｐａｔｈの擬似コードの一例を示す図。
【図２６】ＷＦＳＡに含まれるε遷移を全て除去する方法の擬似コード（ＷＦＳＡ−ＤＩ−ε−ｒｅｍｏｖａｌ）の一例を示す図。
【図２７】ε除去の擬似コード（ＷＦＳＡ−ＣＵＥＣ-ε−ｒｅｍｏｖａｌ）の一例を示す図。
【図２８】関数ＷＦＳＡ−ｍａｋｅ−ｔｒａｎｓｉｔｉｏｎの擬似コードの一例を示す図。
【図２９】ε除去前のＷＦＳＡを示す図。
【図３０】従来法によってε除去を行った結果を示す図。
【図３１】遷移の向きを反転させた後に従来法によってε除去を行った結果を示す図。
【図３２】重みを移動した後のＷＦＳＡを示す図。
【図３３】ＷＦＳＡを示す図。
【図３４】第２の実施の形態によるε除去の最終結果を示す図。
【図３５】第３の実施の形態にかかる情報処理装置の機能ブロック図。
【図３６】文字列の移動方法の擬似コード（ｐｕｓｈ−ｏｕｔｐｕｔ）の一例を示す図。
【図３７】関数ε−ｏｕｔｐｕｔの擬似コードの一例を示す図。
【図３８】関数ε−ＤＦＳの擬似コードの一例を示す図。
【図３９】ε除去前のＦＳＴを示す図。
【図４０】従来法によってε除去を行った結果を示す図。
【図４１】遷移の向きを反転させた後に従来法によってε除去を行った結果を示す図。
【図４２】第３の実施の形態によるε除去処理の結果を示す図。
【発明を実施するための形態】
【００１３】
以下に添付図面を参照して、この発明にかかる情報処理装置の好適な実施の形態を詳細に説明する。
【００１４】
（第１の実施の形態）
第１の実施の形態にかかる情報処理装置は、ε除去のパターン（ε除去パターン）の選択の結果が影響する状態の範囲を探索し、探索した範囲ごとにε除去を実行する。ε除去パターンの選択結果が影響する範囲は、ε遷移の向きに依存せずに探索する。このため、ε遷移の向きに依存せずにε除去を実行することができる。
【００１５】
ここで、ε除去パターンの詳細について説明する。状態ｑｓからε遷移のみで到達できる状態を状態ｑｄとする。受理する言語を変えることなく、この２つの状態間のε遷移を除去するためには、別の新たな遷移を生成する必要がある。ここで受理する言語とは有限状態オートマトンが受理する入力記号列の集合のことを言う。遷移の生成にはパターンがある。以下では、このパターンをε除去パターン（ε−ｒｅｍｏｖａｌ  ｐａｔｔｅｒｎ）と呼ぶこととする。ε除去パターンには少なくとも２つのパターンが存在する。
【００１６】
ε除去パターンの１つは、状態ｑｓに入ってくる遷移（ｉｎｃｏｍｉｎｇ  ｔｒａｎｓｉｔｉｏｎ）を、状態ｑｄを次状態とする遷移として複製するというパターンである。もう１つのε除去パターンは、状態ｑｄから出て行く遷移（ｏｕｔｇｏｉｎｇ  ｔｒａｎｓｉｔｉｏｎ）を、状態ｑｓを前状態とする遷移として複製するというパターンである。いずれのε除去パターンを選択するかによって、最終的に得られる遷移の数が異なる。また、あるε除去パターンの選択の結果が、他の２つの状態間におけるε除去パターンの選択の結果に影響されることもある。このため、第１の実施の形態では、最初にこの選択が互いに影響する範囲を探索する。以下、第１の実施の形態の詳細について説明する。
【００１７】
図１は、第１の実施の形態にかかる情報処理装置１００の機能構成の一例を示すブロック図である。図１に示すように、情報処理装置１００は、第１集合生成部１０１と、第２集合生成部１０２と、組み合わせ生成部１０３と、除去部１０４と、を備えている。
【００１８】
第１集合生成部１０１は、処理対象となる有限状態オートマトンに含まれる状態のうち、ε遷移を順方向および逆方向に辿って到達できる状態の集合（第１集合）を表す無向ε閉包（ｕｎｄｉｒｅｃｔｅｄ  ε−ｃｌｏｓｕｒｅ）を生成する。
【００１９】
第２集合生成部１０２は、他の無向ε閉包と直接接続または間接接続されている無向ε閉包から成る集合（第２集合）を表す連結無向ε閉包（ｃｏｎｎｅｃｔｅｄ  ｕｎｄｉｒｅｃｔｅｄ  ε−ｃｌｏｓｕｒｅ、ＣＵＥＣ）を生成する。また、第２集合生成部１０２は、他のいずれの無向ε閉包とも直接接続していない無向ε閉包１つから成る集合についても連結無向ε閉包に含める。なお、直接接続および間接接続の意味については後述する。連結無向ε閉包が、ε除去パターンの選択が互いに影響を与える範囲に相当する。ε除去は、このような連結無向ε閉包を処理対象として、連結無向ε閉包ごとに実行される。
【００２０】
組み合わせ生成部１０３は、連結無向ε閉包それぞれについて、連結無向ε閉包に含まれる状態間のε遷移それぞれに適用する除去パターンの組み合わせのうち、ε遷移を除去した後の連結無向ε閉包内の遷移数が最小となる組み合わせを求める。
【００２１】
除去部１０４は、生成された組み合わせに含まれる除去パターンで連結無向ε閉包内の各ε遷移のε除去を実行する。
【００２２】
次に、このように構成された第１の実施の形態にかかる情報処理装置１００によるε除去処理について図２を用いて説明する。図２は、第１の実施の形態におけるε除去処理の全体の流れを示すフローチャートである。
【００２３】
まず、第１集合生成部１０１が、入力された有限状態オートマトン（ＦＳＡ）の各状態および遷移を探索し、無向ε閉包を生成する（ステップＳ１０１）。次に、第２集合生成部１０２が、生成された無向ε閉包から連結無向ε閉包を生成する（ステップＳ１０２）。次に、組み合わせ生成部１０３が、連結無向ε閉包内のε遷移に適用できるε除去パターンの組み合わせのうち、遷移の数が最小となるε除去パターンの組み合わせを探索する（ステップＳ１０３）。
【００２４】
組み合わせ生成部１０３は、組み合わせの総数が少ない場合は、全組み合わせについて探索し、現実的な時間で調べられないほど組み合わせの総数が多いときには、一部の組み合わせのみを調べ、その中で最も遷移の数が少なくなる組み合わせを選ぶ。
【００２５】
次に、除去部１０４が、選んだ組み合わせに含まれる各除去パターンでε除去を実行する（ステップＳ１０４）。すなわち、選んだ組み合わせに含まれる各除去パターンで対応するε遷移を除去し、初期状態から到達不可能になった状態と関連する遷移を除去する。
【００２６】
次に、組み合わせ生成部１０３が、全ての連結無向ε閉包について処理が終了したか否かを判断する（ステップＳ１０５）。終了していない場合（ステップＳ１０５：Ｎｏ）、組み合わせ生成部１０３は、未処理の組み合わせ生成部１０３に対して処理を繰り返す（ステップＳ１０３）。終了した場合は（ステップＳ１０５：Ｙｅｓ）、ε除去処理を終了する。以上の処理により、ε遷移が存在しないＦＳＡが得られる。
【００２７】
以下、図２の各ステップの詳細について説明する。
【００２８】
（準備）
ＦＳＡは、状態の集合Ｑ、遷移の集合Ｅ、入力記号の集合Σ、初期状態の集合Ｉ、終了状態の集合Ｆから成る５つ組（Ｑ，Ｅ，Σ，Ｉ，Ｆ）から構成される。遷移は、３つ組（前状態，入力記号，次状態）で構成される。これら５つの集合は、ε除去の処理対象となるＦＳＡを構成する情報として常に参照することができるものとする。例えば、これらの情報が図示しない記憶部等に記憶され、以下に例示する擬似コード等から常に参照できるように構成する。
【００２９】
空集合はφと書く。集合Ｂの要素の数は｜Ｂ｜と書く。ε遷移のみで構成される経路をε経路と定義する。
【００３０】
ある状態から１本以上のε遷移をその遷移の向きに関わらず辿ることで到達できる状態の集合を無向ε閉包と呼ぶ。無向ε閉包Ｃ１とＣ２にそれぞれ含まれる状態をｑ１、ｑ２とする。ｑ１とｑ２がε遷移でない遷移１本のみで接続されているとき、無向ε閉包Ｃ１とＣ２は直接接続されているという。無向ε閉包Ｃ１、Ｃ２、Ｃ３において、Ｃ１とＣ２が接続されており、Ｃ２とＣ３も接続されているとき、Ｃ１とＣ３は間接接続されているという。
【００３１】
直接接続されているか間接接続されているかに関わらず接続されている無向ε閉包から成る集合と、他のいずれの無向ε閉包とも直接接続していない無向ε閉包１つから成る集合を連結無向ε閉包という。すなわち、連結無向ε閉包は１つ以上の無向ε閉包から構成され、２つ以上の無向ε閉包を含む場合、それらは直接接続または間接接続されている。
【００３２】
ε除去パターンの選択が互いに影響を受ける範囲に含まれる状態は、連結無向ε閉包に含まれる状態に等しい。接続されていない、すなわちε遷移以外の遷移が２本以上間に挟まっている２つの無向ε閉包において、一方の無向ε閉包に含まれるε除去パターンが他方の無向ε閉包に含まれるε除去パターンに影響を与えることはない。
【００３３】
（方法）
はじめにε除去パターンの選択が互いに影響を受ける範囲を得る方法について説明し、次にε除去パターンの選択をどのように行うかを説明する。最後に、選んだε除去パターンの選択に基づいてε遷移を除去する方法について説明する。
【００３４】
（無向ε閉包を得る方法：ステップＳ１０１）
各状態へと入ってくるε遷移が出て行くε遷移でもあるとみなして深さ優先探索（Ｄｅｐｔｈ  Ｆｉｒｓｔ  Ｓｅａｒｃｈ、ＤＦＳ）で探索する。ここで探索する対象となる遷移はε遷移のみである。探索が必要な全ての状態に対して探索が終了すると、無向ε閉包が得られる。
【００３５】
図３は、無向ε閉包を得るための擬似コードの一例を示す図である。ここで、Θは無向ε閉包から成る集合である。Ｓはスタックであり、関数ｐｕｓｈによって後に入れられた要素が関数ｐｏｐによって先に取り出される。ｉｎｐｕｔ（ｅ）、ｎ（ｅ）、ｐ（ｅ）はそれぞれ遷移ｅに割り当てられている入力記号、次状態、前状態を表す。図３の擬似コード（ａｌｌ−ｕｎｄｉｒｅｃｔｅｄ−ε−ｃｌｏｓｕｒｅ）は、第１集合生成部１０１が実行する。
【００３６】
１行目で処理対象とするＦＳＡに含まれる状態を全てＱｒに代入する。この時点ではＱとＱｒは等しい。また、Θを空集合として初期化し、スタックＳも空にする。
【００３７】
２行目でＱｒが空集合か否かを調べ、空集合であるなら１７行目に処理を移す。空集合でなければまだ処理すべき状態が残っているということであるので、３行目へと進む。
【００３８】
３行目ではこれ以降の処理で使用するＱεを空集合で初期化する。
【００３９】
４行目では集合Ｑｒからいずれか１つの状態を選び、状態ｑに代入する。選び方はどのようにしてもよいが、例えばランダムに選ぶ、状態番号が最も小さいものを選ぶ、状態番号が最も大きいものを選ぶなどの方法がある。
【００４０】
５行目ではスタックＳに状態ｑを追加する。
【００４１】
６行目ではスタックＳが空集合であるか否かを調べ、空集合であれば１４行目に処理を進める。そうでなければ７行目へと処理を進める。
【００４２】
７行目ではスタックＳから要素が１つ取り出され、ｑεに代入される。代入されたｑεはスタックＳから取り除かれる。
【００４３】
８行目ではｑεをＱεに追加する。
【００４４】
９行目はεが入力記号として割り当てられている全ての遷移について１０行目から１３行目までの処理を行うことを表している。１０行目から１３行目で処理対象となる遷移はeで表される。
【００４５】
１０行目では遷移ｅの前状態とｑεが等しく、かつ、遷移ｅの次状態がＱεに含まれていないことを判定し、判定が真なら１１行目へと処理を進める。そうでなければ１２行目へと処理を進める。
【００４６】
１１行目では遷移ｅの次状態をスタックＳに追加する。
【００４７】
１２行目では遷移ｅの次状態とｑεが等しく、かつ、遷移ｅの前状態がＱεに含まれていないことを判定し、判定が真なら１３行目へと処理を進める。そうでなれば９行目に戻る。
【００４８】
１３行目では遷移ｅの前状態をスタックＳに追加する。その後、９行目に戻る。
【００４９】
１４行目ではＱεに含まれる状態をＱｒから取り除く。
【００５０】
１５行目ではＱεに含まれる状態の数が２個以上であるか否かを判定し、２個以上であれば１６行目に進む。そうでなければ２行目に戻る。
【００５１】
１６行目まで処理が進んだとき、Ｑεは処理対象のＦＳＡに含まれる無向ε閉包の１つになっている。１６行目ではＱεを無向ε閉包を要素とする集合Θに追加する。その後、２行目に戻る。
【００５２】
１７行目ではこの処理で得られた集合Θを処理結果として返す。
【００５３】
図４は、このような処理により得られる無向ε閉包の一例を示す図である。図４の点線で囲まれた部分が無向ε閉包である。この例の場合、図３に示した方法で得られる結果は、Θ＝｛｛１，２｝，｛３，４｝，｛６，７，８｝｝となる。状態は円で表され、遷移は状態と状態とを接続する矢印で表されている。太線の円が初期状態であり、２重線の円が終了状態である。なお、この有限状態オートマトンは入力ａａａのみを受理することができる。
【００５４】
（連結無向ε閉包を得る方法：ステップＳ１０２）
図５は、処理対象としているＦＳＡに含まれる全ての連結無向ε閉包を得るための擬似コードの一例を示す図である。
【００５５】
１行目では連結無向ε閉包を要素とする集合Ψを空集合で初期化する。
【００５６】
２行目は指定された無向ε閉包の集合であるΘに含まれる無向ε閉包の要素全てについて３行目から１３行目までの処理を行うことを表している。処理対象とする無向ε閉包はθであるとする。
【００５７】
３行目では無向ε閉包を要素とする集合ψをθを要素とする集合として初期化する。
【００５８】
４行目はθに含まれる全ての状態について５行目から８行目までを処理することを表している。５行目から８行目の間で処理対象となる状態をｑとしている。
【００５９】
５行目はΘに含まれるθ以外の要素について、６行目から８行目を処理することを表している。処理対象とする要素をθ'とする。
【００６０】
６行目ではθ'に含まれる全ての状態について７行目と８行目を処理することを表している。処理対象とする状態をｑ'とする。
【００６１】
７行目ではε遷移でない遷移のうち、前状態がｑであり次状態がｑ'であるような遷移、または、次状態がｑであり前状態がｑ'であるような遷移が存在しているか否かを判断しており、存在していれば、８行目に進む。
【００６２】
８行目ではψにθ'を追加する。
【００６３】
４行目から８行目は、無向ε閉包θに直接接続されている無向ε閉包をψに集めていることに相当する。
【００６４】
４行目から８行目の一連の処理が完了すると、９行目の処理に移る。９行目はΨに含まれる全ての要素について１０行目から１２行目の処理を行うことを表している。１０行目から１２行目の各処理で処理対象とする要素はψ'と表す。
【００６５】
１０行目ではψとψ'の積集合が空集合であるか否かを判定する。空集合である場合は９行目に戻る。そうでない場合は１１行目に進む。
【００６６】
１１行目ではψ'に含まれる要素である無向ε閉包をψに追加する。
【００６７】
１２行目ではψ'をΨから取り除く。
【００６８】
９行目から１２行目の処理は直接接続されている無向ε閉包から間接接続されている無向ε閉包を見つける処理に該当する。
【００６９】
１３行目ではψをΨに追加する。
【００７０】
１４行目では１行目から１３行目の処理で得られた連結無向ε閉包を要素とする集合Ψを処理結果として返す。
【００７１】
図６は、このような処理により得られる連結無向ε閉包の一例を示す図である。図６の点線で囲まれている部分が連結無向ε閉包である。図６の上部の連結無向ε閉包は、２つの無向ε閉包がε遷移でない遷移１本のみで接続されているために得られる連結無向ε閉包である。一方、図６の下部の無向ε閉包は、上部の無向ε閉包とε遷移でない遷移２本で接続しているので、上部の連結無向ε閉包には含まれず、単独で連結無向ε閉包を構成する。
【００７２】
（ε除去パターン）
ここで、ε除去パターンの詳細について図７〜図９を用いてさらに説明する。図７は、ε遷移の一例を示す図である。図８および図９は、ε除去パターンの一例を示す図である。
【００７３】
ε経路で接続されている２つの状態ｑ１、ｑ２を考える。ｑ１に入ってくる遷移と出て行く遷移の集合をそれぞれＥｉ１、Ｅｏ１、ｑ２に入ってくる遷移と出て行く遷移の集合をそれぞれＥｉ２、Ｅｏ２とする（図７参照）。ｑ１とｑ２の間のε遷移を全て削除したときのＦＳＡが元のＦＳＡと同じ動作をするためには、Ｅｉ１、Ｅｉ２、Ｅｏ１、Ｅｏ２に含まれる遷移の次状態や前状態を変更したり、複製した上で変更したりする必要がある。
【００７４】
ε遷移を除去しても同じ言語を受理できるように変形する際に必要となる遷移を生成するパターンであるε除去パターンは２つ考えられる。１つは、図８のようにＥｉ１を複製するパターンであり、もう１つが図９のようにＥｏ２を複製するパターンである。
【００７５】
以降、図８および図９のパターンを、それぞれをε除去パターン０、ε除去パターン１と呼ぶ。単に図７のようにε遷移が１本だけの場合では、｜Ｅｏ１｜＞０かつ｜Ｅｉ２｜＞０である場合はＥｏ２とＥｉ１のうち含まれる遷移の数が小さいほうを複製すればよい。｜Ｅｏ１｜＝０の場合はＥｉ１を状態２に移動し、｜Ｅｉ２｜＝０の場合はＥｏ２を状態１に移動すればよい。｜Ｅｏ１｜＝０かつ｜Ｅｉ２｜＝０の場合には、いずれを移動させても結果は同じである。
【００７６】
ところが３つ以上の状態が含まれる無向ε閉包では、ε経路１つを除去するときに最も遷移が減るε除去パターンを選んだとしても、他のε経路の除去も含めるとそのε除去パターンが全体として最も遷移が少ないパターンではないことがある。全ての組み合わせについて調べれば、遷移の数が最も少なくなる組み合わせを見つけることができる。
【００７７】
連結無向ε閉包内に含まれる選択が必要なε除去パターンの総数をＮとし、ｉ番目のε除去パターンの選択でε除去パターン０かε除去パターン１のいずれを選んだのかを記録しておく変数をｘｉとする。この変数ｘｉをＮ個並べると、ｘ１ｘ２ｘ３・・・ｘＮとなり、これは配列として記録できる。これをε除去パターン配列ｘとする。
【００７８】
（選択が必要なε除去パターンの列挙）
ステップＳ１０３では、組み合わせ生成部１０３は、まず、選択が必要な全てのε除去パターンを列挙する。以下、詳細について説明する。
【００７９】
連結無向ε閉包に含まれる状態と、その状態から１本以上のε遷移を順方向に進むことで到達することのできる状態とで構成される２つ組をε組と呼ぶこととする。１つのε組につき１つのε除去パターンを選択しなければならないので、全てのε組を列挙できれば、選択が必要な全てのε除去パターンを列挙できたことになる。
【００８０】
図１０は、連結無向ε閉包ψに含まれるε組を全て取得する擬似コードの一例を示す図である。ここで、ε−ｏｕｔ（ｑ）は、状態ｑから出て行く遷移のうちε遷移のみから成る集合である。
【００８１】
１行目では集合ＰεとスタックＳを空集合で初期化する。
【００８２】
２行目は、無向ε閉包を要素とする集合ψに含まれる全ての要素について３行目から１０行目を処理することを表している。３行目から１０行目で処理対象となる無向ε閉包をθとする。
【００８３】
３行目は、無向ε閉包θに含まれる全ての状態について４行目から１０行目を処理することを表している。４行目から１０行目の各処理で対象となる状態をｑとする。
【００８４】
４行目ではｑをスタックＳに追加し、Ｑｓを空集合で初期化する。
【００８５】
５行目ではスタックＳが空集合か否かを判定し、空集合であれば３行目に戻る。そうでなければ６行目に進む。
【００８６】
６行目ではスタックＳから状態を取り出しｑｓに代入する。
【００８７】
７行目ではｑｓをＱｓに追加する。
【００８８】
８行目ではｑｓから出て行くε遷移のうち次状態がＱｓに含まれない遷移ｅについて９行目と１０行目の処理を行う。
【００８９】
９行目ではＰεにｑと遷移ｅの次状態から成る２つ組を追加する。
【００９０】
１０行目ではスタックＳに遷移ｅの次状態を追加する。
【００９１】
１行目から１０行目までの全ての処理が完了すると、Ｐεにε組が記録されるので、１１行目でＰεを処理結果として返す。
【００９２】
（ε除去後の遷移の数の計算）
次に、組み合わせ生成部１０３は、ε除去後の遷移の数を計算する。以下、詳細について説明する。
【００９３】
連結無向ε閉包内のε遷移をε除去パターン配列ｘに基づいて除去すると遷移の数がいくつになるかを計算する関数ｆｎｕｍ（ｘ，Ｐε）を考える。Ｐεはｘに対応する図１０で得られた状態の２つ組から成る集合である。つまり、Ｐεのｉ番目のε組に対応するε除去パターンがε除去パターン配列ｘのｉ番目に記録されることになる。したがって、ｘの長さ（要素の数）を｜ｘ｜、Ｐεの要素の数を｜Ｐε｜とすると、｜ｘ｜と｜Ｐε｜は等しい。各状態に入ってくる遷移と出て行く遷移の数がどのようになっているかが分かれば良いので、図１１と図１２で構成される方法によって実現できる。図１１は、関数ｆｎｕｍの擬似コードの一例を示す図である。図１２は、関数ｆｎｕｍの中で実行される関数ｍａｋｅ−ｔｒａｎｓｉｔｉｏｎの擬似コードの一例を示す図である。
【００９４】
ε除去パターン配列ｘを用いて、ある連結無向ε閉包内のε除去を行う場合には図１１のようなｆｎｕｍ（ｘ，Ｐε）を呼び出す。
【００９５】
１行目ではε除去後の遷移の集合Ｅｎｅを空集合として初期化する。また、Ｐεに状態の２つ組として含まれている各々の状態を全てＱεに代入する。
【００９６】
２行目はＱεに含まれている状態ｑに対して３行目から７行目を処理することを表している。
【００９７】
３行目では第１引数をｑ、第２引数をｘ、第３引数をＰεとして関数ｍａｋｅ−ｔｒａｎｓｉｔｉｏｎを呼び出し、その結果をＥｉｎ、Ｅｏｕｔ、ｂｉｎｉｔｉａｌ、ｂｆｉｎａｌ、ｂｅｒｒｏｒとして受け取る。Ｅｉｎはε除去後に状態ｑに入ってくる遷移の集合、Ｅｏｕｔはε除去後に状態ｑから出て行く遷移の集合、ｂｉｎｉｔｉａｌはε除去後に状態ｑが初期状態であるか否かを表している値、ｂｆｉｎａｌはε除去後に状態ｑが終了状態であるか否かを表している値、ｂｅｒｒｏｒはε除去後に受理する言語が変わるか否かを表している値である。
【００９８】
４行目では受理する言語が変わるか否かを判定し、ｂｅｒｒｏｒが偽のときは６行目に進む。真のときは５行目に進む。
【００９９】
５行目では、エラーとして無限大の値、または、ｆｎｕｍ（ｘ，Ｐε）が返すことができる最大の値を返し、処理を完了する。
【０１００】
６行目では７行目へ進むか否かの判定を行う。ＥｉｎとＥｏｕｔが共に空集合でない、またはｂｉｎｉｔｉａｌが真でＥｏｕｔが空集合でない、またはｂｆｉｎａｌが真でＥｉｎが空集合でなければ７行目へと進む。そうでなければ２行目へ戻る。
【０１０１】
７行目ではＥｉｎとＥｏｕｔをＥｎｅへ追加する。
【０１０２】
８行目では１行目から７行目までの処理で得られたＥｎｅに含まれる遷移の数を処理結果として返す。
【０１０３】
次に、図１２の関数ｍａｋｅ−ｔｒａｎｓｉｔｉｏｎについて説明する。
【０１０４】
１行目ではｑが初期状態であればｂｉｎｉｔｉａｌを真（ｔｒｕｅ）に、そうでなければ偽（ｆａｌｓｅ）に初期化する。同様にｑが終了状態であればｂｆｉｎａｌを真に、そうでなければ偽に初期化する。
【０１０５】
２行目ではε遷移以外の遷移のうち状態ｑへと入ってくる遷移をＥｉｎに代入する。同様に、ε遷移以外の遷移のうち状態ｑから出て行く遷移をＥｏｕｔに代入する。
【０１０６】
３行目は変数ｉの値を１からＰεの要素の数まで１ずつ増やしながら４行目から１６行目を繰り返し処理することを表す。
【０１０７】
４行目ではＰεに含まれる要素のうち、ｉ番目の要素である２つ組に含まれる状態をそれぞれｑｓとｑｄに代入する。ｑｄはｑｓからε遷移を順方向に進むことでたどり着ける状態である。
【０１０８】
５行目ではｑｓがｑと同じ状態であるか否かを判定し、同じ状態でなければ１０行目に進む。同じ状態であれば６行目に進む。
【０１０９】
６行目ではε除去パターン配列ｘのうち、ｉ番目の値が１であるか否かを判定し、１でなければ１０行目に進む。１であれば７行目に進む。ｘｉが１であるということはε除去パターン１を選択していることを意味している。すなわちｑｄから出て行く遷移がｑｓから出て行く遷移として複製されることを意味している。
【０１１０】
７行目ではｑｄから出て行く遷移のうちε遷移でない遷移をｑから出て行く遷移としてＥｏｕｔに追加する。
【０１１１】
８行目ではｑｄが終了状態か否かを判定し、終了状態でなければ１０行目へ進む。そうでなければ９行目へ進む。
【０１１２】
９行目ではｂｆｉｎａｌに真を代入する。そして１０行目へ進む。
【０１１３】
１０行目ではｑｄとｑが等しいか否かを判定し、等しければ１１行目へ進む。そうでなければ３行目へと戻る。
【０１１４】
１１行目ではε除去パターン配列ｘのうち、ｉ番目の値が０であるか否かを判定し、０でなければ３行目へ戻る。０であれば１２行目へ進む。ｘｉが０であるということはε除去パターン０を選択していることを意味している。すなわちｑｓに入ってくる遷移がｑｄに入ってくる遷移として複製されることを意味している。
【０１１５】
１２行目ではｑｓが終了状態であるか否かを判定する。終了状態でなければ１４行目へ進み、そうでなければ１３行目へ進む。
【０１１６】
１３行目が処理されるとき、元のＦＳＡと異なる言語を受理できるようになることを意味しており、正しいε除去が行えない。そのため、引数として受け取ったε除去パターン配列ｘが使用されることがないようにしなければならない。そこで、戻り値の５つ組の５つ目の値を真にすることでこのことを呼び出し側に伝達する。このとき５つ組の他の値は使用されないのでどのような値でもよい。
【０１１７】
１４行目ではｑｓに入ってくる遷移のうちε遷移でない遷移をｑに入ってくる遷移としてＥｉｎに追加する。
【０１１８】
１５行目ではｑｓが初期状態か否かを判定し、初期状態であれば１６行目に進む。そうでなければ３行目に戻る。
【０１１９】
１６行目ではｂｉｎｉｔｉａｌに真を代入する。
【０１２０】
３行目から１６行目の繰り返し処理が完了すると、１７行目へ進む。
【０１２１】
１７行目は１行目から１６行目までの処理の結果を５つ組として返す。５つ組の１つ目にはＥｉｎ、２つ目にはＥｏｕｔ、３つ目にはｂｉｎｉｔｉａｌ、４つ目にはｂｆｉｎａｌ、異なる言語を受理するような変形は発生していないので５つ目には偽が設定される。
【０１２２】
ここで、ｏｕｔ（ｑ）は状態ｑから出て行く遷移の集合、ｉｎ（ｑ）は状態ｑへ入ってくる遷移の集合である。ｘｉは、Ｐεに含まれるｉ番目のε組に対応するε除去パターン配列ｘのｉ番目の要素である。
【０１２３】
組み合わせ生成部１０３は、様々なｘについてｆｎｕｍ（ｘ，Ｐε）の値を求め、この値が最も小さくなるようなｘを求める。除去部１０４は、このようにして得られたｘに基づいて遷移の生成と破棄を行うことで、ε除去の向きに依存せずにε遷移を除去できる。組み合わせ生成部１０３がε除去パターン配列ｘが取りうる全ての値について計算すれば、ε遷移除去後の遷移の数を最小にできる。しかしながら、全ての組み合わせの数は２｜ｘ｜個である。｜ｘ｜が大きすぎるために取りうる全ての値について計算できない場合は、組み合わせ生成部１０３は、いくつかの組み合わせについてのみｆｎｕｍ（ｘ，Ｐε）を計算し、その中で最も小さい値になるようなｘを選ぶようにすればよい。
【０１２４】
例えば、全て１と全て０の２パターンのみ計算して、ｆｎｕｍ（ｘ，Ｐε）の値が小さいほうを使うようにする方法が適用できる。他にも、ｘが０と１の列でしかないことから、遺伝的アルゴリズムなどの組み合わせ最適化問題で用いられる一般的な手法を適用してもよい。
【０１２５】
（ε除去に伴う遷移の生成と破棄：ステップＳ１０４）
ε除去パターン配列ｘの値が決まれば、除去部１０４は、ε除去パターン配列ｘに基づいて遷移の生成と破棄を行うε除去を実行する。図１３は、ε除去の擬似コード（ＣＵＥＣ-ε−ｒｅｍｏｖａｌ）の一例を示す図である。
【０１２６】
１行目ではＰεに含まれる２つ組を構成する状態を全てＱεに代入する。さらにＱ、Ｅ、Ｉ、ＦをそれぞれＱｎｅｗ、Ｅｎｅｗ、Ｉｎｅｗ、Ｆｎｅｗに代入する。
【０１２７】
２行目はＱεに含まれる状態をｑとし、Ｑεに含まれる全ての状態について３行目から１２行目を繰り返し処理することを表している。
【０１２８】
３行目では第１引数をｑ、第２引数をｘ、第３引数をＰεとして関数ｍａｋｅ−ｔｒａｎｓｉｔｉｏｎを呼び出す。結果は５つ組で戻ってくるが、５つ目の値は使用しない。１つ目がε除去後にｑに入ってくる遷移の集合Ｅｉｎ、２つ目がε除去後にｑから出て行く遷移の集合Ｅｏｕｔ、３つ目がε除去後にｑが初期状態か否かを表す値ｂｉｎｉｔｉａｌ、４つ目がε除去後にｑが終了状態か否かを表す値ｂｆｉｎａｌである。ここでは使用しない５つ目の値に対応する部分に「・」を記しているが、これ以降、このように使用しない値が組に含まれる場合には対応する部分に「・」を記すこととする。
【０１２９】
４行目は、以下の（１）〜（４）の４つの条件のいずれかが満たされれば５行目でＥｉｎとＥｏｕｔをＥｎｅｗに追加することを表す。
（１）ＥｉｎもＥｏｕｔも空集合でないこと
（２）ｂｉｎｉｔｉａｌが真かつＥｏｕｔが空集合でないこと
（３）ｂｆｉｎａｌが真かつＥｉｎが空集合でないこと
（４）ｂｉｎｉｔｉａｌが真かつｂｆｉｎａｌが真であること
【０１３０】
４行目の条件が満たされない場合、７行目が実行され、ＥｉｎとＥｏｕｔがＥｎｅｗから除去される。さらにｑが処理対象のＦＳＡを構成するＱｎｅｗから除去される。ｑが初期状態や終了状態である場合はＩｎｅｗやＦｎｅｗからも削除される。
【０１３１】
８行目でｂｉｎｉｔｉａｌが真であれば９行目で状態ｑを初期状態の集合Ｉｎｅｗに追加する。
【０１３２】
１０行目でｂｆｉｎａｌが真であれば１１行目で状態ｑを終了状態の集合Ｆｎｅｗに追加する。
【０１３３】
１２行目では状態ｑから出て行くε遷移をＥｎｅｗから除去する。１３行目で、３行目から１２行目までの繰り返し処理で変更されたＱｎｅｗ、Ｅｎｅｗ、Ｉｎｅｗ、ＦｎｅｗをそれぞれＱ、Ｅ、Ｉ、Ｆに代入する。ただし、Ｅｎｅｗに関しては前状態と次状態がＱｎｅｗに含まれる遷移のみをＥに代入する。
【０１３４】
（全てのε遷移を取り除く方法）
これまでに説明してきた方法を組み合わせると、有限状態オートマトンに含まれる全てのε遷移を取り除く方法（ＤＩ−ε−ｒｅｍｏｖａｌ）を構成できる。図１４は、有限状態オートマトンに含まれる全てのε遷移を取り除く方法の擬似コードの一例を示す図である。図１４は、図２のε除去処理に対応する擬似コードの一例である。
【０１３５】
１行目でａｌｌ−ｕｎｄｉｒｅｃｔｅｄ−ε−ｃｌｏｓｕｒｅ（）（図３）により、無向ε閉包を計算し、その結果をΘに代入する。
【０１３６】
２行目でａｌｌ−ＣＵＥＣ（Θ）（図５）により、連結無向ε閉包を計算し、その結果をΨに代入する。Ψの要素を連結無向ε閉包ψとし、Ψに含まれる全ての要素に対して４行目から６行目を繰り返し実行する。
【０１３７】
４行目ではａｌｌ−ε−ｐａｉｒ（ψ）（図１０）により、ψに含まれるε組を取得し、結果をＰεに代入する。５行目ではｆｎｕｍ（ｘ'，Ｐε）（図１１）を最小にするような、または十分に小さくするようなｘ'を計算し、それをε除去パターン配列ｘに代入する。ｘの全組み合わせを調べても良いし、一部だけを調べてもよい。
【０１３８】
６行目ではＣＵＥＣ-ε−ｒｅｍｏｖａｌ（ｘ，Ｐε）（図１３）により、５行目で求めたｘに基づいて処理対象のＦＳＡからε遷移を除去する。
【０１３９】
全ての連結無向ε閉包について４行目から６行目の処理が完了すると、第１の実施の形態のε除去が完了することになる。
【０１４０】
（処理例）
次に、従来法と第１の実施の形態による処理例について説明する。図１５は、この例で用いるε除去前のＦＳＡを示す図である。太線の円が初期状態であり、ここでは状態１である。２重線の円が終了状態であり、ここでは状態６である。各遷移の近傍に書かれている文字が割り当てられている入力記号である。ε遷移を除去する前の遷移の総数は１０本である。
【０１４１】
図１６は、従来法によってε除去を行った結果を示す図である。図１６に示すように、従来法でε除去を行った後の遷移の総数は９本である。
【０１４２】
図１７は、遷移の向きを反転させた後に従来法によってε除去を行った結果を示す図である。すなわち、図１７は、遷移の向きを反転させた後、初期状態と終了状態を入れ替えた後に従来法によるε除去を行い、遷移の向きを元の向きに戻し、初期状態と終了状態も元に戻した場合のＦＳＡを表す。図１７に示すように、この場合のε除去後の遷移の総数は１０本である。
【０１４３】
図１８は、第１の実施の形態で述べた方法によってε除去を行った結果を示す図である。図１８に示すように、第１の実施の形態の方法でε除去を行った後の遷移の総数は８本である。
【０１４４】
以下、擬似コードを用いて具体的な処理手順を説明する。
【０１４５】
処理は、図１４の１行目の擬似コードから開始する。１行目では関数ａｌｌ−ｕｎｄｉｒｅｃｔｅｄ−ε−ｃｌｏｓｕｒｅを用いて無向ε閉包を全て求める。この結果、Θ＝｛｛１，３｝，｛２，４｝，｛５，６，７｝｝が得られる。このΘを入力として、さらに関数ａｌｌ−ＣＵＥＣにより連結無向ε閉包が得られる。すなわち、Ψ＝｛｛｛１，３｝，｛２，４｝，｛５，６，７｝｝｝が得られる。この例の場合、全ての状態が１つの連結無向ε閉包に含まれることになる。したがって、図１４の４行目から６行目は状態の集合｛｛１，３｝，｛２，４｝，｛５，６，７｝｝で構成される連結無向ε閉包に対してのみ実行されることになる。４行目で全てのε組を取得する。その結果、Ｐε＝｛（１，３），（２，４），（５，６），（５，７）｝が得られる。
【０１４６】
１番目の組を（１，３）、２番目の組を（２，４）、３番目の組を（５，６）、４番目の組を（５，７）とすると、ｆｎｕｍを最も小さくするε除去パターン配列の１つはｘ＝０１１１となる。これは、ｘ１＝０、ｘ２＝１、ｘ３＝１、ｘ４＝１であることを意味する。このε除去パターン配列に基づいて５行目で実際にε遷移を除去し、必要な遷移を生成する。
【０１４７】
ε除去では、図１３の３行目から１２行目を各状態について処理していけばよい。Ｑε＝｛１，２，３，４，５，６，７｝である。最後に１３行目でＱやＥにε除去の結果を反映させる。
【０１４８】
ｑ＝１の場合について述べる。このとき、３行目の結果はＥｉｎ＝φ、Ｅｏｕｔ＝｛（１，ｂ，２）｝、ｂｉｎｉｔｉａｌ＝ｔｒｕｅ、ｂｆｉｎａｌ＝ｆａｌｓｅとなる。４行目の２番目の条件を満たすので、５行目を実行するが、Ｅｎｅｗは変化しない。追加される遷移や状態は既に元のＦＳＡに含まれているからである。８行目の条件を満たすが、元々状態１はＩｎｅｗに含まれているので９行目を実行してもＩｎｅｗに変化はない。１２行目でε遷移（１、ε、３）をＥｎｅｗから除去する。
【０１４９】
ｑ＝２の場合について述べる。このとき、３行目の結果はＥｉｎ＝｛（１，ｂ，２）｝、Ｅｏｕｔ＝｛（２，ａ，５）｝、ｂｉｎｉｔｉａｌ＝ｆａｌｓｅ、ｂｆｉｎａｌ＝ｆａｌｓｅとなる。４行目の１番目の条件を満たすので５行目により、Ｅｎｅｗに遷移（２，ａ，５）が追加される。（１，ｂ，２）は元のＦＳＡに含まれている。１２行目でε遷移（２，ε，４）をＥｎｅｗから除去する。
【０１５０】
ｑ＝３の場合について述べる。このとき、３行目の結果はＥｉｎ＝｛（５，ｃ，３）｝、Ｅｏｕｔ＝｛（３，ａ，５）｝、ｂｉｎｉｔｉａｌ＝ｔｒｕｅ、ｂｆｉｎａｌ＝ｆａｌｓｅとなる。４行目の１番目と２番目の条件を満たすので、５行目で（５，ｃ，３）、（３，ａ，５）が追加されるが元々存在しているので、Ｅｎｅｗに変化はない。８行目の条件も満たすので９行目を実行すると、状態３が初期状態に追加される。
【０１５１】
ｑ＝４の場合について述べる。このとき、３行目の結果はＥｉｎ＝φ、Ｅｏｕｔ＝｛（４，ａ，５）｝、ｂｉｎｉｔｉａｌ＝ｆａｌｓｅ、ｂｆｉｎａｌ＝ｆａｌｓｅとなる。４行目の条件を満たさないので７行目を実行するとＥｎｅｗから遷移（４，ａ，５）が除去され、Ｑｎｅｗから状態４が除去される。
【０１５２】
ｑ＝５の場合について述べる。このとき、３行目の結果はＥｉｎ＝｛（３，ａ，５），（４，ａ，５）｝、Ｅｏｕｔ＝｛（５，ｃ，３），（５，ａ，７），（５，ｂ，６）｝、ｂｉｎｉｔｉａｌ＝ｆａｌｓｅ、ｂｆｉｎａｌ＝ｔｒｕｅとなる。４行目の条件を満たすので、Ｅｉｎ、ＥｏｕｔをＥｎｅｗに追加する。既に存在する遷移もあるが、新たにＥｎｅｗに追加される遷移は（５，ａ，７）と（５，ｂ，６）である。１０行目の条件も満たすので、状態５はＦｎｅｗに追加され、終了状態となる。１２行目で遷移（５，ε，６）と（５，ε，７）をＥｎｅｗから削除する。
【０１５３】
ｑ＝６の場合について述べる。このとき、３行目の結果はＥｉｎ＝｛（７，ｂ，６）｝、Ｅｏｕｔ＝｛（６，ａ，７）｝、ｂｉｎｉｔｉａｌ＝ｆａｌｓｅ、ｂｆｉｎａｌ＝ｔｒｕｅとなる。４行目の条件を満たすので、ＥｉｎとＥｏｕｔをＥｎｅｗに追加するが、Ｅｎｅｗに既に存在するので新たに追加される遷移はない。
【０１５４】
ｑ＝７の場合について述べる。このとき、３行目の結果はＥｉｎ＝｛（６，ａ，７）｝、Ｅｏｕｔ＝｛（７，ｂ，６）｝、ｂｉｎｉｔｉａｌ＝ｆａｌｓｅ、ｂｆｉｎａｌ＝ｆａｌｓｅとなる。４行目の条件を満たすので、ＥｉｎとＥｏｕｔをＥｎｅｗに追加するが、Ｅｎｅｗに既に存在するので新たに追加される遷移はない。
【０１５５】
最後に１３行目でＥｎｅｗに含まれる遷移のうち前状態と次状態がＱｎｅｗに含まれる遷移をＥに代入し、Ｑｎｅｗ、Ｉｎｅｗ、ＦｎｅｗをそれぞれＱ、Ｉ、Ｆに代入すれば、第１の実施の形態によるε除去が完了し、図１８のような結果が得られる。
【０１５６】
次に、第１の実施の形態の情報処理装置１００のハードウェア構成について説明する。図１９は、第１の実施の形態の情報処理装置１００のハードウェア構成例を示すブロック図である。
【０１５７】
図１９に示されるように、情報処理装置１００は、ＣＰＵ（Central  Processing  Unit）１、操作部２、表示部３、ＲＯＭ（Read  Only  Memory）４、ＲＡＭ（Random  Access  Memory）５、記憶部６、およびバス７等を備えている。各部はバス７により接続されている。
【０１５８】
ＣＰＵ１は、ＲＡＭ５の所定領域を作業領域として、ＲＯＭ４または記憶部６に予め記憶された各種制御プログラムとの協働により各種処理を実行し、情報処理装置１００を構成する各部（第１集合生成部、第２集合生成部、組み合わせ生成部、除去部等）の動作を統括的に制御する。またＣＰＵ１は、ＲＯＭ４または記憶部６に予め記憶された所定のプログラムとの協働により各部の機能を実現させる。
【０１５９】
操作部２は、マウスやキーボード等の入力デバイスであって、ユーザから操作入力された情報を指示信号として受け付け、その指示信号をＣＰＵ１に出力する。
【０１６０】
表示部３は、ＬＣＤ（Liquid  Crystal  Display）等の表示装置により構成され、ＣＰＵ１からの表示信号に基づいて、各種情報を表示する。
【０１６１】
ＲＯＭ４は、情報処理装置１００の制御にかかるプログラムや各種設定情報等を書き換え不可能に記憶する。
【０１６２】
ＲＡＭ５は、ＳＤＲＡＭ等の揮発性の記憶媒体であって、ＣＰＵ１の作業エリアとして機能する。具体的には、ε除去処理時において生成される各種変数やパラメータの値等を一時記憶するバッファ等の役割を果たす。
【０１６３】
記憶部６は、フラッシュメモリ等の半導体による記憶媒体や、磁気的または光学的に記録可能な記憶媒体を有し、情報処理装置１００の制御にかかるプログラムや各種設定情報等を書き換え可能に記憶する。また記憶部７は、ＦＳＡに係る各種の情報を予め記憶したり、ε除去処理の処理結果であるＦＳＡを記録したりする。
【０１６４】
第１の実施の形態にかかる情報処理装置で実行されるプログラムは、インストール可能な形式または実行可能な形式のファイルでＣＤ−ＲＯＭ（Compact  Disk  Read  Only  Memory）、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ（Compact  Disk  Recordable）、ＤＶＤ（Digital  Versatile  Disk）等のコンピュータで読み取り可能な記録媒体に記録されてコンピュータプログラムプロダクトとして提供される。
【０１６５】
また、第１の実施の形態にかかる情報処理装置で実行されるプログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成してもよい。また、第１の実施の形態にかかる情報処理装置で実行されるプログラムをインターネット等のネットワーク経由で提供または配布するように構成してもよい。
【０１６６】
また、第１の実施の形態のプログラムを、ＲＯＭ等に予め組み込んで提供するように構成してもよい。
【０１６７】
なお、後述する第２および第３の実施の形態の情報処理装置のハードウェア構成も図１９と同様である。また、第２および第３の実施の形態の情報処理装置で実行されるプログラムも上記説明と同様の構成で同様の手法により提供される。
【０１６８】
以上のように、第１の実施の形態にかかる情報処理装置では、ε除去パターンの選択の結果が影響する状態の範囲（連結無向ε閉包）を求め、求めた連結無向ε閉包ごとにε除去を実行する。連結無向ε閉包は、ε遷移の向きに依存せずに探索される。このため、ε除去の向きに対する依存性がなくなり、元の遷移の向きでε除去を行うか、元の遷移の向きとは逆向きにε除去を行うかを選ぶ必要がなくなる。さらに、従来の方法と同じかそれよりも少ない数の遷移で構成される有限状態オートマトンを得ることができる。
【０１６９】
（第２の実施の形態）
第２の実施の形態では、重み付き有限状態オートマトン（ＷＦＳＡ）に現れるε遷移を除去する方法を説明する。ここでいうε遷移とは、入力記号がεであるような遷移のことを言う。ＷＦＳＡは、ある記号列が入力されるとその記号列を受理するか否かを判定し、さらに受理する場合はその重みを出力する機能を持つ。出力される重みは、入力される記号列に対応する経路上にある重みを、次に説明する一定の規則で計算することで求められる。
【０１７０】
記号列ｘの入力に対応する経路のうちｉ番目の経路をπｉとする。経路πは１または複数の遷移で構成され、それぞれの遷移を初期状態から到達できる順にｅ１、ｅ２、・・・、ｅｎとする。遷移ｅｉの重みをｗ（ｅｉ）とし、経路πの重みをｗ（π）＝ｗ（ｅ１）（×）ｗ（ｅ２）（×）・・・（×）ｗ（ｅｎ）であるとする。記号列ｘに対応する重みはｗ（ｘ）＝ｗ（π１）（＋）ｗ（π２）（＋）・・・（＋）ｗ（πｎ）とする。すなわち、全ての経路の重みを（＋）で演算した結果とする。
【０１７１】
ここで、演算（＋）には例えばｍｉｎやｍａｘなどの演算を用いることができる。また、演算（×）には例えば＋（加算）や×（乗算）などを用いることができる。任意の重みｃに対して１＃をｃ（×）１＃＝１＃（×）ｃ＝ｃを満たす値であると定義する。例えば（×）が＋の場合は１＃は０であり、（×）が×である場合は１＃は１である。すなわち、１＃は、任意の状態間を結ぶ経路上の重みの計算をするときにその値がなかったとしても計算結果が変化しない値（特定値）である。
【０１７２】
このような重みの演算を一般化するこのような手法についてはＭｅｈｒｙａｒ  Ｍｏｈｒｉ,“Ｓｅｍｉｒｉｎｇ  Ｆｒａｍｅｗｏｒｋｓ  ａｎｄ  Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  Ｓｈｏｒｔｅｓｔ−ｄｉｓｔａｎｃｅ  Ｐｒｏｂｌｅｍｓ”（Ｊｏｕｒｎａｌ  ｏｆ  Ａｕｔｏｍａｔａ，Ｌａｎｇｕａｇｅｓ  ａｎｄ  Ｃｏｍｂｉｎａｔｏｒｉｃｓ，２００２，ｖｏｌ．７，ｐｐ．３２１−３５０）に詳しい記載がある。
【０１７３】
ε遷移上に１＃以外の値が割り当てられているときにε遷移を取り除くと、取り除いたε遷移を含む経路に対応する記号列を入力したときに得られる重みが変化する。したがって、第１の実施の形態で説明した方法を用いてε遷移を除去するためには、事前にε遷移上の重みが１＃になるようにＷＦＳＡを変形する必要がある。
【０１７４】
図２０は、第２の実施の形態にかかる情報処理装置２００の構成の一例を示すブロック図である。図２０に示すように、情報処理装置２００は、変更部２０５と、第１集合生成部１０１と、第２集合生成部１０２と、組み合わせ生成部２０３と、除去部２０４と、を備えている。
【０１７５】
第２の実施の形態では、変更部２０５を追加したこと、および、組み合わせ生成部２０３と除去部２０４の機能が第１の実施の形態と異なっている。その他の構成および機能は、第１の実施の形態にかかる情報処理装置１００の構成を表すブロック図である図１と同様であるので、同一符号を付し、ここでの説明は省略する。
【０１７６】
変更部２０５は、ＷＦＳＡに含まれる任意の状態間を結ぶ経路に含まれるε遷移の重みを特定値１＃となるように変更する。組み合わせ生成部２０３は、重みを考慮して遷移数を評価する点が第１の実施の形態の組み合わせ生成部１０３と異なる。除去部２０４は、重みを考慮してε除去を実行する点が、第１の実施の形態の除去部１０４と異なる。
【０１７７】
（方法）
次に、このように構成された第２の実施の形態にかかる情報処理装置２００によるε除去処理について説明する。上記の理由により、ＷＦＳＡの場合には、全てのε遷移上にある重みが１＃になるようにＷＦＳＡを変形した後、第１の実施の形態と同様の方法によってε遷移を除去する。
【０１７８】
（重みの移動）
ε遷移上に重みができる限り残らないように（ε遷移上の重みができる限り１＃になるように）ε遷移の前後に重みを移動させる。図２１は、重みを移動させる方法の擬似コード（ｐｕｓｈ−ｗｅｉｇｈｔ）の一例を示す図である。なお、図中の丸印の中に＋を含む記号は上述の（＋）に相当し、丸印の中に×を含む記号は上述の（×）に相当する。重みが小さいほうが良い経路の場合は、（＋）をｍｉｎで、（×）を＋で、１＃を０であるとして処理すれば良い。重みが大きいほうが良い経路の場合は、（＋）をｍａｘで、（×）を＋で、１＃を０であるとして処理すればよい。
【０１７９】
１行目ではＰεに含まれている状態の２つ組のうち、１つ目の状態を集めてＱｓに代入する。同様に２つ目の状態を集めてＱｄに代入する。また、Ｗを空集合で初期化する。
【０１８０】
２行目はＱｓに含まれる状態をｑｓとし、Ｑｓに含まれる各状態について３行目から１５行目を処理することを表している。
【０１８１】
３行目ではＰεに含まれる状態の２つ組のうち、１つ目の状態がｑｓであるような２つ目の状態を集め、Ｑｎに代入する。これは、ｑｓからε経路を順方向にたどることで到達できる状態の集合を取得することに等しい。
【０１８２】
４行目ではｑｓからＱｎに含まれる各々の状態までのε経路のうちの最良経路の重みを関数ε−ｄｉｓｔａｎｃｅによって計算し、その結果をＷ’に代入する。Ｗ'の要素は３つ組（ε経路の最初の状態、ε経路の最後の状態、ε経路上の重み）である。ここでは３つ組の１番目の状態はｑｓであり、２番目の状態はＱｎに含まれる状態のいずれかである。３番目は、１番目の状態と２番目の状態間のε経路のうちの最良経路の重みである。
【０１８３】
ε−ｄｉｓｔａｎｃｅは良く知られているダイクストラのアルゴリズムによって計算することができる。また、上述のＭｏｈｒｉの文献に記載されている１つの状態からの最短距離問題（ｓｉｎｇｌｅ−ｓｏｕｒｃｅ  ｓｈｏｒｔｅｓｔ−ｄｉｓｔａｎｃｅ  ｐｒｏｂｌｅｍ）を解く一般的な方法によっても計算することができる。
【０１８４】
５行目では状態ｑｓに入ってくるε遷移が存在するか、または、状態ｑｓが終了状態であれば、６行目でＷ'をＷに追加する。そうでなければ、８行目に進む。
【０１８５】
８行目では４行目で得られた３つ組の３番目の値である重み全てと状態ｑｓから出て行く遷移のうちε遷移でない遷移の重み全てとを（＋）で演算し、その結果をｗに代入する。ここで、ｗｅｉｇｈｔ（ｅ）は遷移ｅに割り当てられている重みである。（＋）がｍｉｎなら、これらの重みのうち最も小さい値が得られることになる。
【０１８６】
９行目では、Ｗ'に含まれる３つ組の３番目に記録されている重みとｗｍ−１とを（×）演算で処理した値を新たな３番目の値とする３つ組をＷに追加する。（＋）がｍａｘで（×）が＋であるか、または、（＋）がｍｉｎで（×）が＋である場合、ｙ−１は−ｙと等しい。例えば、ｗｍが２でｗが３の場合、ｗｍ−１（×）ｗ＝−ｗｍ＋ｗ＝−２＋３＝１になる。
【０１８７】
１０行目と１１行目では、ｑｓから出て行く遷移のうちε遷移を除く遷移の重みｗを、ｗｍ−１とｗを（×）によって演算した結果に置き換える処理を行う。
【０１８８】
１２行目と１３行目では、ｑｓに入ってくる遷移のうちε遷移を除く遷移の重みｗをｗとｗｍを（×）によって演算した結果に置き換える処理を行う。例えば、ｑｓに入ってくる遷移ｅの重みが１０で、ｗｍが２であり、（×）を＋としているのであれば、この処理の完了後は、遷移ｅの重みは１２となる。
【０１８９】
１４行目と１５行目では、状態ｑｓが初期状態である場合に状態ｑｓの初期重みλ（ｑｓ）をλ（ｑｓ）（×）ｗｍに置き換える。
【０１９０】
２行目から１５行目の処理の結果、ε遷移に割り当てられている重みが遷移の向きとは逆向きの方向に押し出されることになる。
【０１９１】
１６行目はＱｄに含まれる状態をｑｄとし、Ｑｄに含まれる各状態について１７行目から２５行目の処理を行うことを表している。
【０１９２】
１７行目ではＷに含まれる３つ組のうち、２番目に記録されている状態がｑｄであるような３つ組の３番目に記録されている重み全てと、状態ｑｄに入ってくる遷移のうちε遷移でない遷移に割り当てられている重み全てを（＋）で演算し、ｗｍに代入する。
【０１９３】
１８行目と１９行目ではＷに含まれる３つ組のうち、２番目に記録されている状態がｑｄであるような３つ組の３番目に記録されている重みｗをｗ（×）ｗｍ−１によって得られる値に置き換える。
【０１９４】
２０行目と２１行目では、ε遷移でないｑｄに入ってくる遷移の重みｗをｗ（×）ｗｍ−１で得られる値に置き換える。
【０１９５】
２２行目と２３行目では、ε遷移でないｑｄから出て行く遷移の重みｗをｗｍ（×）ｗで得られる値に置き換える。
【０１９６】
２４行目と２５行目では、状態ｑｄが終了状態である場合に状態ｑｄの終了重みρ（ｑｄ）をｗｍ（×）ρ（ｑｄ）に置き換える。
【０１９７】
１６行目から２５行目の処理の結果、ε遷移に割り当てられている重みが遷移の向きに押し出されることになる。
【０１９８】
２６行目では、Ｗに含まれる３つ組の３番目に記録されている重みが１＃である３つ組をＷから取り除く。
【０１９９】
２７行目で１行目から２６行目の処理によって得られたＷをこの処理の結果として返す。
【０２００】
図２１に示すｐｕｓｈ−ｗｅｉｇｈｔだけではε経路上の重みが全て１＃になるとは限らない。そこで、ε経路上の重みを全て１＃にするために、重みが残っているε経路ごとに新たに状態と遷移を追加する。追加の方法は２種類存在する。１つはε経路の前の状態とその状態へ入ってくる遷移を複製して、ε遷移上の重みを割り当てる方法である。もう１つはε経路による次の状態とその状態から出て行く遷移を複製して、ε遷移上の重みを割り当てる方法である。前者の方法をプッシュパターン０と呼び、後者の方法をプッシュパターン１と呼ぶ。この２つを総称してプッシュパターンと呼ぶ。
【０２０１】
図２２は、プッシュパターンの一例を示す図である。図２２中の個々の遷移の付近にあるスラッシュで分けられて記載されている部分のスラッシュの左側がその遷移に割り当てられた入力記号であり、スラッシュの右側が重みである。
【０２０２】
図２３は、ε除去パターン配列ｘの一例を示す図である。いずれのプッシュパターンを用いるかを表す０と１の列を、第１の実施の形態におけるε除去パターン配列ｘに付け加える。すると、図２３のようにε除去パターン配列ｘは、ε除去用のε除去パターンを記述した部分と重みの処理用のプッシュパターンを記述した部分とに分かれる。
【０２０３】
したがって、組み合わせ生成部２０３が遷移数の評価に用いる関数ｆｎｕｍ（ｘ，Ｐε）は第１の実施の形態とは異なることになる。一方で組み合わせの探索に関しては第１の実施の形態と同様に行うことができる。以下では、第２の実施の形態の組み合わせ生成部２０３が関数ｆｎｕｍの代わりに用いる関数を関数ｇｎｕｍ（ｘ，Ｐε，Ｗ）と表す。ここで、Ｗは図２１に示すｐｕｓｈ−ｗｅｉｇｈｔが処理結果として返す集合である。図２４は、関数ｇｎｕｍの擬似コードの一例を示す図である。図２５は、関数ｇｎｕｍで用いられる関数ｍａｋｅ−ｐａｔｈの擬似コードの一例を示す図である。
【０２０４】
図２４の１行目ではｘとＰεとＷに基づいて新たな状態と遷移が生成される。生成された状態と遷移がそれぞれＱｎｅｗとＥｎｅｗに代入される。そのうち、初期状態はＩｎｅｗに代入され、終了状態はＦｎｅｗに代入される。新たな状態と遷移が生成されるため、ε組が変化する。変化したε組がＰε'に代入される。
【０２０５】
２行目から５行目の処理は、１行目で生成した状態や遷移を追加したＷＦＳＡからε除去後の遷移の数を取得する処理である。具体的には次のとおりである。
【０２０６】
２行目では、処理対象であるＷＦＳＡに含まれる状態、遷移、初期状態、終了状態をそれぞれ、Ｑｏｌｄ、Ｅｏｌｄ、Ｉｏｌｄ、Ｆｏｌｄに記録する。
【０２０７】
３行目ではＱｎｅｗ、Ｅｎｅｗ、Ｉｎｅｗ、Ｆｎｅｗをそれぞれ、処理対象であるＷＦＳＡの状態の集合Ｑ、遷移の集合Ｅ、初期状態の集合Ｉ、終了状態の集合Ｆに追加する。
【０２０８】
４行目では第１の実施の形態で用いた関数ｆｎｕｍによってε除去後の遷移の数を取得し、それをＮに代入する。
【０２０９】
５行目では、２行目で保存したＱｏｌｄ、Ｅｏｌｄ、Ｉｏｌｄ、Ｆｏｌｄを用いて元のＷＦＳＡに戻す。
【０２１０】
６行目では、１行目から５行目の処理で得られた遷移の数Ｎを処理の結果として返す。
【０２１１】
次に、図２５の関数ｍａｋｅ−ｐａｔｈについて説明する。図２５の１行目ではＱｎｅｗとＥｎｅｗを空集合として初期化する。
【０２１２】
２行目は３行目から１５行目の処理についてｉ＝１から｜ｘ｜−｜Ｐε｜まで繰り返し処理することを表している。
【０２１３】
３行目ではＷのｉ番目の要素であるｗｉに記録されている３つ組の１番目をｑｓに２番目をｑｄに３番目をｗに代入する。
【０２１４】
４行目ではＱに含まれていない新しい状態を作成し、ｑｎｅｗに代入する。
【０２１５】
５行目では４行目で作成した新しい状態ｑｎｅｗをＱｎｅｗに追加する。
【０２１６】
６行目ではｘのｉ＋｜Ｐε｜番目の値が０か否かを判定し、０なら７行目へ進む。０以外なら１２行目へ進む。
【０２１７】
７行目から１０行目ではプッシュパターン０に基づいて遷移の生成とε組の変更などを行う。
【０２１８】
７行目では状態ｑｓに入ってくる遷移のうち、ε遷移でない遷移を状態ｑｎｅｗに入ってくる遷移として複製する。このとき重みをｗｅからｗｅ（×）ｗに置き換える。
【０２１９】
８行目では不要になるε組（ｑｓ，ｑｄ）をＰεから取り除き、新たにε組（ｑｎｅｗ、ｑｄ）を追加する。
【０２２０】
９行目でｑｓが初期状態か否かを判定し、初期状態であれば１０行目でｑｎｅｗをＩｎｅｗに追加し、ｑｎｅｗの初期重みをｑｓの初期重みとｗを（×）で演算した結果にする。
【０２２１】
１２行目から１５行目はプッシュパターン１に基づいて遷移の生成とε組の変更などを行う。
【０２２２】
１２行目では状態ｑｄから出て行く遷移のうち、ε遷移でない遷移を状態ｑｎｅｗから出て行く遷移として複製する。このとき重みをｗｅからｗ（×）ｗｅに置き換える。
【０２２３】
１３行目では不要になるε組（ｑｓ，ｑｄ）をＰεから取り除き、新たにε組（ｑｓ，ｑｎｅｗ）を追加する。
【０２２４】
１４行目でｑｄが終了状態か否かを判定し、終了状態であれば１５行目でｑｎｅｗをＦｎｅｗに追加し、ｑｎｅｗの終了重みをｗとｑｄの終了重みを（×）で演算した結果にする。
【０２２５】
１６行目では１行目から１５行目の処理の結果として、５つ組（Ｑｎｅｗ，Ｅｎｅｗ，Ｉｎｅｗ，Ｆｎｅｗ，Ｐε）を返す。
【０２２６】
（ＷＦＳＡに含まれる全てのε遷移を除去する方法）
以上で説明した方法を組み合わせることで、ＷＦＳＡに含まれるε遷移を全て除去することができる。図２６は、ＷＦＳＡに含まれるε遷移を全て除去する方法の擬似コード（ＷＦＳＡ−ＤＩ−ε−ｒｅｍｏｖａｌ）の一例を示す図である。
【０２２７】
１行目では第１の実施の形態と同様に、ａｌｌ−ｕｎｄｉｒｅｃｔｅｄ−ε−ｃｌｏｓｕｒｅ（）（図３）により、無向ε閉包を計算し、その結果をΘに代入する。
【０２２８】
２行目でａｌｌ−ＣＵＥＣ（Θ）（図５）により、連結無向ε閉包を計算し、その結果をΨに代入する。
【０２２９】
３行目はΨに含まれる連結無向ε閉包ψの各々について４行目から９行目までを処理することを表している。
【０２３０】
４行目では第１の実施の形態と同様に、ε組を求め、Ｐεに代入する。
【０２３１】
５行目では、ε組Ｐεを第１引数として図２１の方法を用いることによってε遷移上の重みをできる限り前後のε遷移でない遷移に移動させる。さらに、重みの移動後のε組の状態間を結ぶε経路のうち最良経路の重みがその経路の最初の状態と最後の状態と共に３つ組として得られる。その３つ組から構成される集合がＷに代入される。
【０２３２】
６行目では、長さが｜Ｐε｜＋｜Ｗ｜であるようなε除去パターン配列ｘ'の内容を様々に変えることで関数ｇｎｕｍが最も小さくなるｘ'を見つけ、それをｘに代入する。第１の実施の形態のときと同様、全てのｘの組み合わせを探索することもできるし、一部のみの探索にとどめておくこともできる。第１の実施の形態と同様、どこを探索するかは一般的な組み合わせ最適化の方法を用いればよい。例えば遺伝的アルゴリズムを適用できる。全てが０か全てが１の２通りのみを調べるだけにすることもできる。
【０２３３】
７行目では６行目で得られたｘに基づいて図２５の関数ｍａｋｅ−ｐａｔｈによって得られる新たな状態の集合と遷移の集合、初期状態の集合、終了状態の集合をそれぞれＱｎｅｗ、Ｅｎｅｗ、Ｉｎｅｗ、Ｆｎｅｗに代入する。また、それに伴うＰεの変更も行う。
【０２３４】
８行目では７行目で得られたＱｎｅｗ、Ｅｎｅｗ、Ｉｎｅｗ、ＦｎｅｗをそれぞれＱ、Ｅ、Ｉ、Ｆに追加する。
【０２３５】
９行目では、８行目で状態や遷移を追加したＷＦＳＡのε遷移をｘとＰεに基づいて除去し、それに伴う必要な変形を行う。これは第１の実施の形態と同じである。ただし、初期重みと終了重みの処理が追加される（詳細は後述）。以上の処理により、ＷＦＳＡのε遷移を除去することができる。
【０２３６】
次に、図２６の９行目で用いる関数ＷＦＳＡ−ＣＵＥＣ−ε−ｒｅｍｏｖａｌの詳細について図２７を用いて説明する。図２７は、ε除去の擬似コード（ＷＦＳＡ−ＣＵＥＣ-ε−ｒｅｍｏｖａｌ）の一例を示す図である。
【０２３７】
３行目で得られる戻り値に初期重みと終了重みの項目が追加され、その値を用いて９行目で初期重みの設定を、１１行目で終了重みの設定を行うように追加される。さらに１行目と１３行目にも初期重みと終了重みに関する処理が追加される。１行目には、初期状態ｑ∈Ｉに対応する初期重みλ（ｑ）をλｎｅｗ（ｑ）に代入し、同様に終了状態ｑ∈Ｆに対応する初期重みρ（ｑ）をρｎｅｗ（ｑ）に代入する処理が追加される。１３行目には、初期状態ｑ∈Ｉｎｅｗに対応する初期重みλｎｅｗ（ｑ）をλ（ｑ）に、終了状態ｑ∈Ｆｎｅｗに対応する終了重みρｎｅｗ（ｑ）をρ（ｑ）に代入する処理が追加される。その他は、第１の実施の形態のε除去の擬似コードである図１３のＣＵＥＣ-ε−ｒｅｍｏｖａｌと同様であるため説明を省略する。
【０２３８】
図２８は、図２７の３行目で使用される関数ＷＦＳＡ−ｍａｋｅ−ｔｒａｎｓｉｔｉｏｎの擬似コードの一例を示す図である。図２８は、図１２の関数ｍａｋｅ−ｔｒａｎｓｉｔｉｏｎに以下のような処理を追加している。
【０２３９】
１行目では初期重みと終了重みの処理を追加している。λｑに状態ｑの初期重みを、ρｑに状態ｑの終了重みを代入している。状態ｑが初期状態でない場合において、（＋）にｍｉｎ、（×）に＋を使うときは∞を、（＋）にｍａｘ、（×）に＋を使うときは−∞をλｑに代入する。状態ｑが終了状態でない場合も同様に扱う。
【０２４０】
９行目では最良の終了重みを計算する処理を、１６行目では最良の初期重みを計算する処理を加えている。また、１３行目と１７行目の戻り値にλｑとρｑを追加している。
【０２４１】
（処理例）
次に、従来法と第２の実施の形態による処理例について説明する。図２９は、この例で用いるε除去前のＷＦＳＡを示す図である。太線の円が初期状態であり、スラッシュの左側が状態番号を表し、右側が初期重みを表す。ここでは状態１と２が初期状態であり、それぞれ初期重みが２と５である。２重線の円が終了状態であり、スラッシュの左側が状態番号を表し、右側が終了重みを表す。ここでは状態６と７が終了状態であり、それぞれ終了重みが１と３である。各遷移の近傍に書かれている文字のうち、スラッシュの左側が割り当てられている入力記号であり、右側が割り当てられている重みである。ε遷移を除去する前の遷移の総数は９本である。
【０２４２】
第２の実施の形態による方法も従来法も、この例では（＋）をｍｉｎ、（×）を＋として重みの処理を行うこととする。
【０２４３】
図３０は、従来法によってε除去を行った結果を示す図である。図３０に示すように、従来法でε除去を行った後の遷移の総数は６本である。
【０２４４】
図３１は、遷移の向きを反転させた後に従来法によってε除去を行った結果を示す図である。すなわち、図３１は、遷移の向きを反転させた後、初期状態と終了状態を入れ替えた後に従来法によるε除去を行い、遷移の向きを元の向きに戻し、初期状態と終了状態も元に戻した場合のＷＦＳＡを表す。図３１に示すように、この場合のε除去後の遷移の総数は７本である。
【０２４５】
以下、第２の実施の形態によってε除去を行う場合について説明する。図２６の２行目で連結無向ε閉包が得られる。すなわち、Ψ＝｛｛｛２，３，４，５，６｝｝｝が得られる。この例の場合は、連結無向ε閉包は１つだけなので、それについて３行目から８行目を処理する。
【０２４６】
４行目でε組が得られる。すなわち、Ｐε＝｛（２，４），（２，５），（３，５），（３，６）｝が得られる。５行目でε遷移上の重みをできるだけ前後に移動させて、ε遷移上の重みをなくす。ただし、元のε遷移に割り当てられている重みは変更する必要はない。変更後の情報は戻り値を代入して得られるＷに記録されている。すなわち、Ｗ＝｛（３，５，１）｝となる。状態３と状態５のε経路に重みが１残っているが、それ以外の経路は重みが残っていないことを表している。図３２は、このようにして重みを移動した後のＷＦＳＡを示す図である。
【０２４７】
６行目で最も遷移の数が少なくなるｘが得られる。１番目の組を（２，４）、２番目の組を（２，５）、３番目の組を（３，５）、４番目の組を（３，６）とし、５番目に記録されるプッシュパターンに対応するＷの要素を（３，５，１）とする。この場合、関数ｇｎｕｍを最も小さくするε除去パターン配列の１つはｘ＝１１１１１となる。これは、ｘ１＝１、ｘ２＝１、ｘ３＝１、ｘ４＝１、ｘ５＝１であることを意味する。６行目と７行目で必要な状態と遷移を生成し、Ｐεを更新する。図３３は、この処理の後に得られるＷＦＳＡを示す図である。
【０２４８】
新しく生成された状態８には入ってくる遷移がないが、ε組として更新後のＰεに含まれているため次のε除去処理で問題になることはない。なお、更新後のＰεは｛（２，４），（２，５），（３，８），（３，６）｝となっている。最後に８行目で実際にε遷移を除去し、必要な遷移を生成する。図３４は、ε除去の最終結果を示す図である。
【０２４９】
このように、第２の実施の形態にかかる情報処理装置では、ＷＦＳＡのような入力記号以外の情報が遷移に割り当てられている有限状態オートマトンに対しても、遷移の方向に依存せずにε遷移の除去を行うことができる。さらに、従来法と同じかそれより少ない遷移のＷＦＳＡを得ることができる。
【０２５０】
（第３の実施の形態）
第３の実施の形態では、有限状態トランスデューサ（ＦＳＴ）のε遷移の除去方法を説明する。ＦＳＴの場合も第２の実施の形態の場合と同様に、全てのε遷移上にある文字列が空文字列（空記号）であるεになるようにＦＳＴを変形した後に第１の実施の形態の方法でε除去を行う。第２の実施の形態で用いた１＃がεに該当する。
【０２５１】
図３５は、第３の実施の形態にかかる情報処理装置３００の構成の一例を示すブロック図である。図３５に示すように、情報処理装置３００は、変更部３０５と、第１集合生成部１０１と、第２集合生成部１０２と、組み合わせ生成部３０３と、除去部３０４と、を備えている。
【０２５２】
第３の実施の形態では、変更部３０５、組み合わせ生成部３０３、および除去部３０４の機能が第２の実施の形態と異なっている。その他の構成および機能は、第２の実施の形態にかかる情報処理装置２００の構成を表すブロック図である図２０と同様であるので、同一符号を付し、ここでの説明は省略する。
【０２５３】
変更部３０５は、ＦＳＴに含まれる任意の状態間を結ぶ経路に含まれるε遷移の出力記号を空記号εとなるように変更する。組み合わせ生成部３０３は、重みの代わりに出力記号を用いて遷移数を評価する点が第２の実施の形態の組み合わせ生成部２０３と異なる。除去部３０４は、重みの代わりに出力記号を用いてε除去を実行する点が、第２の実施の形態の除去部２０４と異なる。
【０２５４】
（方法）
次に、このように構成された第３の実施の形態にかかる情報処理装置３００によるε除去処理について説明する。
【０２５５】
（文字列の移動）
第３の実施の形態では、まず、ε遷移上にある文字列ができる限り空文字列となるように文字列を移動させる。第２の実施の形態で説明した重みの移動処理（図２１のｐｕｓｈ−ｗｅｉｇｈｔ）と基本的には同じである。ただし、ε−ｄｉｓｔａｎｃｅの部分を次に説明するε−ｏｕｔｐｕｔに変更し、（＋）を前方最長一致演算とし、（×）を出力記号列の連結演算であるとする。この場合、例えば、ａｂ（＋）ａｃ＝ａ、ａ（×）ｂ＝ａｂ、ａ（×）ε＝ε（×）ａ＝ａのようになる。
【０２５６】
図３６は、文字列の移動方法の擬似コード（ｐｕｓｈ−ｏｕｔｐｕｔ）の一例を示す図である。
【０２５７】
１行目ではＰεに含まれている状態の２つ組のうち、１つ目の状態を集めてＱｓに代入する。同様に２つ目の状態を集めてＱｄに代入する。また、Ｏを空集合で初期化する。
【０２５８】
２行目はＱｓに含まれる状態をｑｓとし、Ｑｓに含まれる全ての状態について３行目から１５行目を処理することを表している。
【０２５９】
３行目は図２１と同様である。
【０２６０】
４行目ではｑｓからＱｎに含まれる各々の状態までのε経路にある出力記号を関数ε−ｏｕｔｐｕｔによって計算し、その結果をＯ'に代入する。Ｏ'の要素は３つ組（ε経路の最初の状態，ε経路の最後の状態，ε経路上の出力記号）である。ここでは３つ組の１番目の状態はｑｓであり、２番目の状態はＱｎに含まれる状態のいずれかである。３番目は、１番目の状態と２番目の状態間のε経路にある出力記号である。ε−ｏｕｔｐｕｔについては後述する。
【０２６１】
５行目と６行目では状態ｑｓに入ってくるε遷移が存在するか、または、ｑｓが終了状態であるとき、Ｏ'をＯに追加する。そうでないときは、８行目に進む。
【０２６２】
８行目では４行目で得られた３つ組の３番目の値である出力記号全てと状態ｑｓから出て行く遷移のうちε遷移でない遷移の出力記号全てとで前方最長一致演算を行い、その結果をｏｍに代入する。ここで、ｏｕｔｐｕｔ（ｅ）は遷移ｅに割り当てられている出力記号である。
【０２６３】
９行目では、Ｏ'に含まれる３つ組の３番目に記録されている出力記号とｏｍ−１とを（×）演算で処理した値を新たな３番目の値とする３つ組をＯに追加する。ｏｍ−１（×）ｏは、出力記号ｏの前方からｏｍを取り除く処理を表している。例えばｏｍ＝ａｂでｏがａｂｃなら、この処理の結果はｃになる。
【０２６４】
１０行目と１１行目では、ｑｓから出て行く遷移のうちε遷移を除く遷移の出力記号ｏの前方からｏｍを取り除いた出力記号に置き換える処理を行う。例えば、ｑｓから出て行く遷移ｅの出力記号がｂｃで、ｗｍがｂであれば、この処理の完了後は、遷移ｅの出力記号はｃとなる。
【０２６５】
１２行目と１３行目では、ｑｓに入ってくる遷移のうちε遷移を除く遷移の出力記号ｏをｏとｏｍをつなげた出力記号に置き換える処理を行う。例えば、ｑｓに入ってくる遷移ｅの出力記号がａで、ｗｍがｂであれば、この処理の完了後は、遷移ｅの出力記号はａｂとなる。
【０２６６】
１４行目と１５行目では、状態ｑｓが初期状態である場合に状態ｑｓの初期出力記号λｏ（ｑｓ）をλｏ（ｑｓ）（×）ｏｍで得られる出力記号に置き換える。
【０２６７】
１６行目はＱｄに含まれる状態をｑｄとし、Ｑｄに含まれる各状態のうちｑｄから出て行くε遷移がなくｑｄが初期状態でない場合について、１７行目から２６行目の処理を行うことを表している。
【０２６８】
１７行目ではＯに含まれる３つ組のうち、２番目に記録されている状態がｑｄであるような３つ組の３番目に記録されている出力記号全てと、状態ｑｄに入ってくる遷移のうちε遷移でない遷移に割り当てられている出力記号全てとを逆向きにしたうえで前方最長一致演算によって処理する。例えば出力記号にａｂｃとｂｂｃが存在するなら、ｏｍにはｃｂが代入されることになる。なお擬似コード中のｒｅｖは出力記号を逆向きにする関数である。
【０２６９】
１８行目から２０行目ではＯに含まれる３つ組のうち、２番目に記録されている状態がｑｄであるような３つ組の３番目に記録されている出力記号ｏを次の出力記号に置き換える。その出力記号とは、ｏを逆向きにして、前方からｏｍを取り除き、その結果の出力記号を逆向きにしたものである。
【０２７０】
２１行目と２２行目では、ε遷移でないｑｄに入ってくる遷移ｅの出力記号を逆向きにし、その前方からｏｍを取り除き、さらに逆向きにした結果を遷移ｅの新たな出力記号とする。
【０２７１】
２３行目と２４行目では、ε遷移でないｑｄから出て行く遷移ｅの出力記号を、その出力記号の前方にｏｍを逆向きにした出力記号をつなげた出力記号に置き換える。
【０２７２】
２５行目と２６行目では、状態ｑｄが終了状態である場合に状態ｑｄの終了出力記号ρｏ（ｑｄ）を、ｏｍを逆向きにした出力記号とρｏ（ｑｄ）とをつなげた出力記号に置き換える。
【０２７３】
２７行目では、Ｏに含まれる３つ組の３番目に記録されている出力記号がε、すなわち出力記号が空である３つ組をＯから取り除く。
【０２７４】
２８行目では１行目から２７行目の処理によって得られたＯをこの処理の結果として返す。
【０２７５】
次に、ε−ｏｕｔｐｕｔの詳細について説明する。ε−ｄｉｓｔａｎｃｅと異なり、ε−ｏｕｔｐｕｔは２つの状態間を結ぶε遷移のみで構成される経路上にある出力記号列の組み合わせ全てを計算する。図３７は、関数ε−ｏｕｔｐｕｔの擬似コードの一例を示す図である。
【０２７６】
１行目では後述する関数ε−ＤＦＳを呼び出し、その結果を状態の集合Ｑｏと遷移の集合Ｅｏに代入する。出力記号の集合Ｌも空集合に初期化する。
【０２７７】
２行目は、３行目から７行目の処理をＱｏに含まれる各々の状態ｑに対して処理することを表している。ただし、その処理順序は遷移の集合Ｅｏのみを使って計算したトポロジカル順であるとする。そうすることで、ある状態を処理するときには、ｑｓからその状態に到達するために通過する経路上にある状態については既に３行目から７行目の処理が完了していることが保証される。
【０２７８】
３行目は、Ｅｏに含まれる遷移のうち、ｑに入ってくるε遷移ｅについて４行目から７行目の処理を行うことを表している。
【０２７９】
４行目と５行目では、遷移ｅの前の状態に対応する出力記号の集合Ｌ（ｐ（ｅ））が空集合の場合、状態ｑに対応する出力記号の集合Ｌ（ｑ）に遷移ｅの出力記号を追加する。
【０２８０】
６行目は、遷移ｅの前状態に記録されている出力記号の集合Ｌ（ｐ（ｅ））に含まれる出力記号ｏについて７行目を処理することを表している。
【０２８１】
７行目では、出力記号ｏに遷移Ｅに割り当てられている出力記号をつなげた出力記号を状態ｑに割り当てられる出力記号Ｌ（ｑ）に追加する。
【０２８２】
８行目から１１行目では、７行目までで得られた結果を処理結果として返すための形式に変換する。その結果、集合Ｒには３つ組（ｑｓ，Ｑｄに含まれる状態のいずれか，出力記号）が要素として記録される。３つ組の３番目にはｑｓから２番目に記録されている状態までのε経路上の出力記号が記録されることになる。
【０２８３】
１２行目では、１１行目までの処理で得られた集合Ｒを処理結果として返す。
【０２８４】
次に、関数ε−ＤＦＳの詳細について説明する。この関数によって、第１引数で指定される状態を最初の状態とする全てのε経路上にある状態の集合と遷移の集合を得ることができる。図３８は、関数ε−ＤＦＳの擬似コードの一例を示す図である。
【０２８５】
１行目では状態の集合ＱｓとＱｏにｑを追加する。Ｅｏには空集合を代入する。
【０２８６】
２行目は、状態ｑから出て行くε遷移ｅについて３行目から７行目までの処理を行うことを表している。
【０２８７】
３行目では遷移ｅの次状態がＱｓに含まれているか否かを判定し、含まれていなければ４行目に処理を進める。
【０２８８】
４行目ではＥｏに遷移ｅを追加する。
【０２８９】
５行目では遷移ｅの次状態がＱｏに含まれているか否かを判定し、含まれていなければ６行目に処理を進める。
【０２９０】
６行目では関数ε−ＤＦＳを再帰的に呼び出す。引数は、遷移ｅの次状態とＱｓとＱｏである。得られた結果はＱｒとＥｒに代入する。
【０２９１】
７行目では６行目で得られたＱｒとＥｒをそれぞれＱｏとＥｏに追加する。
【０２９２】
８行目では、７行目までの処理で得られた結果としてＱｏとＥｏから成る２つ組を返す。
【０２９３】
（ＦＳＴに含まれる全てのε遷移を除去する方法）
ＦＳＴに含まれる全てのε遷移を除去するには、図２６の重みに関する処理を出力記号に関する処理に置き換えればよい。置き換える箇所を以下に説明する。１つは４行目のｐｕｓｈ−ｗｅｉｇｈｔをｐｕｓｈ−ｏｕｔｐｕｔに変更することである。それに伴いＷに記録されている３つ組の３番目が重みから出力記号に変わる。他には、初期状態ｑに対応する初期重みλ（ｑ）に対する処理を初期出力記号λｏ（ｑ）に変更する。また、終了状態ｑに対応する終了重みρ（ｑ）に対する処理を終了出力記号ρｏ（ｑ）に変更する。同様に図２５、図２７、図２８の重みに関する処理を出力記号に関する処理に置き換えればよい。
【０２９４】
（処理例）
次に、従来法と第３の実施の形態による処理例について説明する。図３９は、この例で用いるε除去前のＦＳＴを示す図である。太線の円が初期状態であり、スラッシュの左側が状態番号であり右側が初期出力記号である。ここでは状態１と２が初期状態であり、それぞれ初期出力記号がＡとεである。２重線の円が終了状態であり、スラッシュの左側が状態番号であり右側が終了出力記号である。ここでは状態６と７が終了状態であり、それぞれ終了出力記号がＢとεである。各遷移の近傍に書かれている文字のうち、コロンの左側が割り当てられている入力記号であり、右側が割り当てられている出力記号である。
【０２９５】
図４０は、従来法によってε除去を行った結果を示す図である。図４１は、遷移の向きを反転させた後に従来法によってε除去を行った結果を示す図である。すなわち、図４１は、遷移の向きを反転させ、出力記号も反転させ、初期状態と終了状態を入れ替えてから従来によるε除去を行い、遷移の向きを元の向きに戻し、初期状態と終了状態を再度入れ替えた場合のＦＳＴを表す。
【０２９６】
図４２は、第３の実施の形態によるε除去処理の結果を示す図である。この例では遷移の本数は従来法の結果を表す図４０と同じであるが、出力記号の割り当て方が異なっていることが分かる。
【０２９７】
（重み付き有限状態トランスデューサの場合）
重み付き有限状態トランスデューサの場合は、重みの移動と出力記号列の移動の両方を順に行った後、重みと出力記号の組を重みとみなして第２の実施の形態に記載のε除去処理を実行すればよい。
【０２９８】
このように、第３の実施の形態にかかる情報処理装置では、ＦＳＴおよびＷＦＳＴなどのように、入力記号以外の情報が遷移に割り当てられている場合であっても、遷移の方向に依存せずにε遷移の除去を行うことができる。さらに、遷移の数を従来の方法と同じかそれより少なくすることができる。
【０２９９】
なお、本発明は、上記実施の形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化することができる。また、上記実施の形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成することができる。例えば、実施の形態に示される全構成要素からいくつかの構成要素を削除してもよい。さらに、異なる実施の形態にわたる構成要素を適宜組み合わせても良い。
【符号の説明】
【０３００】
１００、２００、３００  情報処理装置
１０１  第１集合生成部
１０２  第２集合生成部
１０３、２０３、３０３  組み合わせ生成部
１０４  、２０４、３０４  除去部
２０５、３０５  変更部
３０５  変更部
【図１】
2011198126.tif 000003
【図２】
2011198126.tif 000004
【図３】
2011198126.tif 000005
【図４】
2011198126.tif 000006
【図５】
2011198126.tif 000007
【図６】
2011198126.tif 000008
【図７】
2011198126.tif 000009
【図８】
2011198126.tif 000010
【図９】
2011198126.tif 000011
【図１０】
2011198126.tif 000012
【図１１】
2011198126.tif 000013
【図１２】
2011198126.tif 000014
【図１３】
2011198126.tif 000015
【図１４】
2011198126.tif 000016
【図１５】
2011198126.tif 000017
【図１６】
2011198126.tif 000018
【図１７】
2011198126.tif 000019
【図１８】
2011198126.tif 000020
【図１９】
2011198126.tif 000021
【図２０】
2011198126.tif 000022
【図２１】
2011198126.tif 000023
【図２２】
2011198126.tif 000024
【図２３】
2011198126.tif 000025
【図２４】
2011198126.tif 000026
【図２５】
2011198126.tif 000027
【図２６】
2011198126.tif 000028
【図２７】
2011198126.tif 000029
【図２８】
2011198126.tif 000030
【図２９】
2011198126.tif 000031
【図３０】
2011198126.tif 000032
【図３１】
2011198126.tif 000033
【図３２】
2011198126.tif 000034
【図３３】
2011198126.tif 000035
【図３４】
2011198126.tif 000036
【図３５】
2011198126.tif 000037
【図３６】
2011198126.tif 000038
【図３７】
2011198126.tif 000039
【図３８】
2011198126.tif 000040
【図３９】
2011198126.tif 000041
【図４０】
2011198126.tif 000042
【図４１】
2011198126.tif 000043
【図４２】
2011198126.tif 000044