(57)【要約】【課題】事前処理なしに単値でないＮＦＳＴを決定化すること。【解決手段】有限状態トランスデューサが有する状態のうち、同一の入力記号により遷移する複数の状態を抽出して併合する状態併合部と、併合前の前記複数の状態のそれぞれから次の状態への遷移毎に対応する識別記号を、前記次の状態への入力記号として付与することにより決定化する記号決定部と、を有し、前記識別記号は、前記有限状態トランスデューサが有する遷移に割り当てられている入力記号とは異なる記号であることを特徴とする。【選択図】図２０
2010237806.tif 000002
【特許請求の範囲】
【請求項１】
有限状態トランスデューサが有する遷移に割り当てられている入力記号とは異なる記号である識別記号を生成する記号決定部と、
前記有限状態トランスデューサが有する状態のうち、同一の入力記号による遷移先にある一または複数の状態を抽出し、抽出した前記状態をサブ状態として有する状態を生成する状態併合部と、
前記状態併合部が生成する状態間の遷移の入力記号として、有限状態トランスデューサが有する遷移に割り当てられている入力記号または前記識別記号を付与することにより決定化する単値化処理部と、
を有することを特徴とする有限状態トランスデューサ決定化装置。
【請求項２】
前記識別記号が付与された入力による遷移先の状態を、前記サブ状態のそれぞれの遷移先の状態とする遷移生成制御部を有することを特徴とする請求項１記載の有限状態トランスデューサ決定化装置。
【請求項３】
前記遷移生成制御部は、前記サブ状態の次の状態から遷移する際の入力記号を、決定化前の前記次の状態に対応する入力記号とすることを特徴とする請求項２記載の有限状態トランスデューサ決定化装置。
【請求項４】
前記サブ状態から次の状態への出力記号は、空を含むことを特徴とする請求項２又は３記載の有限状態トランスデューサ決定化装置。
【請求項５】
前記状態併合部が生成した状態が有する一または複数のサブ状態からの遷移のうち、同一の入力記号により遷移する複数の遷移があり、かつ、前記複数の遷移による出力記号が複数あり、前記複数の遷移による遷移先の状態が同一の場合に、
前記状態併合部は、前記複数の遷移の遷移先の状態を生成し、
前記記号決定部は、前記複数の遷移毎に対応する識別記号を付与することを特徴とする請求項１記載の有限状態トランスデューサ決定化装置。
【請求項６】
前記記号決定部は、前記状態併合部が生成した状態と該状態への遷移の出力記号とを、該状態への遷移の識別記号に対応づけることを特徴とする請求項１記載の有限状態トランスデューサ決定化装置。
【請求項７】
前記記号決定部は、さらに、一の状態からの遷移毎に、前記識別記号を一意にすることを特徴とする請求項６記載の有限状態トランスデューサ決定化装置。
【請求項８】
前記記号決定部は、前記識別記号に対応付けられる状態毎、及び、出力記号毎、に、前記識別記号を一意にすることを特徴とする請求項６記載の有限状態トランスデューサ決定化装置。
【請求項９】
前記有限状態トランスデューサが、重み付き有限状態トランスデューサの場合に、
前記識別記号に対応する遷移のうち、重みに基づいて、最良の経路となる遷移を選択する遷移選択部を有することを特徴とする請求項１記載の有限状態トランスデューサ決定化装置。
【請求項１０】
有限状態トランスデューサが有する遷移に割り当てられている入力記号とは異なる記号である識別記号を生成する記号決定ステップと、
前記有限状態トランスデューサが有する状態のうち、同一の入力による遷移先にある一または複数の状態を抽出し、抽出した前記状態をサブ状態として有する状態を生成する状態併合ステップと、
前記状態併合ステップが生成する状態間の遷移の入力記号として、有限状態トランスデューサが有する遷移に割り当てられている入力記号または前記識別記号を付与することにより決定化する単値化ステップと、
を有することを特徴とする有限状態トランスデューサ決定化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，有限状態トランスデューサ決定化装置及び有限状態トランスデューサ決定化方法に関する。
【背景技術】
【０００２】
有限状態オートマトン（Ｆｉｎｉｔｅ  Ｓｔａｔｅ  Ａｕｔｏｍａｔｏｎ，ＦＳＡ）の一種である有限状態トランスデューサ（Ｆｉｎｉｔｅ  Ｓｔａｔｅ  Ｔｒａｎｓｄｕｃｅｒ，ＦＳＴ）は自然言語処理や音声認識等さまざまな分野で利用されている。形式的にはＦＳＴは６つ組（Ｑ，Σ，Δ，Ｅ，Ｉ，Ｆ）で表される。ここで，Ｑは状態の集合，Σは入力記号の集合，Ｅは遷移の集合，Ｉは初期状態の集合，Ｆは終了状態の集合，Δは出力記号の集合を表す。ＦＳＴにおける遷移ＥはＥ⊆Ｑ×Σ×Δ＊×Ｑである。Δ＊はΔのクリーネ閉包（Ｋｌｅｅｎｅ  ｃｌｏｓｕｒｅ）であり，空記号列εとΔの組み合わせで作成できる全ての記号列から成る集合である。ＦＳＴから出力記号を取り除くとＦＳＡとなる。またＦＳＴは一般順序機械（ｇｅｎｅｒａｌｉｚｅｄ  ｓｅｑｕｅｎｔｉａｌ  ｍａｃｈｉｎｅ）と呼ばれることがある。
【０００３】
ＦＳＴが非決定的（ｎｏｎｄｅｔｅｒｍｉｎｉｓｔｉｃ）であるとは，複数の経路に同一の入力記号列が割り当てられていることをいう。形式的には，集合Ｘのサイズ（要素の数）を｜Ｘ｜と表すこととし，状態ｑ∈Ｑから入力記号列ｗ∈Σ＊によって遷移することができる経路の集合をΠ（ｑ，ｗ）⊆Ｅ＊とするとき，｜Π（ｑ，ｗ）｜＞１であるようなｑが存在することをいう。このようなＦＳＴを非決定性有限状態トランスデューサ（Ｎｏｎｄｅｔｅｒｍｉｎｉｓｔｉｃ  Ｆｉｎｉｔｅ  Ｓｔａｔｅ  Ｔｒａｎｓｄｕｃｅｒ，ＮＦＳＴ）という。一方，ＦＳＴが決定的（ｄｅｔｅｒｍｉｎｉｓｔｉｃ）であるとは，ある入力記号列が与えられたとき取りうる経路が最大でも１つだけであることをいう。形式的には，全てのｑ∈Ｑ，ｗ∈Σ＊に対して，｜Π（ｑ，ｗ）｜≦１であることをいう。このようなＦＳＴを決定的有限状態トランスデューサ（Ｄｅｔｅｒｍｉｎｉｓｔｉｃ  Ｆｉｎｉｔｅ  Ｓｔａｔｅ  Ｔｒａｎｓｄｕｃｅｒ，ＤＦＳＴ）という。ＮＦＳＴをＤＦＳＴへと変換することを決定化（ｄｅｔｅｒｍｉｎｉｚｅ）という。この決定化は例えば特許文献１や非特許文献１に記載の方法を用いることで行える。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】米国特許第６，４５６，９７１号明細書
【非特許文献】
【０００５】
【非特許文献１】Ｍ．Ｍｏｈｒｉ，Ｏｎ  Ｓｏｍｅ  Ａｐｐｌｉｃａｔｉｏｎｓ  ｏｆ  Ｆｉｎｉｔｅ−Ｓｔａｔｅ  Ａｕｔｏｍａｔａ  Ｔｈｅｏｒｙ  ｔｏ  Ｎａｔｕｒａｌ  Ｌａｎｇｕａｇｅ  Ｐｒｏｃｅｓｓｉｎｇ，Ｎａｔｕｒａｌ  Ｌａｎｇｕａｇｅ  Ｅｎｇｉｎｅｅｒｉｎｇ，１９９６，ｖｏｌ．２，ｉｓｓｕｅ  １，Ｐａｇｅｓ  ６１−８０
【非特許文献２】Ｊｅａｎ  Ｂｅｒｓｔｅｌ，Ｔｒａｎｓｄｕｃｔｉｏｎｓ  ａｎｄ  Ｃｏｎｔｅｘｔ−Ｆｒｅｅ  Ｌａｎｇｕａｇｅｓ，１９７９，Ｃｈａｐｔｅｒ  ＩＶ，Ｓｅｃｔｉｏｎ  ６
【非特許文献３】Ｃ．Ａｌｌａｕｚｅｎ，Ｍ．Ｍｏｈｒｉ，Ａｎ  Ｏｐｔｉｍａｌ  Ｐｒｅ−ｄｅｔｅｒｍｉｎｉｚａｔｉｏｎ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ＷｅｉｇｈｔｅｄＴｒａｎｓｄｕｃｅｒｓ，Ｔｈｅｏｒｅｔｉｃａｌ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，２００４，Ｖｏｌｕｍｅ  ３２８，Ｉｓｓｕｅ  １−２，Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ  ａｎｄ  ａｐｐｌｉｃａｔｉｏｎ  ｏｆ  ａｕｔｏｍａｔａ，Ｐａｇｅｓ  ３−１８
【非特許文献４】Ｍ．Ｍｏｈｒｉ，Ｍ．Ｒｉｌｅｙ，Ｄ．Ｈｉｎｄｌｅ，Ａ．Ｌｊｏｌｊｅ，Ｆ．Ｃ．Ｎ．Ｐｅｒｅｉｒａ，Ｆｕｌｌ  Ｅｘｐａｎｓｉｏｎ  ｏｆ  Ｃｏｎｔｅｘｔ−ｄｅｐｅｎｄｅｎｔ  Ｎｅｔｗｏｒｋｓ  ｉｎ  Ｌａｒｇｅ  Ｖｏｃａｂｕｌａｒｙ  Ｓｐｅｅｃｈ  Ｒｅｃｏｇｎｉｔｉｏｎ．１９９８，Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ａｃｏｕｓｔｉｃｓ，Ｓｐｅｅｃｈ，ａｎｄ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ（ＩＣＡＳＳＰ’９８），Ｓｅａｔｔｌｅ，Ｗａｓｈｉｎｇｔｏｎ
【非特許文献５】Ｃ．Ａｌｌａｕｚｅｎ，Ｍ．Ｍｏｈｒｉ，Ｇｅｎｅｒａｌｉｚｅｄ  Ｏｐｔｉｍｉｚａｔｉｏｎ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  Ｓｐｅｅｃｈ  Ｒｅｃｏｇｎｉｔｉｏｎ  Ｔｒａｎｓｄｕｃｅｒｓ，２００３，Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ａｃｏｕｓｔｉｃｓ，Ｓｐｅｅｃｈ，ａｎｄ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ（ＩＣＡＳＳＰ’０３）
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら，従来の方法で単値でないＮＦＳＴを決定化するには，単値でない原因となる部分を発見するステップと，発見した部分を単値にすることで，単値なＮＦＳＴへと変換するステップから構成される事前処理が必要であった（「単値」については後述する）。
【０００７】
本発明は，上記の点に鑑みて，これらの問題を解消するために発明されたものであり，事前処理なしに単値でないＮＦＳＴを決定化することにある。
【課題を解決するための手段】
【０００８】
上述した課題を解決し，目的を達成するために，本発明は，有限状態トランスデューサが有する遷移に割り当てられている入力記号とは異なる記号である識別記号を生成する記号決定部と，前記有限状態トランスデューサが有する状態のうち，同一の入力記号による遷移先にある一または複数の状態を抽出し，抽出した前記状態をサブ状態として有する状態を生成する状態併合部と，前記状態併合部が生成する状態間の遷移の入力記号として，有限状態トランスデューサが有する遷移に割り当てられている入力記号または前記識別記号を付与することにより決定化する単値化処理部と，を有することを特徴とする。
【０００９】
上述した課題を解決し，目的を達成するために，本発明は，また，有限状態トランスデューサが有する遷移に割り当てられている入力記号とは異なる記号である識別記号を生成する記号決定ステップと，前記有限状態トランスデューサが有する状態のうち，同一の入力による遷移先にある一または複数の状態を抽出し，抽出した前記状態をサブ状態として有する状態を生成する状態併合ステップと，前記状態併合ステップが生成する状態間の遷移の入力記号として，有限状態トランスデューサが有する遷移に割り当てられている入力記号または前記識別記号を付与することにより決定化する単値化ステップと，を有することを特徴とする。
【発明の効果】
【００１０】
本発明の有限状態トランスデューサ決定化装置及び有限状態トランスデューサ決定化方法によれば，事前処理なしに単値でないＮＦＳＴを決定化することが可能になる。
【図面の簡単な説明】
【００１１】
【図１】図１は，ｔｗｉｎｓ  ｐｒｏｐｅｒｔｙを持つＦＳＴの例を示す図である。
【図２】図２は，決定化後に出力記号が消えない例を説明する図である。
【図３−１】図３−１は，本実施の形態の有限状態トランスデューサ決定方法の詳細を示す擬似コード（その１）である。
【図３−２】図３−２は，本実施の形態の有限状態トランスデューサ決定方法の詳細を示す擬似コード（その２）である。
【図４】図４は，補助入力記号を割り当てる処理の擬似コードである。
【図５】図５は，例１における決定化前のＦＳＴ  Ｔ１を示す図である。
【図６】図６は，例１の決定化後のＦＳＴの初期状態を示す図である。
【図７】図７は，例１の決定化処理の過程におけるＦＳＴを示す図（その１）である。
【図８】図８は，例１の決定化処理の過程におけるＦＳＴを示す図（その２）である。
【図９】図９は，例１の決定化処理の過程におけるＦＳＴを示す図（その３）である。
【図１０】図１０は，例１の決定化後のＦＳＴを示す図である。
【図１１】図１１は，例２における決定化前のＦＳＴ  Ｔ１を示す図である。
【図１２】図１２は，例２の決定化後のＦＳＴの初期状態を示す図である。
【図１３】図１３は，例２の決定化処理の過程におけるＦＳＴを示す図（その１）である。
【図１４】図１４は，例２の決定化処理の過程におけるＦＳＴを示す図（その２）である。
【図１５】図１５は，例２の決定化処理の過程におけるＦＳＴを示す図（その３）である。
【図１６】図１６は，例２の決定化後のＦＳＴを示す図である。
【図１７】図１７は，終了出力がないＦＳＴを処理する例の擬似コードである。
【図１８】図１８は，終了出力がＮ個あってもよいＦＳＴを処理する例の擬似コードである。
【図１９】図１９は，ハードウェアの構成の例を示す図である。
【図２０】図２０は，本実施の形態に係る有限状態トランスデューサ決定化装置の機能構成の例を示す図である。
【図２１】図２１は，音声認識におけるＦＳＴの例を示す図である。
【図２２】図２２は，翻訳におけるＦＳＴの例を示す図である。
【図２３】図２３は，検索における決定化前のＦＳＴの例を示す図である。
【図２４】図２４は，検索における決定化後のＦＳＴの例を示す図である。
【図２５】図２５は，重みが加えられたＦＳＴに補助入力記号を付加する処理の擬似コードである。
【図２６】図２６は，決定化前のＷＦＳＴを示す図である。
【図２７】図２７は，決定化後のＷＦＳＴの初期状態を示す図である。
【図２８】図２８は，決定化処理の過程におけるＷＦＳＴを示す図（その１）である。
【図２９】図２９は，決定化処理の過程におけるＷＦＳＴを示す図（その２）である。
【図３０】図３０は，決定化後のＷＦＳＴを示す図である。
【図３１】図３１は，音声認識におけるＷＦＳＴの例を示す図である。
【発明を実施するための形態】
【００１２】
以下，本実施の形態を図面に基づき説明する。
【００１３】
（実施の形態１〕
ＮＦＳＴには単値（ｓｉｎｇｌｅ−ｖａｌｕｅｄ）であるものとそうでないものがある。ＮＦＳＴが単値であるとは，どのような入力記号列をＮＦＳＴに入力しても得られる出力が最大でも１つであることをいう。形式的には，経路π∈Π（ｑ，ｗ）の出力記号列をｏｕｔ（π）とするとき，｜｛ｏｕｔ（π）｜π∈Π（ｑ，ｗ），ｑ∈Ｑ，ｗ∈Σ＊｝｜≦１であることをいう。同様に，単値でないとは｜｛ｏｕｔ（π）｜π∈Π（ｑ，ｗ），ｑ∈Ｑ，ｗ∈Σ＊｝｜＞１であることをいう。
【００１４】
単値でないＮＦＳＴの決定化を特許文献１に記載の方法で行うと，決定化前には存在していた出力記号が消えることがある。非特許文献１に記載の方法では決定化が終了しないことがある。このような状況は，ＦＳＴが次に説明するｔｗｉｎｓ  ｐｒｏｐｅｒｔｙを持っていないときに発生する（非特許文献２，３）。
【００１５】
状態ｑから入力記号ｗにより状態ｑ’へ到達する経路の集合をΠ（ｑ，ｗ，ｑ’），経路πの遷移先の状態をｎ（π）とする。さらに（×）を記号列の結合演算とし，記号列をｘとするとき，ｘ−１はｘ−１（×）ｘ＝εを満たすような記号列であるとする。例えばＡ（×）Ｂ＝ＡＢ，Ａ−１（×）ＡＢ＝Ｂである。
【００１６】
（条件）
ｏｕｔ（π１）−１（×）ｏｕｔ（π２）＝ｏｕｔ（π１π’１）−１（×）ｏｕｔ（π２π’２）
を満たすとき，状態ｑ１＝ｎ（π１），ｑ２＝ｎ（π２）はｔｗｉｎｓであるという。ここで，初期状態ｉ１，ｉ２∈Ｉから入力記号列ｘ∈Σ＊による経路をπ１∈Π（ｉ１，ｘ），π２∈Π（ｉ２，ｘ）としている。また，入力記号列ｙ∈Σ＊に対してπ’１∈Π（ｑ１，ｙ，ｑ１），π’２∈Π（ｑ２，ｙ，ｑ２）である。経路π１の後ろに経路π’１をつなげた経路をπ１π’１と表現している。全てのｑ１，ｑ２の組み合わせがｔｗｉｎｓであるとき，そのＦＳＴはｔｗｉｎｓ  ｐｒｏｐｅｒｔｙを持つという。循環経路（ｃｙｃｌｉｃ  ｐａｔｈ）がないＦＳＴの場合はΠ（ｑ１，ｙ，ｑ１）やΠ（ｑ２，ｙ，ｑ２）が空集合であるため，そもそもｔｗｉｎｓでない状態が存在しない。したがって，そのようなＦＳＴもｔｗｉｎｓ  ｐｒｏｐｅｒｔｙを持つ。
【００１７】
ｔｗｉｎｓでない状態を見つけ，補助入力記号（Ａｕｘｉｌｉａｒｙ  ｉｎｐｕｔ  ｓｙｍｂｏｌ）を該当箇所に導入することで決定化可能にする方法，言い換えると単値なＦＳＴへと変換する方法は従来より提案されている（非特許文献３）。補助入力記号とは，元のＦＳＴには含まれていない入力記号であり，単値なＦＳＴにするために新たに導入する入力記号のことである。このような方法により，事前に単値でないＦＳＴを単値なＦＳＴへと変換することで，単値でないＦＳＴを決定化することができる。
【００１８】
ｔｗｉｎｓ  ｐｒｏｐｅｒｔｙを持っていても出力記号が消える場合がある。図１のような場合である。ここで，太線の丸は初期状態，二重線の丸は終了状態を表す。「：」の左側が入力記号，右側が出力記号列である。
【００１９】
このような場合，終了状態からｎ個の出て行く遷移を認めるようにし，そこに出力記号を割り当てれば（図２），決定化後も出力記号が消えることはなくなる。このようなＦＳＴについては特許文献１，非特許文献２に記載がある。
【００２０】
各遷移に重みが付与されたＦＳＴは重み付き有限状態トランスデューサ（Ｗｅｉｇｈｔｅｄ  Ｆｉｎｉｔｅ  Ｓｔａｔｅ  Ｔｒａｎｓｄｕｃｅｒ，ＷＦＳＴ）と呼ばれる。ＦＳＴの場合と同様に，ＷＦＳＴについても決定化を行うことが可能であり，例えば特許文献１の方法によって決定化を行うことができる。ＷＦＳＴの場合においても，単値でないＷＦＳＴが存在する。単値でないＷＦＳＴを決定化するには，単値なＷＦＳＴへと変換する必要があるが，この変換方法については非特許文献３に記載がある。この方法を用いて，まず単値でないＷＦＳＴを単値なＷＦＳＴへと変換し，その後，決定化するという方法を行うことで，単値でないＷＦＳＴを決定化することができる。
【００２１】
すなわち，単値でない原因となる部分を発見するステップと，発見した部分を単値にすることで，単値なＮＦＳＴへと変換するステップから構成される事前処理が必要となる。以下の実施の形態では，この事前処理を行うことなく，単値でないＮＦＳＴを決定化することについて，説明する。
【００２２】
次に，本実施の形態やそれ以降の実施の形態で必要な記号，用語等について説明する。
【００２３】
空集合はφまたは｛｝で表す。空記号列はεで表す。空記号列は，空列や空文字列などと呼ばれることがある。遷移ｅ∈Ｅの遷移元状態をｐ（ｅ），遷移先状態をｎ（ｅ），入力記号をｉｎ（ｅ），出力記号列をｏｕｔ（ｅ）とする。同様に，経路π∈Ｅ＊の始端状態をｐ（π），終端状態をｎ（π），入力記号列をｉｎ（π），出力記号列をｏｕｔ（π）とする。経路π上にある遷移の総数を｜π｜とする。π上のｊ個目の遷移先の状態を（π）ｊとする。ｐ（π）＝（π）０，ｎ（π）＝（π）｜π｜である。補助入力記号は＃ｎ（ｎは整数）で表すこととする。複数の補助入力記号を区別できればよいので，ここでは＃ｎのｎは整数であるとする。
【００２４】
プログラム等で集合を表現するときは，集合の要素を格納でき，集合内に重複した要素が発生しなければどのように表現してもよく，例えば，配列，リンクリスト，２分木，ハッシュテーブルなどが挙げられる。
【００２５】
本実施の形態での方法は，ｔｗｉｎｓ  ｐｒｏｐｅｒｔｙを持たないＦＳＴ全てについて決定化できるというわけではない。本実施の形態での方法によって決定化でできるＮＦＳＴは次の条件を満たすもののみである。
【００２６】
初期状態から状態ｑ１，ｑ２までの経路をそれぞれπ１，π２とし，状態ｑ１からｑ１までの経路をπ’１，状態ｑ２からｑ２までの経路をπ’２とし，さらにｉｎ（π１π’１）＝ｉｎ（π２π’２）であるとする。このような状態ｑ１とｑ２の全てに対してｔｗｉｎｓであるか，次の条件を満たすとき，本実施の形態の方法によって単値へと変換しながら決定化することができる。
【００２７】
その条件とは，（π１）ｊ＝（π２）ｊであるようなｊが存在し，状態（π１）ｊと（π２）ｊまでのπ１とπ２上にある遷移の出力記号列を全てεとすると，状態ｑ１とｑ２がｔｗｉｎｓとなることである。
【００２８】
以上の条件を満たさないＮＦＳＴは単値にできないため，本実施の形態で述べる方法による決定化処理が完了することはない。
【００２９】
本実施の形態の方法の詳細は図３−１及び図３−２（以下、「図３」という。）の擬似コードの通りである。なお、図３−２に示す擬似コードは、図３−１に続く擬似コードであり、両者を併せて１つの関数ｄｅｔｅｒｍｉｎｉｚｅとなる。この擬似コードは，ＦＳＴに初期出力と終了出力を加えたＦＳＴの決定化を行うことができる。ただし，終了出力は出力記号列１つのみとしている。初期出力がないＦＳＴ，終了出力が複数あるＦＳＴ，終了出力がないＦＳＴに対する処理方法は後に説明する。この擬似コードによって決定化を行う対象のＦＳＴをＴ１＝（Ｑ１，Σ１，Δ，Ｅ１，Ｉ１，Ｆ１，λ１，ρ１），決定化後のＦＳＴをＴ２＝（Ｑ２，Σ２，Δ，Ｅ２，ｉ２，Ｆ２，λ２，ρ２）とする。Ｑ１，Ｑ２は状態の集合，Σ１，Σ２は入力記号の集合，Δは出力記号の集合，Ｅ１，Ｅ２は遷移の集合，Ｉ１は初期状態の集合，ｉ２は初期状態，λ１は初期出力関数，λ２は初期出力，ρ１，ρ２は終了出力関数を表す。初期状態ｉ∈Ｉに対し，λ１（ｉ）∈Δ＊であり，λ２∈Δ＊である。終了状態ｑ∈Ｆ１に対してρ１（ｑ）∈Δ＊であり，同様にｑ∈Ｆ２に，対してρ２（ｑ）∈Δ＊である。
【００３０】
出力記号の演算は一般化のため（＋）と（×）で表す。図中では（＋）は＋を丸で囲った記号，（×）は×を丸で囲った記号で表す。本実施の形態では，（＋）は前方最長一致（ｌｏｎｇｅｓｔ  ｃｏｍｍｏｎ  ｐｒｅｆｉｘ）演算を，（×）は結合演算を表す。例えばａｂｃ（＋）ａｄｃ＝ａ，ａ（×）ｂ＝ａｂとなる。さらに特別な値である１＃を導入する。本実施の形態では，１＃を空記号列εとして扱う。言い換えると，本実施の形態に限っては図３の１＃をεと置き換えても意味は同じであるということである。記号列をｘとするとき，ｘ−１はｘ−１（×）ｘ＝１＃＝εを満たすような記号列であるとする。例えば，ａ−１（×）ａｂ＝ｂとなる。ａｕｘ（ｑ，ｖ）は出力記号ｖ∈Δ＊と状態ｑ∈Ｑ２に対応する補助入力記号を表している。ａｕｘ（ｑ，ｖ）の詳細については後述する。
【００３１】
Ｔ２の状態の集合Ｑ２の要素である状態をｑ２とするとき，（Ｔ１の状態，入力記号または出力記号列）の２つ組の集合でｑ２は表される。形式的には，ｑ２⊆｛（ｑ１，ｗ）｜ｑ１∈Ｑ１，ｗ∈（Σ１∪Δ＊）｝である。コンピュータ上で実際に動作させる際には，図３の擬似コードと同じく，Ｔ２の各状態を区別するために２つ組の集合を用いてもよいし，Ｔ２の各状態に番号を割り当てておき，さらにその番号と２つ組の集合とを相互に関連付けて記憶するようにしておいてもよい。また，決定化が完了すれば，２つ組の集合は不要なので，各状態には区別するためだけの情報を含めておくだけでよい。例えば，Ｔ２の各状態に互いに異なる番号を割り当てればよい。
【００３２】
図３で使われているγ（ｑ２，α）とξ（ｑ２，α，ｑｎ）は
γ（ｑ２，α）＝｛ｎ（ｅ）｜ｅ∈Ｅ１，（ｑ，・）∈ｑ２，ｐ（ｅ）＝ｑ，ｉｎ（ｅ）＝α｝
ξ（ｑ２，α，ｑｎ）＝｛（ｗ，ｅ）｜（ｑ，ｗ）∈ｑ２，ｅ∈Ｅ１，ｐ（ｅ）＝ｑ，ｎ（ｅ）＝ｑｎ，ｉｎ（ｅ）＝α｝
のように定義される。γ（ｑ２，α）は決定化後の状態ｑ２の要素である決定化前の状態のそれぞれからの入力記号αによる遷移先の状態の集合を表している。ξ（ｑ２，α，ｑｎ）は，決定化後の状態ｑ２の要素である決定化前の状態が遷移元状態であり，決定化前の状態ｑｎ∈Ｑ１が遷移先であり，さらに入力記号αが割り当てられている遷移の集合を表している。
【００３３】
図３の擬似コードを順に説明する。なお，本実施の形態では，擬似コードの１行に対応する処理毎に，一のステップが実行される。１行目ではＦＳＴ  Ｔ２の状態の集合Ｑ２，遷移の集合Ｅ２，終了状態の集合Ｆ２を空集合にすることで初期化する。入力記号の集合Σ２はＦＳＴ  Ｔ１の入力記号の集合Σ１を代入する。
【００３４】
２行目ではＦＳＴ  Ｔ１の初期状態に割り当てられている出力記号列全てについて最長前方一致演算を行った結果をＦＳＴ  Ｔ２の初期出力記号列λ２へと代入する。
【００３５】
３行目ではＴ２の初期状態ｉ２を作成する。Ｔ１の初期状態と出力記号列の２つ組を要素とする集合として初期状態は表される。ｉ２に含まれる要素を（ｉ，ｗ）とするとき，ｗはＴ１の初期状態ｉに対応する初期出力記号列λ１（ｉ）の前方から順にλ２と同じ出力記号列を取り除いたものとなる。例えば，λ１（ｉ）がａｂｃで，λ２がａｂならｗ＝（ａｂ）−１（×）ａｂｃ＝ｃとなる。
【００３６】
４行目ではスタックＳにＴ２の初期状態を設定する。この時点ではＳに含まれる要素はｉ２のみである。なお，スタックＳは値を１つずつ追加・取り出しができることができればどのようなものでもかまわないので，スタックではなく例えばキューとして実装してもよい。さらにＱ２にｉ２を追加する。
【００３７】
５行目ではスタックＳが空か否かを判断する。空なら決定化が完了したことを意味するので，処理を終了する。空でない場合は６行目以降を処理していく。
６行目ではスタックＳから要素を１つ取り出し，ｑ２に代入する。取り出した要素はスタックＳから除去される。
【００３８】
７行目ではｑ２に含まれる要素である２つ組（状態，記号列）のうち，少なくとも１つの記号列がΣ１に含まれていれば８行目に処理を進める。そうでなければ１４行目に処理を進める。
【００３９】
８行目ではｑ２に含まれている要素である２つ組を（ｑ，ｗ）とする。なお，必ず｜ｑ２｜＝１であるのでｑ，ｗは一意に決まる。
【００４０】
９行目では１０行目で作成する遷移の遷移先状態ｑｎ２を作成する。状態ｑｎ２は状態ｑと出力記号列１＃から成る２つ組を要素とする集合となる。
【００４１】
１０行目では遷移元状態がｑ２，入力記号がｗ，出力記号が１＃，遷移先状態がｑｎ２である遷移をＥ２へ追加する。
【００４２】
１１行目ではｑｎ２が既にＱ２に含まれているか否かを判断し，もし含まれていなければ，１２行目へと処理を進める。１２行目ではスタックＳにｑｎ２を追加し，さらにＱ２にもｑｎ２を追加する。
【００４３】
１４行目から２３行目ではＴ２の終了状態と終了出力を作成する処理である。
１４行目ではｑ２の要素である２つ組に含まれている状態ｑ∈Ｑ１のうち終了状態Ｆ１に含まれているものが少なくとも１つあるか否か判断する。少なくとも１つあれば１５行目の処理に進む。
【００４４】
１５行目ではｑ２に含まれる２つ組（ｑ，ｗ）のうち，ｑ∈Ｆ１であるような２つ組（ｑ，ｗ）の全てに対して，ｗ（×）ρ１（ｑ）を計算し，その計算で得られた出力記号列すべてを含む集合をＷとする。
【００４５】
１６行目では出力記号列の集合Ｗに含まれる出力記号列全てに対して（＋）による演算を行い，その結果をｗ２に代入する。例えばＷ＝｛ｘ１，ｘ２，ｘ３｝であれば，ｘ１（＋）ｘ２（＋）ｘ３という計算をすることになる。
【００４６】
１７行目では１６行目で計算したｗ２と同じ出力記号列が少なくとも１つＷに含まれていれば１８行目に処理を進める。そうでなければ１９行目に処理を進める。
【００４７】
１８行目ではｗ２をｑ２の終了出力としてρ２（ｑ２）に代入し，さらに終了状態としてＦ２にｑ２を追加する。
【００４８】
１９行目はＷに含まれる出力記号列ｗのうち，ｗ２と異なるものについて，２０行目から２３行目を処理することを表している。
２０行目では状態ｑｎ２を空集合にする。
２１行目では遷移元状態をｑ２，入力記号を（ｑｎ２，ｗ），出力記号列をｗ，遷移先状態をｑｎ２とするような遷移をＥ２へ追加する。また，追加した遷移の入力記号をΣ２に追加する。
【００４９】
２２行目ではＴ２の状態の集合Ｑ２にｑｎ２が含まれているか否かを判断する。含まれていなければ２３行目へと処理を進める。
２３行目ではｑｎ２の終了出力ρ２（ｑｎ２）を１＃とし，Ｔ２の状態の集合Ｑ２と終了状態の集合Ｆ２へｑｎ２を追加する。
【００５０】
２４行目は，Σ１に含まれる入力記号αについてそれぞれ２５行目から３７行目の処理を行うことを表している。２つ組（Ｔ１の状態，出力記号列）としてｑ２に含まれているＴ１の状態が遷移元状態である遷移に割り当てられている全ての入力記号について２５行目から３７行目までを処理できればよいので，それらに含まれていない入力記号については２５行目から３７行目までを処理する必要はない。ただし，処理したとしても２６行目や３２行目の条件を満たすことがないので，結果は処理しなかった場合と同じである。
【００５１】
２５行目ではγ（ｑ２，α）の各要素ｑｎに対して次の処理を行い，ｑｎと得られた結果で２つ組（ｑｎ，出力記号列の集合）を作り，全てのｑｎに対応する２つ組（ｑｎ，出力記号列の集合）の集合をθに代入する。その処理とは，ｗを出力記号列，ｅを遷移とするとき，ξ（ｑ２，α，ｑｎ）の各要素（ｗ，ｅ）に対してｗ（×）ｏｕｔ（ｅ）を計算した結果を要素とする集合を作成する処理である。
【００５２】
２６行目では２５行目で作成したθの要素である２つ組（ｑｎ，Ｗ）のうち，Ｗのサイズが２以上である要素について２７行目から３１行目の処理を行う。
２７行目では２つ組（ｑｎ，α）をｑｎ２へ代入する。
２８行目は，Ｗに含まれる要素ｗについてそれぞれ２９行目を処理することを表している。
【００５３】
２９行目では遷移元状態をｑ２，入力記号をａｕｘ（ｑｎ２，ｗ），出力記号列をｗ，遷移先状態をｑｎ２とする遷移をＥ２へ追加する。さらに，追加した遷移の入力記号をΣ２へ追加する。
３０行目ではｑｎ２がＱ２に含まれているか否かを判断し，含まれていなければ３１行目へと処理を進める。
【００５４】
３１行目ではスタックＳにｑｎ２を追加し，さらにＱ２にｑｎ２を追加する。
３２行目ではθの要素である２つ組（ｑｎ，Ｗ）のうち，Ｗのサイズが１の２つ組が少なくとも１つあれば３３行目から３７行目の処理を行う。
【００５５】
３３行目ではθの要素である２つ組（ｑｎ，Ｗ）のうち，Ｗのサイズが１であるもの全てについて，出力記号列ｗ∈Ｗを（＋）で計算し，得られた結果をｗ２へ代入する。例えばｒ１，ｒ２，ｒ３∈Ｑ１としてθ＝｛（ｒ１，｛ａｂ｝），（ｒ２，｛ａｃ｝），（ｒ３，｛ｂ，ｃｄ｝）｝であるとするとき，Ｗのサイズが１である２つ組は（ｒ１，｛ａｂ｝），（ｒ２，｛ａｃ｝）であり，これらの出力記号列を（＋）で計算すると，ａｂ（＋）ａｃ＝ａとなるので，ｗ２＝ａとなる。
【００５６】
３４行目は３３行目と同様にθのＷのサイズが１である２つ組（ｑｎ，Ｗ）に対し，ｑｎとＷの要素ｗの前方からｗ２に一致する部分を除いた出力記号列とから成る２つ組を作成し，それらの集合をｑｎ２へ代入する。３３行目の例を用いて説明すると，３３行目と同様にＷのサイズが１である２つ組は（ｒ１，｛ａｂ｝），（ｒ２，｛ａｃ｝）であるので，ｒ１に対してはａ−１（×）ａｂ＝ｂ，ｒ２に対してはａ−１（×）ａｃ＝ｃとなる。その結果，この例の場合はｑｎ２＝｛（ｒ１，ｂ），（ｒ２，ｃ）｝となる。
【００５７】
３５行目では遷移元状態をｑ２，入力記号をα，出力記号をｗ２，遷移先状態をｑｎ２とする遷移をＥ２へ追加する。
３６行目ではｑｎ２がＱ２に含まれているか否かを判断し，含まれていなければ３７行目の処理を行う。
【００５８】
３７行目ではスタックＳにｑｎ２を追加し，さらにＱ２にｑｎ２を追加する。
決定化が完了すると，各状態に関連付けられている２つ組（状態，記号列）の集合を記憶しておく必要はなくなるので，各状態に互いに異なる番号を割り当て直すという処理を行うこともできる。また，決定化中に随時番号を割り当てておき，その番号に２つ組（状態，記号列）の集合を関連付けておくようにすることもできる。
【００５９】
決定化後の状態ｑ∈Ｑ２と出力記号列ｖ∈Δ＊を引数として取り，戻り値として補助入力記号を返すアルゴリズムａｕｘは，ｑとｖとから成る２つ組のそれぞれに対して，互いに異なる補助入力記号を割り当てることができればよい。
補助入力記号をｙとして，３つ組（ｑ，ｖ，ｙ）を要素とする集合をＹとし，決定化を行う前に空集合に初期化されているものとする。すると，アルゴリズムａｕｘは図４のような手順によって実現できる。
【００６０】
ここで，ｍａｋｅ＿ａｕｘは引数として番号ｎが渡されると，補助入力記号＃ｎを返すという処理を行う。
【００６１】
図４の擬似コードの動作例を次に示す。説明を簡単にするため，決定化後のＦＳＴの状態は単に番号で表すものとする。Ｙが空集合のときにａｕｘ（１，Ｂ）が呼び出されると，Ｙが空集合なので１行目の条件が満たされることはない。したがって，３行目へと処理を進める。３行目では，ｍａｋｅ＿ａｕｘ（１）が呼び出される。｜Ｙ｜＝０であるからである。すると，補助入力記号＃１が得られるのでｙに代入し，４行目でＹに（１，Ｂ，＃１）を追加し，５行目で得られた＃１を返す。
【００６２】
再度ａｕｘ（１，Ｂ）が呼び出されると，Ｙ＝｛（１，Ｂ，＃１）｝であることから１行目の条件を満たすので，２行目で，条件を満たしたＹの要素の３番目の要素ｙ１である＃１を結果として返す。
【００６３】
次にａｕｘ（２，Ｂ）が呼び出されると，１行目の条件を満たさない。ｑ１＝２，ｖ１＝Ｂであるような要素はＹには今は含まれていないからである。そこで，３行目で新しい補助入力記号を作成する。今，｜Ｙ｜＝１であるので，ｍａｋｅ＿ａｕｘ（２）を実行することになり，＃２が得られ，ｙに代入する。これを使ってＹに（２，Ｂ，＃２）を追加すると，Ｙ＝｛（１，Ｂ，＃１），（２，Ｂ，＃２）｝となる。そして，＃２を結果として返す。
【００６４】
以上のようにしていくことで，状態ｑと出力記号列ｖの組み合わせに対して，それぞれ互いに異なる補助入力記号を割り当てていくことができる。また，必要な補助入力記号のみを作成することができる。
【００６５】
なお，決定化後の状態から出て行く遷移の作成が状態ごとに完了するたびに，Ｙを空集合に初期化することもできる。具体的には図３の６行目から３７行目の処理が終わるたびにＹを空集合にすればよい。このようにすると，生成される補助入力記号の種類を少なく抑えることができる。処理する決定化後の状態ごとに，必要に応じて＃１から順に生成されるためである。その代わり，状態ｑと出力記号列ｖが同じであっても異なる補助入力記号が割り当てられることがある。
【００６６】
（例１）
本実施の形態における決定化方法がどのように動作するのかについて，図５のＦＳＴを決定前のＦＳＴ  Ｔ１として説明する。図３と同様に決定化後のＦＳＴはＴ２とする。なおこの例ではスタックＳはスタックとして，つまり先入れ後出し方式で動作するものとする。図５よりＱ１＝｛０，１，２，３，４，５，６｝，Ｉ１＝｛０｝，Ｆ１＝｛６｝，Σ１＝｛ａ，ｂ，ｃ，ｄ｝，Δ１＝｛Ａ，Ｂ，Ｃ｝である。太線の円が初期状態であり，二重線の円が終了状態を表している。各遷移のラベルのうち，「：」の左側が入力記号，右側が出力記号列を表している。
【００６７】
図３の１行目でまず決定化後のＦＳＴの初期化が行われる。
次に２行目で初期出力を計算する。この例のＦＳＴには初期出力はない。言い換えるとλ１（０）＝１＃＝ε，つまり空記号列を出力するということである。したがって，λ２＝εとなる。
【００６８】
３行目では決定化後のＦＳＴの初期状態を作成する。ｉ２＝｛（０，ε）｝となる（図６）。
【００６９】
４行目では３行目で作成した状態ｉ２をスタックＳとＱ２に追加し，その結果，Ｓ＝｛｛（０，ε）｝｝，Ｑ２＝｛｛（０，ε）｝｝となる。
【００７０】
｜Ｓ｜＝１であるので，５行目の条件を満たし，６行目に処理を進める。
６行目でスタックＳから値を取り出し，ｑ２に代入すると，Ｓ＝φ，ｑ２＝｛（０，ε）｝となる。
【００７１】
７行目では，判断しなければならないｗはｗ＝εの場合のみである。ｗはΣ１には含まれていないので，７行目の条件は満たされない。したがって，１４行目に処理を進める。
１４行目では，ｑ２に含まれている２つ組（状態，記号列）のうちの状態がＦ１に含まれているか否かを判断する。いま，ｑ２に含まれる状態は状態０のみであり，これはＦ１には含まれていない。したがって，処理を２４行目に進める。
【００７２】
Σ１＝｛ａ，ｂ，ｃ｝ではあるが，状態０から出て行く遷移の入力記号はａのみであるので，α＝ａの場合のみを処理すればよい。したがって，２４行目ではα＝ａとして２５行目以降の処理を行う。
【００７３】
２５行目では，θ＝｛（１，｛ε（×）Ａ｝），（２，｛ε（×）Ｂ｝），（３，｛ε（×）Ｃ｝）｝＝｛（１，｛Ａ｝），（２，｛Ｂ｝），（３，｛Ｃ｝）｝となる。
２６行目の｜Ｗ｜＞１の条件を満たすθの要素はないので，３２行目へと処理を進める。
｜Ｗ｜＝１を満たすθの要素は存在するので３２行目の条件を満たし，３３行目へと処理を進める。
【００７４】
３３行目の処理で，ｗ２＝Ａ（＋）Ｂ（＋）Ｃ＝ε＝１＃となる。
３４行目の処理で，ｑｎ２＝｛（１，Ａ），（２，Ｂ），（３，Ｃ）｝が得られる。ｘ−１（×）ｘ＝εであるので，ε−１＝εである。ｘ＝εとするとε−１（×）ε＝εなので両辺に右側からεを（×）演算でつなげるとε−１（×）ε（×）ε＝ε（×）εとなり，ε−１（×）ε＝ε（×）εとなり，両辺の右側のεを取り除くとε−１＝εと変形できるからである。したがって，例えば，ｑｎ２の最初の要素である（１，Ａ）はｗ２（×）Ａ＝ε−１（×）Ａ＝ε（×）Ａ＝Ａのような計算から得られる。
【００７５】
３５行目で状態元状態が｛（０，ε）｝で入力記号がａ，出力記号がε，遷移先状態が｛（１，Ａ），（２，Ｂ），（３，Ｃ）｝である遷移を作成しＥ２に加える。その結果，図７のうち初期状態と状態Ｓ１０１とそれらの間の遷移とから構成されるＦＳＴになる。
【００７６】
今ｑｎ２はＱ２には含まれていないので３６行目を満たし，３７行目が処理される。
３７行目では，ｑｎ２をＳとＱ２に追加するので，Ｓ＝｛｛（１，Ａ），（２，Ｂ），（３，Ｃ）｝｝，ｑ２＝｛｛（０，ε）｝，｛（１，Ａ），（２，Ｂ），（３，Ｃ）｝｝となる。
【００７７】
５行目に処理が戻り，スタックＳは空集合ではないので，６行目に処理を進む。
６行目で，ｑ２＝｛（１，Ａ），（２，Ｂ），（３，Ｃ）｝となり，Ｓ＝φとなる。
ＡもＢもＣもΣ１には含まれていないので，７行目の条件は満たされず，１４行目に処理が進む。
【００７８】
状態１，２，３はＦ１には含まれていない，つまり終了状態ではないので，１４行目の条件は満たさない。したがって２４行目に処理が進む。
【００７９】
状態１，２，３から出て行く遷移の入力記号はｂのみであるので，２５行目から３７行目の処理はα＝ｂの場合の処理のみを行えばよい。
２５行目では，θ＝｛（４，｛Ａ（×）ε，Ｂ（×）ε｝），（５，｛Ｃ（×）ε｝）｝＝｛（４，｛Ａ，Ｂ｝），（５，｛Ｃ｝）｝となる。
【００８０】
２６行目ではθの要素のうち，（４，｛Ａ，Ｂ｝）が｜Ｗ｜＞１の条件を満たすので，これについて２７行目から３１行目の処理を行う。
２７行目で，ｑｎ２＝｛（ｑｎ，α）｝＝｛（４，ｂ）｝となり，２８行目へと処理が進む。
【００８１】
いま，Ｗ＝｛Ａ，Ｂ｝であるので，まず，ｗ＝Ａについて２９行目の処理を行う。ここでａｕｘ（ｑｎ２，ｗ）＝ａｕｘ（｛（４，ｂ）｝，Ａ）＝＃１とする。そうすると，２９行目では，遷移元状態が｛（１，Ａ），（２，Ｂ），（３，Ｃ）｝，入力記号が＃１，出力記号列がＡ，遷移先状態が｛（４，ｂ）｝である遷移がＥ２に追加され，さらにΣ２に＃１が追加される。同様にｗ＝Ｂについても処理を行うが，このときａｕｘ（｛（４，ｂ）｝，Ｂ）＝＃２とすると，遷移元状態が｛（１，Ａ），（２，Ｂ），（３，Ｃ）｝，入力記号が＃２，出力記号列がＢ，遷移先状態が｛（４，ｂ）｝である遷移がＥ２に追加され，さらにΣ２に＃２が追加される。その結果，図７のうち，初期状態と状態Ｓ１０１と状態Ｓ１０２とそれらの状態間の遷移とから構成されるＦＳＴになる。
【００８２】
３０行目で，Ｑ２に｛（４，ｂ）｝が含まれていないと判定され，３１行目でＳとＱ２に｛（４，ｂ）｝が追加される。その結果，Ｓ＝｛｛（４，ｂ）｝｝，Ｑ２＝｛｛（０，ε）｝，｛（１，Ａ），（２，Ｂ），（３，Ｃ）｝，｛（４，ｂ）｝｝となる。
【００８３】
３２行目の処理に進むが，｜Ｗ｜＝１を満たす要素がθに含まれているので，３２行目の条件を満たし，３３行目以降の処理が行われる。ここで，条件を満たすのは，（５，｛Ｃ｝）である。
【００８４】
３３行目で，ｗ２＝Ｃとなる。
３４行目で，ｑｎ２＝｛（５，Ｃ−１（×）Ｃ）｝＝｛（５，ε）｝となる。
３５行目で，遷移元状態が｛（１，Ａ），（２，Ｂ），（３，Ｃ）｝，入力記号がｂ，出力記号列がＣ，遷移先状態が｛（５，ε）｝である遷移が追加される。その結果，図７のうち，初期状態と状態Ｓ１０１と状態Ｓ１０２と状態Ｓ１０３とそれらの状態間の遷移とから構成されるＦＳＴになる。
【００８５】
ｑｎ２＝｛（５，ε）｝なので３６行目の条件を満たし，３７行目に処理が進む。
３７行目で，ＳとＱ２に｛（５，ε）｝が追加される。その結果，Ｓ＝｛｛（４，ｂ）｝，｛（５，ε）｝｝，Ｑ２＝｛｛（０，ε）｝，｛（１，Ａ），（２，Ｂ），（３，Ｃ）｝，｛（４，ｂ）｝，｛（５，ε）｝｝となる。
【００８６】
５行目に処理が戻るが，Ｓは空集合ではないので６行目に処理を進める。
この例ではＳはスタックであるとしているので，６行目でｑ２＝｛（５，ε）｝となる。  また，Ｓ＝｛｛（４，ｂ）｝｝となる。
【００８７】
ｑ２に含まれる記号列はεのみであるので，７行目の条件は満たさない。そのため，１４行目に処理が進む。
【００８８】
状態５は終了状態ではないので，１４行目の条件は満たさず，２４行目の処理へ進む。
２５行目以降で処理するべきαはｃだけなので，α＝ｃとする。
２５行目で，θ＝｛（６，｛ε（×）ε｝）｝＝｛（６，｛ε｝）｝となる。
２６行目を満たすθの要素はないので，３２行目へと処理を進める。
θの要素は１つであり，その要素に関してＷ＝｛ε｝であるので，｜Ｗ｜＝１となり，３２行目の条件を満たす。したがって，３３行目以降の処理に進む。
【００８９】
３３行目で，ｗ２＝εになる。
３４行目で，ｑｎ２＝｛（６，ε）｝となる。
【００９０】
３５行目で，遷移元状態が｛（５，ε）｝，入力記号がｃ，出力記号がε，遷移先状態が｛（６，ε）｝の遷移がＥ２に追加される。その結果，状態Ｓ１０４を含む図７のようなＦＳＴになる。
ｑｎ２＝｛（６，ε）｝なので３６行目の条件を満たし，３７行目に処理が進む。３７行目で，ＳとＱ２に｛（６，ε）｝が追加される。その結果，Ｓ＝｛｛（４，ｂ）｝，｛（６，ε）｝｝，Ｑ２＝｛｛（０，ε）｝，｛（１，Ａ），（２，Ｂ），（３，Ｃ）｝，｛（４，ｂ）｝，｛（５，ε）｝｝，｛（６，ε）｝｝となる。
【００９１】
５行目に処理が戻るが，Ｓは空集合ではないので６行目に処理を進める。
６行目でｑ２＝｛（６，ε）｝となる。また，Ｓ＝｛｛（４，ｂ）｝｝となる。
ｑ２に含まれる記号列はεのみであるので，７行目の条件は満たさない。そのため，１４行目に処理が進む。
【００９２】
状態６は終了状態なので，１４行目の条件を満たし，１５行目の処理へ進む。
ρ１（６）＝εであるので，１５行目でＷ＝｛ε（×）ε｝＝｛ε｝となる。
１６行目で，ｗ２＝εとなる。
Ｗの要素は１つで，それはεであるので，１７行目の条件を満たし，１８行目へ処理を進める。
【００９３】
１８行目で，ρ２（｛（６，ε）｝）＝ε，Ｆ２＝｛｛（６，ε）｝｝となる。その結果，図８のようになる。
１９行目を満たすＷの要素はないので，２０行目から２３行目は処理されず，２４行目の処理へ進む。
【００９４】
２５行目以降で処理するべきαはｄだけなので，α＝ｄとする。
２５行目で，θ＝｛（０，｛ε（×）ε｝）｝＝｛（０，｛ε｝）｝となる。
２６行目を満たすθの要素はないので，３２行目へと処理を進める。
θの要素は１つであり，その要素に関してＷ＝｛ε｝であるので，｜Ｗ｜＝１となり，３２行目の条件を満たす。したがって，３３行目以降の処理に進む。
【００９５】
３３行目で，ｗ２＝εになる。
３４行目で，ｑｎ２＝｛（０，ε）｝となる。
３５行目で，遷移元状態が｛（６，ε）｝，入力記号がｄ，出力記号がε，遷移先状態が｛（０，ε）｝の遷移がＥ２に追加される。その結果，図９のうち，状態Ｓ１０５とその状態への遷移とその状態からの遷移を除いた部分から構成されるＦＳＴになる。
ｑｎ２＝｛（０，ε）｝なので３６行目の条件を満たさないため，３７行目は処理されない。
【００９６】
５行目に処理が戻るが，Ｓは空ではないので６行目に処理を進める。
６行目でｑ２＝｛（４，ｂ）｝となる。また，Ｓ＝φとなる。
ｑ２に含まれる記号列はｂであるので，７行目の条件を満たし，８行目へ処理を進める。
８行目で，ｑ＝４，ｗ＝ｂとなる。
９行目で，ｑｎ２＝｛（４，１＃）｝＝｛（４，ε）｝となる。
【００９７】
１０行目で，遷移元状態が｛（４，ｂ）｝，入力記号がｂ，出力記号がε，遷移先状態が｛（４，ε）｝の遷移がＥ２に追加される。その結果，図９のうち，状態Ｓ１０５から出て行く遷移を除いた部分から構成されるＦＳＴになる。
ｑｎ２＝｛（４，ε）｝であるので，１１行目の条件を満たし，１２行目へ処理を進める。
１２行目で，ＳとＱ２に｛（４，ε）｝が追加される。その結果，Ｓ＝｛｛（４，ε）｝｝，Ｑ２＝｛｛（０，ε）｝，｛（１，Ａ），（２，Ｂ），（３，Ｃ）｝，｛（４，ｂ）｝，｛（５，ε）｝｝，｛（６，ε）｝，｛（４，ε）｝｝となる。
【００９８】
５行目に処理が戻るが，Ｓは空ではないので６行目に処理を進める。
６行目でｑ２＝｛（４，ε）｝となる。また，Ｓ＝φとなる。
ｑ２に含まれる記号列はεのみであるので，７行目の条件は満たさない。そのため，１４行目に処理が進む。
【００９９】
状態４は終了状態ではないので，１４行目の条件は満たさず，２４行目の処理へ進む。
２５行目以降で処理するべきαはｃだけなので，α＝ｃとする。
２５行目で，θ＝｛（６，｛ε（×）ε｝）｝＝｛（６，｛ε｝）｝となる。
２６行目を満たすθの要素はないので，３２行目へと処理を進める。
【０１００】
θの要素は１つであり，その要素に関してＷ＝｛ε｝であるので，｜Ｗ｜＝１となり，３２行目の条件を満たす。したがって，３３行目以降の処理に進む。
３３行目で，ｗ２＝εになる。
３４行目で，ｑｎ２＝｛（６，ε）｝となる。
３５行目で，遷移元状態が｛（４，ε）｝，入力記号がｃ，出力記号がε，遷移先状態が｛（６，ε）｝の遷移がＥ２に追加される。その結果，図９のようになる。
【０１０１】
ｑｎ２＝｛（６，ε）｝なので３６行目の条件を満たさず，３７行目は処理されない。
５行目に処理が戻るが，いまＳは空集合なので，５行目の条件を満たさない。したがって，決定化処理が完了したことになる。
各状態に関連付けられている２つ組の集合を番号に置き換えて，図１０のようにすることもできる。
【０１０２】
（例２）
初期状態や終了状態が複数ある場合に本実施の形態における決定化方法がどのように動作するのかについて，図１１のＦＳＴを決定前のＦＳＴ  Ｔ１として説明する。
図３と同様に決定化後のＦＳＴはＴ２とする。なおこの例でもスタックＳはスタックとして，つまり先入れ後出し方式で動作するものとする。図１１よりＱ１＝｛０，１，２，３，４，５｝，Ｉ＝｛０，１｝，Ｆ＝｛３，４，５｝，Σ１＝｛ａ，ｂ｝，Δ１＝｛Ａ，Ｂ，Ｃ，Ｄ｝，λ１（０）＝Ａ，λ１（１）＝ＡＢ，ρ１（３）＝Ｄ，ρ１（４）＝Ａ，ρ１（５）＝εである。初期状態と終了状態に記載されている／の左側が状態番号で，／の右側がそれぞれ初期出力記号と終了出力記号である。
【０１０３】
図３の１行目でまず決定化後のＦＳＴの初期化が行われる。
次に２行目で初期出力を計算する。λ２＝λ１（０）（＋）λ１（１）＝Ａ（＋）ＡＢ＝Ａとなる。
３行目では決定化後のＦＳＴの初期状態を作成する。ｉ２＝｛（０，Ａ−１（×）Ａ），（１，Ａ−１（×）ＡＢ）｝＝｛（０，ε），（１，Ｂ）｝となる（図１２）。
【０１０４】
４行目では３行目で作成した状態ｉ２をスタックＳとＱ２に追加し，その結果，Ｓ＝｛｛（０，ε），（１，Ｂ）｝｝，Ｑ２＝｛｛（０，ε），（１，Ｂ）｝｝となる。
｜Ｓ｜＝１であるので，５行目の条件を満たし，６行目に処理を進める。
６行目でスタックＳから値を取り出し，ｑ２に代入すると，Ｓ＝φ，ｑ２＝｛（０，ε），（１，Ｂ）｝となる。
【０１０５】
７行目では，判断しなければならないｗに該当する記号列はεとＢである。どちらもΣ１には含まれていないので，７行目の条件は満たされない。したがって，１４行目に処理を進める。
【０１０６】
１４行目では，ｑ２に含まれている２つ組（状態，記号列）のうちの状態がＦ１に含まれているか否かを判断する。いま，ｑ２に含まれる状態は状態０と状態１であるが，これらはＦ１には含まれていない。したがって，処理を２４行目に進める。
Σ１＝｛ａ，ｂ｝ではあるが，状態０と状態１から出て行く遷移の入力記号はａのみであるので，α＝ａの場合のみを処理すればよい。したがって，２４行目ではα＝ａとして２５行目以降の処理を行う。
【０１０７】
２５行目では，θ＝｛（２，｛ε（×）ε，Ｂ（×）Ｃ｝）｝＝｛（２，｛ε，ＢＣ｝）｝となる。
２６行目ではθの要素のうち，（２，｛ε，ＢＣ｝）が｜Ｗ｜＞１の条件を満たすので，これについて２７行目から３１行目の処理を行う。
２７行目で，ｑｎ２＝｛（ｑｎ，α）｝＝｛（２，ａ）｝となり，２８行目へと処理が進む。
【０１０８】
いま，Ｗ＝｛ε，ＢＣ｝であるので，まず，ｗ＝εについて２９行目の処理を行う。ここでａｕｘ（ｑｎ２，ｗ）＝ａｕｘ（｛（２，ａ）｝，ε）＝＃１とする。そうすると，２９行目では，遷移元状態が｛（０，ε），（１，Ｂ）｝，入力記号が＃１，出力記号列がε，遷移先状態が｛（２，ａ）｝である遷移がＥ２に追加され，さらにΣ２に＃１が追加される。同様にｗ＝ＢＣについても処理を行うが，このときａｕｘ（｛（２，ａ）｝，ＢＣ）＝＃２とすると，遷移元状態が｛（０，ε），（１，Ｂ）｝，入力記号が＃２，出力記号列がＢＣ，遷移先状態が｛（２，ａ）｝である遷移がＥ２に追加され，さらにΣ２に＃２が追加される。その結果，図１３のうち，初期状態と状態Ｓ２０１とそれらの状態間の遷移から構成されるＦＳＴになる。
【０１０９】
３０行目で，Ｑ２に｛（２，ａ）｝が含まれていないと判定され，３１行目でＳとＱ２に｛（２，ａ）｝が追加される。その結果，Ｓ＝｛｛（２，ａ）｝｝，Ｑ２＝｛｛（０，ε），（１，Ｂ）｝，｛（２，ａ）｝｝となる。
３２行目の処理に進むが，｜Ｗ｜＝１を満たす要素がθには含まれていないので，３２行目の条件を満たさない。したがって，３３行目以降の処理は行われず，５行目に処理が戻る。
【０１１０】
Ｓは空集合ではないので６行目に処理を進める。
６行目でｑ２＝｛（２，ａ）｝となる。また，Ｓ＝φとなる。
ｑ２に含まれる記号列はａであるので，７行目の条件を満たし，８行目へ処理を進める。
【０１１１】
８行目で，ｑ＝２，ｗ＝ａとなる。
９行目で，ｑｎ２＝｛（２，１＃）｝＝｛（２，ε）｝となる。
１０行目で，遷移元状態が｛（２，ａ）｝，入力記号がａ，出力記号列がε，遷移先状態が｛（２，ε）｝の遷移がＥ２に追加される。その結果，図１３のうち，初期状態と状態Ｓ２０１と状態Ｓ２０２とそれらの状態間の遷移から構成されるＦＳＴになる。
【０１１２】
ｑｎ２＝｛（２，ε）｝であるので，１１行目の条件を満たし，１２行目へ処理を進める。
１２行目で，ＳとＱ２に｛（２，ε）｝が追加される。その結果，Ｓ＝｛｛（２，ε）｝｝，Ｑ２＝｛｛（０，ε），（１，Ｂ）｝，｛（２，ａ）｝，｛（２，ε）｝｝となる。
５行目に処理が戻るが，Ｓは空ではないので６行目に処理を進める。
６行目でｑ２＝｛（２，ε）｝となる。また，Ｓ＝φとなる。
【０１１３】
ｑ２に含まれる記号列はεのみであるので，７行目の条件は満たさない。そのため，１４行目に処理が進む。
状態２は終了状態ではないので，１４行目の条件は満たさず，２４行目の処理へ進む。
【０１１４】
２５行目以降で処理するべきαはｂだけなので，α＝ｂとする。
２５行目で，θ＝｛（３，｛ε（×）ε｝），（４，｛ε（×）Ｄ｝），（５，｛ε（×）ＤＢ｝）｝＝｛（３，｛ε｝），（４，｛Ｄ｝），（５，｛ＤＢ｝）｝となる。
２６行目を満たすθの要素はないので，３２行目へと処理を進める。
θの要素は３つあり，それらの要素に関してＷは｛ε｝，｛Ｄ｝，｛ＤＢ｝であるので，それら全てについて｜Ｗ｜＝１となる。したがって，３２行目の条件を満たし，３３行目以降の処理に進む。
【０１１５】
３３行目で，ｗ２＝εになる。
３４行目で，ｑｎ２＝｛（３，ε），（４，Ｄ），（５，ＤＢ）｝となる。
３５行目で，遷移元状態が｛（２，ε）｝，入力記号がｂ，出力記号がε，遷移先状態が｛（３，ε），（４，Ｄ），（５，ＤＢ）｝の遷移がＥ２に追加される。その結果，図１３のＦＳＴになる。
【０１１６】
ｑｎ２＝｛（３，ε），（４，Ｄ），（５，ＤＢ）｝なので３６行目の条件を満たし，３７行目に処理が進む。３７行目で，ＳとＱ２に｛（３，ε），（４，Ｄ），（５，ＤＢ）｝が追加される。その結果，Ｓ＝｛｛（３，ε），（４，Ｄ），（５，ＤＢ）｝｝，Ｑ２＝｛｛（０，ε），（１，Ｂ）｝，｛（２，ａ）｝，｛（２，ε）｝，｛（３，ε），（４，Ｄ），（５，ＤＢ）｝｝となる。
【０１１７】
５行目に処理が戻るが，Ｓは空集合ではないので６行目に処理を進める。
６行目でｑ２＝｛（３，ε），（４，Ｄ），（５，ＤＢ）｝となる。また，Ｓ＝φとなる。
ｑ２に含まれる記号列はεとＤとＤＢであるので，７行目の条件は満たさない。そのため，１４行目に処理が進む。
【０１１８】
状態３，４，５は終了状態なので，１４行目の条件を満たし，１５行目の処理へ進む。
ρ１（３）＝Ｄ，ρ１（４）＝Ａ，ρ１（５）＝εであるので，１５行目でＷ＝｛ε（×）Ｄ，Ｄ（×）Ａ，ＤＢ（×）ε｝＝｛Ｄ，ＤＡ，ＤＢ｝となる。
１６行目で，ｗ２＝Ｄ（＋）ＤＡ（＋）ＤＢ＝Ｄとなる。
Ｗの要素にはＤが含まれているので，１７行目の条件を満たし，１８行目へ処理を進める。
【０１１９】
１８行目で，ρ２（｛（３，ε），（４，Ｄ），（５，ＤＢ）｝）＝Ｄ，Ｆ２＝｛｛（３，ε），（４，Ｄ），（５，ＤＢ）｝｝となる。その結果，図１４のようになる。
【０１２０】
１９行目を満たすＷの要素があるので，まずはｗ＝ＤＡについて２０行目から２３行目の処理を行う。
２０行目でｑｎ２＝φとする。
【０１２１】
ａｕｘ（ｑｎ２，ｗ）＝ａｕｘ（φ，ＤＡ）＝＃３とすると，２１行目で，遷移元状態が｛（３，ε），（４，Ｄ），（５，ＤＢ）｝，入力記号が＃３，出力記号がＤＡ，遷移先状態がφの遷移がＥ２に追加される。
φはＱ２に含まれていないので，２２行目を満たし，２３行目へ進む。
２３行目で，ρ２（ｑｎ２）＝ρ２（φ）＝１＃＝ε，Ｑ２＝｛｛（０，ε），（１，Ｂ）｝，｛（２，ａ）｝，｛（２，ε）｝，｛（３，ε），（４，Ｄ），（５，ＤＢ）｝，φ｝，Ｆ２＝｛｛（３，ε），（４，Ｄ），（５，ＤＢ）｝，φ｝となる。その結果，図１４に図１５の状態Ｓ２０４と遷移ｔ２０４ａが追加される。つまり図１５のうち，遷移ｔ２０４ｂを除く部分で構成されるＦＳＴとなる。
【０１２２】
次に，ｗ＝ＤＢについて２０行目から２３行目の処理を行う。
２０行目でｑｎ２＝φとする。
ａｕｘ（ｑｎ２，ｗ）＝ａｕｘ（φ，ＤＢ）＝＃４とすると，２１行目で，遷移元状態が｛（３，ε），（４，Ｄ），（５，ＤＢ）｝，入力記号が＃４，出力記号がＤＢ，遷移先状態がφの遷移がＥ２に追加される。図１５でいうと遷移ｔ２０４ｂが追加される。その結果，図１５のＦＳＴとなる。
【０１２３】
いま，φはＱ２に含まれているので，２２行目を満たさない。
ｗ２でないＷの要素の全てについて処理を終えたので，２４行目に処理を進める。
状態３，４，５から出て行く遷移は存在しないので，２４行目以降の処理を行っても何も起きない。
【０１２４】
５行目に処理が戻るが，いまＳは空集合なので，５行目の条件を満たさない。したがって，決定化処理が完了したことになる。
前述したように，補助入力記号の番号（＃ｎのｎの部分）を状態ごとに１から振るようにすることもできる。その場合，決定化後のＦＳＴは図１６のようになる。
【０１２５】
（初期出力がない場合のＦＳＴの処理について）
初期出力がないＦＳＴを用いる場合，決定化したいＮＦＳＴの初期出力はεであると考えられる。したがって，図３の２行目で，λ２＝εとなる。つまり，決定化後のＤＦＳＴも初期出力がないＤＦＳＴになる。したがって，決定化前の初期状態に割り当てられている初期出力が全てεであるとするだけで，初期出力のないＮＦＳＴから初期出力のないＤＦＳＴへと決定化する処理を図３の方法を用いることで行うことができる。
【０１２６】
（終了出力がないＦＳＴの処理について）
終了出力がないＦＳＴ，つまり，ρが定義されないＦＳＴに関する決定化を行う場合には，図３の方法の１５行目から２３行目を図１７のように変更すればよい。
決定化前のＦＳＴの終了出力がないので，Ｗはｑ２に含まれる２つ組（状態，記号列）のうち，Ｆ１に含まれる状態と組になっている記号列から成る。ただし，記号列が１＃であるものは含めない（図１７の１行目）。
【０１２７】
Ｗが空集合であれば（図１７の２行目），３行目でｑ２をＦ２に追加する。
Ｗの全ての要素に対して図１７の５行目から８行目の処理を行うが，５行目から７行目の動作は図３の２０行目から２２行目と同じである。図１７の８行目では，ｑｎ２をＱ２とＦ２に追加する処理を行う。
【０１２８】
以上をまとめると，終了出力が必要ないときは単にｑ２を終了状態にする。そうでないときは新たに終了状態を作成し，その状態を遷移先状態，ｑ２を遷移元状態とする遷移を作成し，その遷移の出力記号列にｗを割り当てるということである。
【０１２９】
（終了出力がＮ個あってもよいＦＳＴの処理について）
各終了状態に終了出力を最大でＮ個（Ｎ≧０）割り当てることができるＦＳＴの場合，状態ｑに割り当てられる終了出力ρ（ｑ）は出力記号列の集合となる。ただし，｜ρ（ｑ）｜≦Ｎを満たすとする。ρ（ｑ）＝φの場合，状態ｑの終了出力はないということになる。このようなＦＳＴに関する決定化を行う場合には，図３の方法の１５行目から２３行目を図１８のように変更すればよい。
【０１３０】
図１８の１行目でｑ２をＦ２に追加する。
２行目では終了出力の一覧を作成する。ｑ２に含まれる２つ組（状態ｑ，記号列ｗ）のうち，状態ｑが決定化前のＦＳＴの終了状態であるような全ての２つ組に対し，その記号列ｗと状態ｑに割り当てられている終了出力ｙからｘ＝ｗ（×）ｙを計算し，そのうち，ｘが１＃でないようなｘからなる記号列の集合をＷとする。
【０１３１】
３行目ではＷのサイズがＮより大きいか否かを判断し，大きい場合には４行目へと処理を進め，そうでない場合には１１行目へと処理を進める。ＷのサイズがＮより大きい場合は，Ｗに含まれる終了出力の全てをｑ２の終了出力に割り当てることができないからである。
４行目では，図３の２０行目と同様に遷移先状態ｑｎ２を作成する。
５行目では，作成したｑｎ２がＱ２に含まれているか否かを判断し，含まれていなければ６行目の処理を行う。
【０１３２】
６行目では，ｑｎ２の終了出力ρ２（ｑｎ２）を空集合に設定し，ｑｎ２をＱ２とＦ２に追加する。
７行目ではＷのサイズがＮより大きいかを判断し，大きい場合には８行目から１０行目を繰り返し処理する。
８行目では，Ｗから出力記号を１つ取り出し，それをｗとする。取り出し方は例えばＷに含まれる出力記号列のうち長い出力記号列から取り出すようにすればよい。短い出力記号列から取り出すようにすることもできる。
【０１３３】
９行目では遷移元状態をｑ２，入力記号をａｕｘ（ｑｎ２，ｗ），出力記号列をｗ，遷移先状態をｑｎ２とする遷移をＥ２へ追加する。さらに，追加した遷移の入力記号をΣ２へ追加する。
１０行目では，Ｗからｗを取り除く。
１１行目では，Ｗに残っている出力記号をｑ２の終了出力ρ２（ｑ２）へと割り当てる。
【０１３４】
（ハードウェア構成）
図１９は本実施の形態に記載した方法を実施するために必要な決定化装置２７００のハードウェア構成を示したブロック図である。図１９に示されているように決定化装置２７００は，ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１，操作部２，表示部３，ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）４，ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）５，記憶部６，バス７等を備えている。各部はバス７により接続されている。
【０１３５】
ＣＰＵ１は，ＲＡＭ５の所定領域を作業領域として，ＲＯＭ４又は記憶部６に予め記憶された各種制御プログラムとの協働により各種処理を実行し，決定化装置２７００を構成する各部の動作を統括的に制御する。またＣＰＵ１は，ＲＯＭ４又は記憶部６に予め記憶された所定のプログラムとの協働により後述する各機能部の機能を実現させる。
【０１３６】
操作部２は，マウスやキーボード等の入力デバイスであって，ユーザから操作入力された情報を指示信号として受け付け，その指示信号をＣＰＵ１に出力する。表示部３は，ＬＣＤ（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）等の表示装置により構成され，ＣＰＵ１からの表示信号に基づいて，各種情報を表示する。
【０１３７】
ＲＯＭ４は，決定化装置２７００の制御にかかるプログラムや各種設定情報等を書き換え不可能に記憶する。ＲＡＭ５は，ＳＤＲＡＭ等の揮発性の記憶媒体であって，ＣＰＵ１の作業エリアとして機能する。具体的には，決定化処理時において生成される各種変数やパラメータの値等を一時記憶するバッファ等の役割を果たす。
【０１３８】
記憶部６は，フラッシュメモリ等の半導体による記憶媒体や，磁気的又は光学的に記録可能な記憶媒体を有し，決定化装置２７００の制御にかかるプログラムや各種設定情報等を書き換え可能に記憶する。また記憶部６は，ＦＳＴに係る各種の情報を予め記憶したり，決定化処理の処理結果であるＦＳＴを記録したりする。
【０１３９】
（処理部構成）
図２０は，本実施形態に係る有限状態トランスデューサの決定化方法を実行する，決定化装置の機能構成を示す図である。図２０の決定化装置１００は，ＦＳＴ読取部１０１からＦＳＴが入力され，ＦＳＴ書込部１０９に対して決定化したＦＳＴを出力する。
【０１４０】
決定化装置１００は，集合生成部１０，単値状態処理部２０，終了状態処理部３０，単値化処理部４０，及び，遷移選択部５０を有する。
【０１４１】
集合生成部１０は，ＦＳＴ読取部１０１から入力されるＦＳＴから，状態と，状態毎に対応する遷移に割り当てられている入力記号，出力記号，及び，遷移先の状態と，を含む集合をそれぞれ生成する。決定化後のＦＳＴに対応する集合についても空集合であるものを含め生成する。また，その他のワーク領域として使用する集合等についても生成する。生成された集合は，単値状態処理部２０，終了状態処理部３０，単値化処理部４０，及び，遷移選択部５０によって処理され，ＦＳＴの決定化が行われる。集合生成部１０は，図３の１行目ないし４行目の処理も行う。
【０１４２】
単値状態処理部２０は，状態取得部２１，及び，遷移生成制御部２２を有する。状態取得部２１は，集合生成部１０により生成された集合の中から，決定化後の状態のうち，その状態から出て行く遷移の生成処理がまだ行われていない状態を取得する。この状態を決定化処理中状態と呼ぶこととし，図３のｑ２に対応する。遷移生成制御部２２は，決定化処理中状態から出て行く遷移とその遷移先の状態を生成し，生成された状態を決定化後のＦＳＴに含ませる。
【０１４３】
なお，単値状態処理部２０は，図３の６行目から１２行目の処理を行う。状態取得部２１は，図３の６行目の処理を行う。遷移生成制御部２２は，図３の７行目ないし１２行目の処理を行う。
【０１４４】
終了状態処理部３０は，ＦＳＴの終了状態を生成する。終了状態処理部３０は，状態併合部３１，記号決定部３２，及び，遷移生成制御部３３を有する。状態併合部３１は，決定化処理中状態に対応する一または複数の終了出力を取得する。
【０１４５】
記号決定部３２は，状態併合部３１が取得した終了出力が複数あるときに，必要に応じて遷移生成制御部３３によって生成される遷移に対応する識別記号を決定する。ここで決定される識別記号は，ＦＳＴ読取部１０１が読み取ったＦＳＴに含まれているどの入力記号とも異なる記号となる。遷移生成制御部３３は，遷移の生成や終了状態を生成する処理の全体を制御する。
【０１４６】
なお，終了状態処理部３０は，図３の１３行目ないし２３行目の処理を行う。状態併合部３１は，図３の１５行目の処理を行う。記号決定部３２は，図３の２１行目の処理のうち，関数ａｕｘによる処理を行う。遷移生成制御部３３は，図３の１３行目ないし２３行目の処理のうち，状態併合部３１及び記号決定部３２による処理ではない処理を行う。
【０１４７】
単値化処理部４０は，同一の入力記号が割り当てられている複数の遷移を併合して単値化すると共に決定化する処理を行う。単値化処理部４０は，状態併合部４１，記号決定部４２，サブ状態生成部４３，遷移生成制御部４４を有する。
【０１４８】
状態併合部４１は，集合生成部１０により生成された集合の中から，同一の入力記号による遷移先にある複数の状態を取得し，それらをサブ状態として有する状態を生成する。同一の入力記号による遷移先の状態が一つだけの場合にも複数ある場合と同様にサブ状態を有するようにしておくと，サブ状態に関する処理が容易になる。
【０１４９】
記号決定部４２は，状態併合部４１により生成された一の状態に対し，入力記号として扱う識別記号を一または複数生成する。生成された識別記号のそれぞれは，一の状態からの出て行く一または複数の遷移に割り当てられる出力記号のそれぞれに対応する。ここで決定される識別記号は，記号決定部３２と同様に，ＦＳＴ読取部１０１が読み取ったＦＳＴに含まれているどの入力記号とも異なる記号となる。サブ状態生成部４３は，状態併合部４１が生成する状態に含まれるサブ状態を生成する。なお，記号決定部４２が生成する識別記号は，状態併合部４１が生成した状態毎に対応する。
【０１５０】
遷移生成制御部４４は，単値化処理部４０が行う処理の全体の制御を行う。
【０１５１】
なお，状態併合部４１は，図３の２５行目の処理を行う。記号決定部４２は，図３の２９行目の処理のうち，関数ａｕｘによる処理を行う。サブ状態生成部４３は，図３の２７行目と３４行目の処理を行う。遷移生成制御部４４は，図３の２４行目ないし３７行目の処理のうち，単値化処理部４０が有する他の処理部が行う処理ではない処理を行う。
【０１５２】
遷移選択部５０は，入力されるＦＳＴが重み付きＦＳＴの場合に，重みに基づいて，最良の経路となる遷移を選択する。
【０１５３】
（音声認識でのＦＳＴの具体例）
ＦＳＴは音声認識や自然言語処理の分野などで利用されている。ひとつの例として，音素列から単語へと変換する機能をＮＦＳＴとして実現する方法が挙げられる。一般的にはこのようなＮＦＳＴには決定化処理が施される。各状態からの遷移先の状態が入力記号を与えると一意に決まり，扱い易いからである。このとき，同音異表記語が存在すると，同じ発音列に対して異なる単語が割り当てられることになる。つまり単値でないＮＦＳＴが作成されることになる。具体的には図２１のようになる。この例では，入力記号を発音記号として，出力記号列を単語としている。発音列を数単語にわたって変換したいときは，この図の場合，入力記号と出力記号が共にεである状態５から状態０へと遷移を作成すればよい。
【０１５４】
（翻訳でのＦＳＴの具体例）
発音から単語へと変換できるＦＳＴを実現できるので，同様に，ある言語の文字を入力記号に，別の言語の文字列を出力記号に割り当てるとする。例えば，日本語で「会議」という文字列は英語ではｍｅｅｔｉｎｇ，ｃｏｎｆｅｒｅｎｃｅ，ｃｏｕｎｃｉｌなどに翻訳できるので，それをＦＳＴとして表すと図２２のようになる。この例の場合も単値なＦＳＴでないので，終了出力を割り当てないＦＳＴを用いる場合には，従来の方法によって決定化することができない。１単語だけでなく複数の単語を連続して他の言語に翻訳するには，状態１，２，３から状態４への遷移の遷移先を状態０に変更することで実現できる。このときは終了出力を複数割り当てられるＦＳＴを用いても，補助入力記号を追加する事前処理なしでは従来の決定化の方法では決定化することができない。本実施の形態の方法であれば，事前処理なしで決定化を行うことができる。
【０１５５】
（検索でのＦＳＴの具体例）
検索したい対象の文章をＦＳＴで表現すると，文書内の検索を容易に行うことができるようになる。
【０１５６】
例えば，「Ｇｏｏｄ  ｍｏｒｎｉｎｇ」という文章があったとする。文章の先頭「Ｇ」を１文字目，次の「ｏ」を２文字目のようにする。各文字が現れる文章内での位置を出力記号，文章内の文字を入力記号として，図２３のようなＦＳＴを作成する。＜ｓｐ＞はスペースを表すものとする。例えばこの文章内の文字列「ｒｎｉ」が出現する位置を検索したい場合，このＦＳＴに入力記号列「ｒｎｉ」を入力することになる。そうすると，状態０，状態８，状態９，状態１０と遷移し，出力記号列は「８」となる。つまり，「ｒｎｉ」は８文字目に出現することがわかる。入力記号に「ｏ」が割り当てられている状態０からの遷移を見ると，「ｏ：２」，「ｏ：３」，「ｏ：７」の３つがある。これらの遷移の遷移先は全て終了状態であるので，入力記号列として「ｏ」を入力すると，２，３，７の３種類を出力することができる。つまり，このＦＳＴは単値でないということである。
【０１５７】
ＦＳＴを決定化しておけば，検索したい文字列，つまり入力記号列に対するＦＳＴでの経路が一意に定まるので，検索時の計算量を決定化しない場合に比べて減らすことができる。一方，このＦＳＴは単値ではないため従来の決定化の手法では決定化できない。そこで本実施の形態における決定化を用いて単値なＦＳＴへと変形しながら決定化を行う。そして，決定化したＦＳＴを用いて検索するときには，補助入力記号を持つ遷移を全てε遷移とみなせばよい。ε遷移とは，入力記号を消費せずに次の状態へと遷移ができる遷移のことである。
【０１５８】
図２３のＦＳＴを本実施の形態における方法によって決定化したＦＳＴを図２４に示す。決定化後のＦＳＴへ入力記号列「ｏ」を入力すると，初期状態である状態０から状態１３へと遷移する。補助入力記号である＃１，＃２，＃３はεであるとみなすので，ＦＳＴに入力される入力記号列を消費せずに遷移できる先は状態１５のみである。それらの遷移の出力記号列は２，３，７なので，文章中の「ｏ」が現れる位置は，２文字目，３文字目，７文字目ということになる。ＦＳＴに入力される入力記号列が「ｏｒ」であれば，状態０から状態１３を経由して状態８へと遷移する経路が１つのみあり，その経路の出力記号は７である。つまり，「ｏｒ」が現れる位置は７文字目ということになる。
【０１５９】
（効果）
以上のように本実施の形態によると，事前に単値に変形する処理を行うことなく，単値でないＦＳＴを単値でないＦＳＴへと変形しながら決定化することができる。
【０１６０】
（実施の形態２）
（準備）
本実施の形態では，ＦＳＴの各遷移に割り当てられている入力記号と出力記号列に加えて，重みが加えられた，重み付き有限状態トランスデューサ（Ｗｅｉｇｈｔｅｄ  Ｆｉｎｉｔｅ  Ｓｔａｔｅ  Ｔｒａｎｓｄｕｃｅｒ，ＷＦＳＴ）の決定化方法のうち，単値でないＷＦＳＴを単値にしながら決定化する方法について述べる。ここでいう重みとは，何らかの確率値やスコア，ペナルティなどであり，入力記号を受理する経路に沿って何らかの規則（足し算，掛け算，最小値，最大値などなんでも良い）によって演算されるものである。
【０１６１】
重みがとりうる値の集合をＲｗとする。Ｒｗは例えば整数であったり実数であったりする。また，ＦＳＴの場合にはΔとしていた出力記号の集合をＲｏとする。そうすると，ＷＦＳＴは９つ組（Ｑ，Σ，Ｒｏ，Ｒｗ，Ｅ，Ｉ，Ｆ，λ，ρ）で表すことができる。Ｑ，Σ，Ｉ，Ｆ，λ，ρはＦＳＴの場合と同様である。遷移の集合Ｅに関しては，Ｅ⊆Ｑ×Σ×Δ×Ｑとなる。ここでΔを出力とし，Δ＝Ｒｏ＊×Ｒｗとした。遷移ｅ∈Ｅに割り当てられている出力記号列と重みはＦＳＴの場合と同じように，ｏｕｔ（ｅ）∈Δとする。つまり，ｏｕｔ（ｅ）は遷移ｅに割り当てられている２つ組（出力記号列，重み）を表すということである。初期出力関数λは初期状態をｉ∈Ｉとするときλ（ｉ）∈Δである。同様に終了状態をｑ∈Ｆとするとき，終了出力関数はρ（ｑ）∈Δである。
【０１６２】
（方法）
出力Δの計算方法を次のように定義すると，単値でないＷＦＳＴの決定化に実施の形態１の決定化方法をそのまま用いることができるようになる。
出力記号列Ｒｏの演算（＋）ｏと（×）ｏと特別な値１＃ｏを実施の形態１と同じように定義する。つまり，（＋）ｏを前方最長一致（ｌｏｎｇｅｓｔ  ｃｏｍｍｏｎ  ｐｒｅｆｉｘ）演算であると定義し，（×）ｏを結合演算であると定義し，１＃ｏを空記号列εであると定義する。
【０１６３】
重みＲｗの演算（＋）ｗと（×）ｗと特別な値１＃ｗは例えば次のように定義する。値ｘ，ｙ∈Ｒｗに対して，ｘ（＋）ｗｙ＝ｍｉｎ（ｘ，ｙ），ｘ（×）ｗｙ＝ｘ＋ｙと定義し，１＃ｗ＝０と定義する。これは非特許文献５でｔｒｏｐｉｃａｌ  ｓｅｍｉｒｉｎｇと呼ばれている演算方法である。他にも，ｘ（＋）ｗｙ＝ｘ＋ｙ，ｘ（×）ｗｙ＝ｘ×ｙと定義し，１＃ｗ＝１と定義することができる。非特許文献５でｌｏｇ  ｓｅｍｉｒｉｎｇと呼ばれている演算方法を用いることも可能である。
【０１６４】
以上のように出力記号列と重みの演算方法を定義すると，出力記号列と重みの２つ組である出力Δの演算（＋）と（×）と特別な値１＃は，ｘ１，ｘ２∈Ｒｏ，ｙ１，ｙ２∈Ｒｗであるとして，それぞれ（ｘ１，ｙ１）（＋）（ｘ２，ｙ２）＝（ｘ１（＋）ｏｘ２，ｙ１（＋）ｗｙ２），（ｘ１，ｙ１）（×）（ｘ２，ｙ２）＝（ｘ１（×）ｏｘ２，ｙ１（×）ｗｙ２），１＃＝（１＃ｏ，１＃ｗ）と定義できる。さらに出力Δに関する和集合の演算∪を次式のように定義する。
【０１６５】
【数１】
2010237806.tif 000003
【０１６６】
決定化後の状態ｑ∈Ｑ２と出力ｖ∈Δを引数にとり，戻り値として補助入力記号返すアルゴリズムａｕｘを図２５のようにする。１行目で出力Δの出力記号列と重みをそれぞれｘ，ｙとし，２行目で状態ｑと出力記号列ｘを引数としてａｕｘ０を呼び出し，その戻り値を返すという処理を行うということである。
ここで，ａｕｘ０は実施の形態１で使用したアルゴリズムａｕｘに相当し，例えば図４のような方法である。
【０１６７】
図３で使用されている（＋），（×），１＃，∪，ａｕｘを以上のように定義し直すと，単値でないＷＦＳＴに関しても，図３の方法により単値に変形しながら決定化を行うことができる。
【０１６８】
（例）
本実施の形態におけるＷＦＳＴの決定化方法がどのように動作するのかについて，図２６のＷＦＳＴを決定化前のＷＦＳＴ  Ｔ１とし，決定化後のＷＦＳＴをＴ２として説明する。初期出力と終了出力は１＃とし，図からは省略している。
【０１６９】
図２６よりＱ１＝｛０，１，２，３｝，Ｉ１＝｛０｝，Ｆ１＝｛３｝，Σ１＝｛ａ，ｂ｝，Ｒｏ＝｛Ａ，Ｂ｝である。Ｒｗは整数とする。実施の形態１におけるＦＳＴの図と同様に，太線の円が初期状態であり，二重線の円が終了状態を表している。各遷移のラベルのうち，「：」の左側が入力記号，「：」と「／」の間が出力記号列，「／」の右側が重みを表している。なお，この例では重みｘ，ｙ∈Ｒｗをｘ（＋）ｗｙ＝ｍｉｎ（ｘ，ｙ），ｘ（×）ｗｙ＝ｘ＋ｙ，１＃ｗ＝０で演算するものとする。そうすると，ｘ−１（×）ｘ＝１＃ｗよりｘ−１＋ｘ＝０であるので，ｘ−１＝−ｘとなる。
【０１７０】
図３の１行目でまず決定化後のＷＦＳＴの初期化が行われる。次に２行目で初期出力を計算する。この例のＷＦＳＴには初期出力はない。言い換えるとλ１（０）＝１＃＝（ε，０），つまり空記号列と重み０を出力するということである。したがって，λ２＝（ε，０）となる。
【０１７１】
３行目では決定化後のＷＦＳＴの初期状態を作成する。ｉ２＝｛（０，（ε，０））｝となる（図２７）。
【０１７２】
４行目では３行目で作成した状態ｉ２をスタックＳとＱ２に追加し，その結果，Ｓ＝｛｛（０，（ε，０））｝｝，Ｑ２＝｛｛（０，（ε，０））｝｝となる。
｜Ｓ｜＝１であるので，５行目の条件を満たし，６行目に処理を進める。
６行目でスタックＳから値を取り出し，ｑ２に代入すると，Ｓ＝φ，Ｑ２＝｛（０，（ε，０））｝となる。
【０１７３】
７行目では，判断しなければならないｗはｗ＝（ε，０）の場合のみである。ｗはΣ１には含まれていないので，７行目の条件は満たされない。したがって，１４行目に処理を進める。
【０１７４】
１４行目では，ｑ２に含まれている２つ組（状態，出力）のうちの状態がＦ１に含まれているか否かを判断する。いま，ｑ２に含まれる状態は状態０のみであり，これはＦ１には含まれていない。したがって，処理を２４行目に進める。
【０１７５】
Σ１＝｛ａ，ｂ｝ではあるが，状態０から出て行く遷移の入力記号はａのみであるので，α＝ａの場合のみを処理すればよい。したがって，２４行目ではα＝ａとして２５行目以降の処理を行う。
【０１７６】
２５行目では，θ＝｛（１，｛（ε，０）（×）（Ａ，１）｝），（２，｛（ε，０）（×）（Ａ，３）｝）｝＝｛（１，｛（ε（×）ｏＡ，０（×）ｗ１）｝），（２，｛（ε（×）ｏＡ，０（×）ｗ３）｝）｝＝｛（１，｛（Ａ，０＋１）｝），（２，｛（Ａ，０＋３）｝）｝＝｛（１，｛（Ａ，１）｝），（２，｛（Ａ，３）｝）｝となる。
２６行目の｜Ｗ｜＞１の条件を満たすθの要素はないので，３２行目へと処理を進める。
｜Ｗ｜＝１を満たすθの要素は存在するので３２行目の条件を満たし，３３行目へと処理を進める。
【０１７７】
３３行目の処理で，ｗ２＝（Ａ，１）（＋）（Ａ，３）＝（Ａ（＋）ｏＡ，１（＋）ｗ３）＝（Ａ，ｍｉｎ（１，３））＝（Ａ，１）となる。
３４行目の処理で，ｑｎ２＝｛（１，（Ａ，１）−１（×）（Ａ，１）），（２，（Ａ，１）−１（×）（Ａ，３））｝＝｛（１，（Ａ−１（×）ｏＡ，１−１（×）ｗ１）），（２，（Ａ−１（×）ｏＡ，１−１（×）ｗ３））｝＝｛（１，（ε，−１＋１）），（２，（ε，−１＋３））｝＝｛（１，（ε，０）），（２，（ε，２））｝が得られる。
３５行目で状態元状態が｛（０，（ε，０））｝で入力記号がａ，出力記号がＡ，重みが１，遷移先状態が｛（１，（ε，０）），（２，（ε，２））｝である遷移を作成しＥ２に加える。その結果，図２８の初期状態と状態Ｓ３０１とそれらの状態間の遷移から構成されるＦＳＴになる。
【０１７８】
今ｑｎ２はＱ２には含まれていないので３６行目を満たし，３７行目が処理される。
３７行目では，ｑｎ２をＳとＱ２に追加するので，Ｓ＝｛｛（１，（ε，０）），（２，（ε，２））｝｝，Ｑ２＝｛｛（０，（ε，０））｝，｛（１，（ε，０）），（２，（ε，２））｝｝となる。
【０１７９】
５行目に処理が戻り，スタックＳは空集合ではないので，６行目に処理を進む。
６行目で，ｑ２＝｛（１，（ε，０）），（２，（ε，２））｝となり，Ｓ＝φとなる。
（ε，０）も（ε，２）もΣ１には含まれていないので，７行目の条件は満たされず，１４行目に処理が進む。
【０１８０】
状態１，２はＦ１には含まれていない，つまり終了状態ではないので，１４行目の条件は満たさない。したがって２４行目に処理が進む。
状態１，２から出て行く遷移の入力記号はｂのみであるので，２５行目から３７行目の処理はα＝ｂの場合の処理のみを行えばよい。
【０１８１】
２５行目では，θ＝｛（３，｛（ε，０）（×）（Ａ，２）｝∪｛（ε，０）（×）（Ｂ，１）｝∪｛（ε，２）（×）（Ａ，５）｝∪｛（ε，２）（×）（Ａ，２）｝）｝＝｛（３，｛（Ａ，２）｝∪｛（Ｂ，１）｝∪｛（Ａ，７）｝∪｛（Ａ，４）｝）｝＝｛（３，｛（Ａ，２（＋）ｗ７）｝∪｛（Ｂ，１（＋）ｗ４）｝）｝＝｛（３，｛（Ａ，ｍｉｎ（２，７））｝∪｛（Ｂ，ｍｉｎ（１，４））｝）｝＝｛（３，｛（Ａ，２）｝∪｛（Ｂ，１）｝）｝＝｛（３，｛（Ａ，２），（Ｂ，１）｝）｝となる。
【０１８２】
２６行目ではθの要素のうち，（３，｛（Ａ，２），（Ｂ，１）｝）が｜Ｗ｜＞１の条件を満たすので，これについて２７行目から３１行目の処理を行う。
２７行目で，ｑｎ２＝｛（ｑｎ，α）｝＝｛（３，ｂ）｝となり，２８行目へと処理が進む。
【０１８３】
いま，Ｗ＝｛（Ａ，２），（Ｂ，１）｝であるので，まず，ｗ＝（Ａ，２）について２９行目の処理を行う。ここでａｕｘ（ｑｎ２，ｗ）＝ａｕｘ（｛（３，ｂ）｝，（Ａ，２））＝＃１とする。そうすると，２９行目では，遷移元状態が｛（１，（ε，０）），（２，（ε，２））｝，入力記号が＃１，出力が（Ａ，２），遷移先状態が｛（３，ｂ）｝である遷移がＥ２に追加され，さらにΣ２に＃１が追加される。同様にｗ＝（Ｂ，１）についても処理を行うが，このときａｕｘ（｛（３，ｂ）｝，（Ｂ，１））＝＃２とすると，遷移元状態が｛（１，（ε，０）），（２，（ε，２））｝，入力記号が＃２，出力が（Ｂ，１），遷移先状態が｛（３，ｂ）｝である遷移がＥ２に追加され，さらにΣ２に＃２が追加される。その結果，図２８の初期状態と状態Ｓ３０１と状態Ｓ３０２と，それらの状態間の遷移から構成されるＦＳＴになる。
【０１８４】
３０行目で，Ｑ２に｛（３，ｂ）｝が含まれていないと判定され，３１行目でＳとＱ２に｛（３，ｂ）｝が追加される。その結果，Ｓ＝｛｛（３，ｂ）｝｝，Ｑ２＝｛｛（０，（ε，０））｝，｛（１，（ε，０）），（２，（ε，２））｝，｛（３，ｂ）｝｝となる。
【０１８５】
３２行目の処理に進むが，｜Ｗ｜＝１を満たす要素がθに含まれていないので，３２行目の条件を満たさない。したがって，３３行目以降の処理は行われず，５行目に処理が戻る。
【０１８６】
Ｓは空集合ではないので６行目に処理を進める。
６行目でｑ２＝｛（３，ｂ）｝となる。また，Ｓ＝φとなる。
ｑ２に含まれる記号列はｂであるので，７行目の条件を満たし，８行目へ処理を進める。
【０１８７】
８行目で，ｑ＝３，ｗ＝ｂとなる。
９行目で，ｑｎ２＝｛（３，１＃）｝＝｛（３，（ε，０））｝となる。
１０行目で，遷移元状態が｛（３，ｂ）｝，入力記号がｂ，出力記号列がε，重みが０，遷移先状態が｛（３，（ε，０））｝の遷移がＥ２に追加される。その結果，図２８の状態Ｓ３０３を含む全ての状態と遷移から構成されるＦＳＴになる。
【０１８８】
ｑｎ２＝｛（３，ε）｝であるので，１１行目の条件を満たし，１２行目へ処理を進める。
１２行目で，ＳとＱ２に｛（３，（ε，０））｝が追加される。その結果，Ｓ＝｛｛（３，（ε，０））｝｝，Ｑ２＝｛｛（０，（ε，０））｝，｛（１，（ε，０）），（２，（ε，２））｝，｛（３，ｂ）｝，｛（３，（ε，０））｝｝となる。
【０１８９】
５行目に処理が戻るが，Ｓは空ではないので６行目に処理を進める。
６行目でｑ２＝｛（３，（ε，０））｝となる。また，Ｓ＝φとなる。
ｑ２に含まれる記号列は（ε，０）のみであるので，７行目の条件を満たさない。そのため，１４行目に処理が進む。
【０１９０】
状態３は終了状態なので，１４行目の条件を満たし，１５行目の処理へ進む。
ρ１（３）＝（ε，０）であるので，１５行目でＷ＝｛（ε，０）（×）（ε，０）｝＝｛（ε，０）｝となる。
１６行目で，ｗ２＝｛（ε，０）｝となる。
Ｗの要素は１つで，それは（ε，０）であるので，１７行目の条件を満たし，１８行目へ処理を進める。
【０１９１】
１８行目で，ρ２（｛（３，（ε，０））｝）＝（ε，０），Ｆ２＝｛｛（３，（ε，０））｝｝となる。その結果，図２９のようになる。
【０１９２】
１９行目を満たすＷの要素はないので，２０行目から２３行目は処理されず，２４行目の処理へ進む。
状態３から出て行く遷移は存在しないので，２４行目以降の処理を行っても何も起きない。
【０１９３】
５行目に処理が戻るが，いまＳは空集合なので，５行目の条件を満たさない。したがって，決定化処理が完了したことになる。
ＦＳＴの場合と同様に，各状態に関連付けられている２つ組の集合を番号に置き換えて，図３０のようにすることもできる。
【０１９４】
（音声認識での具体例）
ＷＦＳＴを用いた具体例として，音声認識の単語辞書に単語ごとに挿入ペナルティを重みとして設定したＷＦＳＴを図３１に挙げる。この場合，ｓｅｅを出力する場合は挿入ペナルティが１０，ｓｅａを出力するときは挿入ペナルティが２０となる。音声認識における他の使用例については非特許文献４に記述がある。
【０１９５】
以上のように，実施の形態２の方法によると，単値でないＷＦＳＴを単値なＷＦＳＴへと変形しながら決定化することができる。
【０１９６】
なお，本発明は，上記実施の形態そのままに限定されるものではなく，実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化することができる。また，上記実施の形態に開示されている複数の構成要素の適宜な組み合わせにより，種々の発明を形成することができる。例えば，実施の形態に示される全構成要素からいくつかの構成要素を削除してもよい。さらに，異なる実施の形態にわたる構成要素を適宜組み合わせても良い。
【０１９７】
以上のように，本発明にかかる決定化装置は，音声認識技術や翻訳技術，要約技術に適している。
【符号の説明】
【０１９８】
１０   集合生成部
２０   単値状態処理部
２１   状態取得部
２２   遷移生成制御部
３０   終了状態処理部
３１   状態併合部
３２   記号決定部
３３   遷移生成制御部
４０   単値化処理部
４１   状態併合部
４２   記号決定部
４３   サブ状態生成部
４４   遷移生成制御部
５０   遷移選択部
１００ 決定化装置
１０１ ＦＳＴ読取部
１０９ ＦＳＴ書込部
２７００      決定化装置
【図１】
2010237806.tif 000004
【図２】
2010237806.tif 000005
【図３−１】
2010237806.tif 000006
【図３−２】
2010237806.tif 000007
【図４】
2010237806.tif 000008
【図５】
2010237806.tif 000009
【図６】
2010237806.tif 000010
【図７】
2010237806.tif 000011
【図８】
2010237806.tif 000012
【図９】
2010237806.tif 000013
【図１０】
2010237806.tif 000014
【図１１】
2010237806.tif 000015
【図１２】
2010237806.tif 000016
【図１３】
2010237806.tif 000017
【図１４】
2010237806.tif 000018
【図１５】
2010237806.tif 000019
【図１６】
2010237806.tif 000020
【図１７】
2010237806.tif 000021
【図１８】
2010237806.tif 000022
【図１９】
2010237806.tif 000023
【図２０】
2010237806.tif 000024
【図２１】
2010237806.tif 000025
【図２２】
2010237806.tif 000026
【図２３】
2010237806.tif 000027
【図２４】
2010237806.tif 000028
【図２５】
2010237806.tif 000029
【図２６】
2010237806.tif 000030
【図２７】
2010237806.tif 000031
【図２８】
2010237806.tif 000032
【図２９】
2010237806.tif 000033
【図３０】
2010237806.tif 000034
【図３１】
2010237806.tif 000035