"有限状態オートマトンに含まれる第1状態から出て行く遷移であって、第1記号が割り当てられている第1遷移が2以上存在する場合に、新たな第2状態を生成する状態生成ステップと、前記第1状態から前記第2状態への遷移であって、前記第1記号が割り当てられた第2遷移を生成する第1遷移生成ステップと、前記第1遷移それぞれに対して、前記第1遷移の次の状態から出て行く遷移である第3遷移の前の状態を前記第2状態に置き換えた第4遷移を生成する第2遷移生成ステップと、前記第4遷移を生成した前記第1遷移の次の状態であって、前記第1遷移以外に入ってくる遷移が存在しない状態を削除し、削除した状態から出て行く遷移を削除し、前記第4遷移を生成した前記第1遷移を削除する第1削除ステップと、を含むことを特徴とするオートマトン決定化方法。前記第3遷移と前記第4遷移とを関連づける第1関連づけステップと、前記第1遷移生成ステップにより前記第2遷移を生成するときに、前記第1遷移に他の遷移が関連づけられている場合に、生成された前記第2遷移と前記他の遷移とを関連づける第2関連づけステップと、前記有限状態オートマトンに含まれる2つの状態が、前記状態から出て行く遷移に関連づけられた遷移についての予め定められた基準を満たす場合に、2つの前記状態が等価であると判定する判定ステップと、等価であると判定された2つの前記状態のうち一方の状態に入ってくる遷移の次の状態を他方の状態につなぎ替えるつなぎ替えステップと、をさらに含むこと、を特徴とする請求項1に記載のオートマトン決定化方法。前記基準は、前記一方の状態から出て行く遷移に関連づけられているすべての遷移と、前記他方の状態から出て行く遷移に関連づけられているすべての遷移と、が一致することを定める基準であること、を特徴とする請求項2に記載のオートマトン決定化方法。前記第1遷移の次の状態と前記第2状態とを関連づける第3関連づけステップと、前記状態生成ステップにより前記第2状態を生成するときに、前記第1遷移の次の状態に他の状態が関連づけられている場合に、生成された前記第2状態と前記他の状態とを関連づける第4関連づけステップと、前記有限状態オートマトンに含まれる2つの状態が、前記状態に関連づけられた状態についての予め定められた基準を満たす場合に、2つの前記状態が等価であると判定する判定ステップと、等価であると判定された2つの前記状態のうち一方の状態に入ってくる遷移の次の状態を他方の状態につなぎ替えるつなぎ替えステップと、をさらに含むこと、を特徴とする請求項1に記載のオートマトン決定化方法。前記基準は、前記一方の状態に関連づけられているすべての状態と、前記他方の状態に関連づけられているすべての状態と、が一致することを定める基準であること、を特徴とする請求項4に記載のオートマトン決定化方法。前記有限状態オートマトンは、重み付き有限状態オートマトンであり、前記第1遷移それぞれの重みから予め定められた演算により算出される重みの最良値である、前記第2遷移の重みを算出する重み算出ステップをさらに含むこと、を特徴とする請求項1に記載のオートマトン決定化方法。前記第3遷移と前記第4遷移とを関連づけるとともに、前記第4遷移の重みを関連づけに割り当てる第5関連づけステップと、前記第1遷移生成ステップにより前記第2遷移を生成するときに、前記第1遷移に他の遷移が関連づけられている場合に、生成された前記第2遷移と前記他の遷移とを関連づける第6関連づけステップと、前記重み付き有限状態オートマトンに含まれる2つの状態が、前記状態から出て行く遷移に関連づけられた遷移についての予め定められた基準を満たす場合に、2つの前記状態が等価であると判定する判定ステップと、等価であると判定された2つの前記状態のうち一方の状態に入ってくる遷移の次の状態を他方の状態につなぎ替えるつなぎ替えステップと、をさらに含むこと、を特徴とする請求項6に記載のオートマトン決定化方法。前記基準は、前記一方の状態から出て行く遷移に関連づけられているすべての遷移およびすべての関連づけの重みと、前記他方の状態から出て行く遷移に関連づけられているすべての遷移およびすべての関連づけの重みと、が一致することを定める基準であること、を特徴とする請求項7に記載のオートマトン決定化方法。前記有限状態オートマトンは、有限状態トランスデューサであり、前記第1遷移それぞれの出力記号列の最長前方一致の記号列である、前記第2遷移の出力記号列を算出する記号列算出ステップをさらに含むこと、を特徴とする請求項1に記載のオートマトン決定化方法。前記第3遷移と前記第4遷移とを関連づけるとともに、前記第4遷移の出力記号列を関連づけに割り当てる第7関連づけステップと、前記第1遷移生成ステップにより前記第2遷移を生成するときに、前記第1遷移に他の遷移が関連づけられている場合に、生成された前記第2遷移と前記他の遷移とを関連づける第8関連づけステップと、前記有限状態トランスデューサに含まれる2つの状態が、前記状態から出て行く遷移に関連づけられた遷移についての予め定められた基準を満たす場合に、2つの前記状態が等価であると判定する判定ステップと、等価であると判定された2つの前記状態のうち一方の状態に入ってくる遷移の次の状態を他方の状態につなぎ替えるつなぎ替えステップと、をさらに含むこと、を特徴とする請求項9に記載のオートマトン決定化方法。前記基準は、前記一方の状態から出て行く遷移に関連づけられているすべての遷移およびすべての関連づけの出力記号列と、前記他方の状態から出て行く遷移に関連づけられているすべての遷移およびすべての関連づけの出力記号列と、が一致することを定める基準であること、を特徴とする請求項10に記載のオートマトン決定化方法。初期状態から到達できない状態と遷移とを、予め定められた頻度で削除する第2削除ステップをさらに含むこと、を特徴とする請求項1に記載のオートマトン決定化方法。前記第2削除ステップは、1つの前記第1状態について、前記状態生成ステップ、前記第1遷移生成ステップ、前記第2遷移生成ステップ、および、前記第1削除ステップのうちいずれかが完了するごとに、初期状態から到達できない状態と遷移とを削除すること、を特徴とする請求項12に記載のオートマトン決定化方法。有限状態オートマトンに含まれる第1状態から出て行く遷移であって、第1記号が割り当てられている第1遷移が2以上存在する場合に、新たな第2状態を生成する状態生成部と、前記第1状態から前記第2状態への遷移であって、前記第1記号が割り当てられた第2遷移を生成する第1遷移生成部と、前記第1遷移それぞれに対して、前記第1遷移の次の状態から出て行く遷移である第3遷移の前の状態を前記第2状態に置き換えた第4遷移を生成する第2遷移生成部と、前記第4遷移を生成した前記第1遷移の次の状態であって、前記第1遷移以外に入ってくる遷移が存在しない状態を削除し、削除した状態から出て行く遷移を削除し、前記第4遷移を生成した前記第1遷移を削除する削除部と、を備えることを特徴とするオートマトン決定化装置。コンピュータに、有限状態オートマトンに含まれる第1状態から出て行く遷移であって、第1記号が割り当てられている第1遷移が2以上存在する場合に、新たな第2状態を生成する状態生成ステップと、前記第1状態から前記第2状態への遷移であって、前記第1記号が割り当てられた第2遷移を生成する第1遷移生成ステップと、前記第1遷移それぞれに対して、前記第1遷移の次の状態から出て行く遷移である第3遷移の前の状態を前記第2状態に置き換えた第4遷移を生成する第2遷移生成ステップと、前記第4遷移を生成した前記第1遷移の次の状態であって、前記第1遷移以外に入ってくる遷移が存在しない状態を削除し、削除した状態から出て行く遷移を削除し、前記第4遷移を生成した前記第1遷移を削除する第1削除ステップと、を実行させるためのオートマトン決定化プログラム。しかしながら、従来技術では、NFSAを記憶領域に保ったまま、DFSAを新たに生成する方法が用いられている。このような方法では、状態や遷移を多量に含んでいるNFSAを決定化しようとした場合に多くの記憶領域が必要になるという問題があった。実施形態のオートマトン決定化方法は、状態生成ステップと、第1遷移生成ステップと、第2遷移生成ステップと、第1削除ステップと、を含む。状態生成ステップは、有限状態オートマトンに含まれる第1状態から出て行く遷移であって、第1記号が割り当てられている第1遷移が2以上存在する場合に、新たな第2状態を生成する。第1遷移生成ステップは、第1状態から第2状態への遷移であって、第1記号が割り当てられた第2遷移を生成する。第2遷移生成ステップは、第1遷移それぞれに対して、第1遷移の次の状態から出て行く遷移である第3遷移の前の状態を第2状態に置き換えた第4遷移を生成する。第1削除ステップは、第4遷移を生成した第1遷移の次の状態であって、第1遷移以外に入ってくる遷移が存在しない状態を削除し、削除した状態から出て行く遷移を削除し、第4遷移を生成した第1遷移を削除する。以下に添付図面を参照して、この発明にかかるオートマトン決定化装置の好適な実施形態を詳細に説明する。第1の実施形態第1の実施形態にかかるオートマトン決定化装置は、NFSAを変形することにより決定化を行う。同じ記憶領域でより多くの状態や遷移を含んだNFSAを決定化するために、NFSAに含まれる状態や遷移のうち、決定化にとって不要となった状態や遷移を記憶領域から逐次削除することによって決定化に必要となる記憶領域を減らす。これにより、より少ない記憶領域で有限状態オートマトンの決定化を行うことができる。特に、ある入力記号に対する次の状態が複数存在するような状態、すなわち、非決定性の状態の全体に占める割合が少ないNFSAを決定化するときの記憶領域の削減に効果的である。準備WFSAは、状態の集合Qと遷移の集合E、入力記号の集合Σ、重みの集合K、初期状態の集合I、終了状態の集合F、初期重み関数λ、終了重み関数ρを含む8つ組Q,E,Σ,K,I,F,λ,ρから構成される。遷移は4つ組前状態,入力記号,重み,次状態で構成される。集合Kは、整数全体からなる集合、実数全体からなる集合、複素数全体からなる集合、行列、ブーリアン0と1のみから成る集合、および、文字列から成る集合など様々な集合に対応させることができる。集合Kは、正でない実数からなる集合や負でない実数からなる集合などに対応させることもできる。初期状態qi∈Iに対応する初期重みはλqiとなる。同様に終了状態qf∈Fに対応する終了重みはρqfとなる。終了状態でない状態qがρの引数に与えられた場合は、集合Kに含まれない値を返し、その値は終了状態でないすべての状態に対して同じ値であるとする。これら8つの集合は本実施形態での決定化の対象となるWFSAを構成する情報としてすべての方法擬似コードから常に参照することができるものとする。WFSAの決定化を行うには集合Kに対し2つの2項演算と×、さらに定数0と1を定義できる必要がある。ここではこのような演算と定数を伴う集合Kが、半環semiringと呼ばれる条件を満たしているものとする。さらに、ab≠0を満たす任意のa,b∈Kに対して、c=ab-1×aとなるようなcが存在する必要がある。なお、xの逆元をx-1と書く。すなわち、x-1×x=1である。集合Kが半環であるとは次の1~4の4つの条件を満たすことを意味する。1Kが演算に対して可換モノイドであり、その単位元が0である。2Kが演算×に対してモノイドであり、その単位元が1である。3任意のx,y,z∈Kに対して分配法則が成り立つ。すなわち、x×yz=x×yx×zと、yz×x=y×xz×xと、を満たす。4任意のx∈Kに対して、0×x=x×0=0が成り立つ。上記のような条件を満たす半環には、例えばトロピカル半環tropicalsemiring、または、minplussemiringと呼ばれるものが存在する。トロピカル半環は、集合Kが0以上の実数Rに無限大∞を加えた集合である。トロピカル半環は、がmin、×が、0が∞、1が0であるような演算と定数を伴う。集合Kが0以上の整数Nに∞を加えた集合も同様にトロピカル半環と呼ばれる。集合Kが0以下の実数R-に-∞を加えた集合でがmax、×が、0が-∞、1が0であるような半環や、トロピカル半環のの計算をxy=-loge-xe-yに置き換えた対数半環logsemiringも条件を満たす。集合Kが文字列で、が前方最長一致longestcommonprefix、×が連結、1が空文字列εと書く、0がτであるような文字列半環stringsemiringも条件を満たす。ここでτは、任意の文字列xに対してxτ=τx=xとなるような文字列であり、εはε×x=x×ε=xとなるような文字列であるとする。逆元も定義でき、任意の文字列x、yに対して、x-1×x×y=yとなる。文字列半環を用いることで、FSTをWFSAと同様に扱うことができる。他にも様々な半環が知られている。WFSTの場合はFSTに重みが加わっているが、上記条件を満たす半環と文字列半環とを組み合わせた半環を用いることでWFSAと同様に扱うことができる。例えば、重みにトロピカル半環、出力文字列に文字列半環を用いる場合には、集合Kを重みの集合R∪{∞}と文字列の集合Σとの組み合わせとする。そして、任意の重みa,b∈R∪{∞}と文字列x,y∈Σに対してをa,xb,y=ab,xy、×をa,x×b,y=a×b,x×y、0=∞,τ、1=0,εのように定義することで、WFSTをWFSAの場合と同様に扱うことができる。遷移eの前状態はpe、次状態はne、入力記号はine、重みはweで表す。遷移の集合Eに含まれる遷移の次状態から成る集合をnEで表す。空集合はφまたは{}と書く。集合Bの要素の数は|B|と書く。差集合は\で表す。例えば{1、2}\{2}={1}である。集合Wの各要素について演算を行うことを以下の数1で表す。各要素をw1,w2,w3,,w|W|とするとき、w1w2w3w|W|と書くことと同じである。重みの最良値とは、対象となる重みの各要素について演算を行った結果である。対象となる重みが同じであっても使用する半環が異なると重みの最良値が異なる値になることがある。例えば重みの集合{1,2,3}に対してがminであるような半環を用いている場合は、重みの最良値は1になる。がmaxであるような半環を用いている場合は重みの最良値は3になる。方法の概要以下では、オートマトン決定化装置を音声認識装置に適用した例を説明するが、適用可能な装置はこれに限られるものではない。また、以下では、WFSAを対象とした決定化方法を例に説明するが、他のFSAについても同様の手順を適用できる。図1は、音声認識装置100の構成例を示すブロック図である。図1に示すように、音声認識装置100は、モデル生成部110と、音声認識部130と、音響モデル121と、単語辞書122と、言語モデル123と、を備えている。音声認識部130は、入力された音声を認識し、音声認識結果を出力する。音声認識部130は、音声取得部131と、特徴抽出部132と、デコード部133と、ラティス処理部134と、出力部135と、を備えている。音声取得部131は、各種記憶装置図示せずに記録された音声、マイクからの入力音声、および、通信回線から入力される音声などを取り込み、特徴抽出部132に取り込んだ音声を渡す。特徴抽出部132は、受け取った音声から音声の特徴量を抽出してデコード部133に渡す。デコード部133は、モデル生成部110が生成したモデルを用いて、受け取った特徴量をデコードし、デコードの結果をラティス単語ラティスや音素ラティスなどとしてラティス処理部134に渡す。ラティス処理部134は、決定化部113を備えている。ラティスはFSAの一種であるので、ラティス処理部134は必要に応じて決定化部113を用いて決定化を行う。ラティス処理部134は、例えばラティス中で認識結果として最も尤もらしい系列を求め、それを認識結果として出力部135に渡す。出力部135は、受け取った認識結果を、画面等を用いてユーザに出力提示する。音響モデル121は、特徴抽出部132が抽出する特徴量に対応する音素を見つけるための情報を記録する。単語辞書122は、音素列と単語との対応付けを記録する。言語モデル123は、単語列の尤もらしい並びを見つけるための情報を記録する。認識できる単語の並びを表す文法を言語モデル123の代わりに用いるように構成しても良い。モデル生成部110は、デコード部133で用いるためのWFSTで表現されたモデルを生成する。モデル生成部110は、音響モデル121、単語辞書122、および、言語モデル123を入力とし、入力されたモデルをWFSTに変換したモデルを生成する。単語辞書から変換されたWFSTの入力記号には音素、出力記号には単語、重みには例えば0が割り当てられる。言語モデルから変換されたWFSTの入力記号と出力記号には単語が、重みには単語列の尤もらしい並びを見つけるための値が割り当てられる。モデル生成部110は、モデル変換部111と、合成部112と、決定化部113と、最小化部114と、を備えている。モデル変換部111は、入力されたモデル音響モデル121、単語辞書122、言語モデル123をWFSTへと変換する。合成部112は、変換された複数のWFSTを合成する。例えば単語辞書122から生成されたWFSTと言語モデル123から生成されたWFSTを合成すると、入力記号が音素で出力記号が単語、重みが単語列の尤もらしい並びを見つけるための値に対応するWFSTが生成される。決定化部113は、合成前や合成後のWFSTを必要に応じて決定化する。最小化部114は、決定化されたWFSTの状態や遷移ができる限り少なくなるようにWFSTを変形する。このように、本実施形態では、音声認識におけるモデル作成時モデル生成部110の決定化部113、および、デコード時に生成されるラティスを処理する際ラティス処理部134の決定化部113の少なくとも一方で決定化処理が実行される。既に述べたように決定化に関してWFSTとWFSAは同様に扱うことができるため、以下で述べる説明ではWFSAを用いる。図2は、決定化部113の詳細な構成例を示すブロック図である。決定化部113は、併合部150と、判定部161と、削除部162と、つなぎ替え部163と、を含む。併合部150は、決定化のために遷移を併合し、必要に応じて状態を生成する。併合部150は、状態生成部151と、遷移生成部152と、関連づけ部153と、重み算出部154と、を備えている。状態生成部151は、決定化の際に必要な状態を生成する。例えば、状態生成部151は、決定化するWFSAに含まれる各状態第1状態について、当該状態から出て行く遷移であって、同一の記号が割り当てられている遷移第1遷移が2以上存在する場合に、新たな状態第2状態を生成する。遷移生成部152は、決定化の際に必要な遷移を生成する。例えば、遷移生成部152は、第1状態から第2状態への遷移第2遷移を生成する。また、遷移生成部152は、第1遷移の次の状態から出て行く遷移第3遷移の前の状態を第2状態に置き換えた遷移第4遷移を生成する。関連づけ部153は、遷移生成部152により生成される遷移と、既にWFSAに含まれる遷移であって遷移生成の根拠となる遷移とを関連づける。例えば、関連づけ部153は、第3遷移と第4遷移とを関連づける。重み算出部154は、生成される遷移の重みを算出する。例えば、重み算出部154は、複数の第1遷移それぞれの重みから予め定められた演算により算出される重みの最良値を、第2遷移の重みとして算出する。判定部161は、決定化するWFSAに含まれる2つの状態が等価であるか否かを判定する。例えば、判定部161は、2つの状態が、状態から出て行く遷移に関連づけられた遷移についての予め定められた基準を満たす場合に、2つの状態が等価であると判定する。判定部161は、例えば、一方の状態から出て行く遷移に関連づけられているすべての遷移と、他方の状態から出て行く遷移に関連づけられているすべての遷移と、が一致することを基準として利用する。削除部162は、併合部150の処理によって不要になった状態や遷移を記憶領域から削除する。判定部161により、ある状態が別の状態と等価であると判定された場合は、削除部162は、一方の状態を削除する。環状経路が存在しないFSAを決定化する場合には、判定部161が存在しなくても決定化そのものは実行できる。ただし、決定化後のFSAの状態や遷移は、判定部161が存在する場合に比べ多くなることがある。つなぎ替え部163は、必要に応じて、遷移の接続先の状態を変更する。すなわち、つなぎ替え部163は、遷移のつなぎ替えを行う。例えば、つなぎ替え部163は、等価であると判定された2つ状態のうち一方の状態に入ってくる遷移の次の状態を他方の状態につなぎ替える。次に、このように構成された第1の実施形態にかかる音声認識装置100による決定化処理について図3を用いて説明する。図3は、第1の実施形態における決定化処理の全体の流れを示すフローチャートである。なお、図3のフローチャートは、第1の実施形態のみでなく、以下に説明するすべての実施形態における決定化処理の流れの概要を表す。決定化部113は、処理開始時に、決定化するNFSA本実施形態では非決定性WFSAをRAMなどの記憶装置の記憶領域に読み込むステップS101。決定化部113は、すべての状態について決定化が完了するまでステップS102からステップS103を繰り返し処理する。ステップS102では、決定化部113の併合部150は、まだ決定化が終わっていない状態を初期状態の側から順に決定化する。ステップS103では、決定化部113の削除部162が、ステップS102の決定化により不要になった状態や遷移を記憶領域から削除する。決定化部113はすべての状態を決定化したか否かを判断しステップS104、決定化していない場合はステップS104:No、ステップS102に戻り処理を繰り返す。すべての状態を決定化した場合ステップS104:Yes、決定化処理を終了する。以下に、決定化処理の詳細な例を説明する。図4は、本実施形態におけるWFSAの決定化処理の擬似コードの一例を示す図である。決定化を行う非決定性WFSAA=Q,E,Σ,K,I,F,λ,ρは、最初に記憶領域に記憶されているものとする。本実施形態では、この記憶領域に記録されているQ、E、I、F、λ、ρを順次変更することによって決定化を行う。1行目では後述する3つ組からなる集合Mを空集合に初期化する。なお、Mは、いずれの擬似コードからでも参照できるものとする。2行目では関数mergeInitialsによって初期状態を1つの状態に併合する。mergeInitialsについては後で述べる。3行目では集合SにIを代入する。さらに処理済か否かを判断するための集合Q’にIを代入する。ここで、集合Sはスタックでもキューでも何でも良い。4行目ではSが空集合か否かを判定する。空集合でなければ5行目から24行目までの処理を行う。5行目ではSから1つ状態を取り出し、qに代入する。6行目ではqから出て行く遷移outgoingtransitionを集合Eoutに代入する。7行目ではEoutに含まれる遷移の入力記号をΣoutに代入する。8行目はΣoutに含まれる各入力記号σについて9行目から24行目までの処理を行うことを表す。9行目では入力記号がσであるようなEoutに含まれる遷移をEσに代入する。10行目ではEσに含まれる遷移の次状態の数が1か否かを判定し、1なら11行目から13行目を、そうでなければ15行目から24行目を処理する。11行目は関数mergeWeightを呼び出す。引数としてEσを渡し、戻り値として得られる状態をqnに代入する。関数mergeWeightは、Eσが複数の遷移を含んでいるときに遷移を1つに併合する処理を行う。詳細は後述する。12行目ではqnがQ’に含まれているかを判定し、含まれていなければ13行目を処理する。13行目ではSとQ’にqnを追加する。15行目では関数mergeTransitionsを呼び出す。この関数は遷移の併合を行い、それに必要な新しい状態を生成し、その状態を戻り値として返す。その状態をqnewとする。関数mergeTransitionsが、例えば状態生成部151、遷移生成部152および関連づけ部153の機能に相当する。16行目ではqnewを引数として関数reconnectを呼び出す。この関数は、状態qnewと等価な状態が存在するか否かを判断し、存在する場合はtrueを、存在しない場合がfalseを返す。また、等価な状態が存在すれば、状態qへ入ってくる遷移incomingtransitionの次状態を、その状態へと変更する処理つなぎ替えを行う。ここで等価な状態とは、本明細書においては、一方を他方の状態であるとしてもWFSAが受理する言語や出力する重みに影響を及ぼさないことをいう。アクセプタの場合は、重みが存在しないが、その場合は受理する言語に影響を及ぼさないことをいう。この関数の詳細は後述する。戻り値がfalseであれば17行目でSにqnewを追加する。関数reconnectが、例えばつなぎ替え部163の機能に相当する。18行目はEσに含まれる遷移の次状態から成る集合に含まれる各状態qnについて19行目から23行目を処理することを示す。19行目ではqnに入ってくる遷移がすべてEσに含まれているか否かを判定し、そうであれば20行目から23行目を処理する。20行目では集合Erにqnから出て行く遷移を代入する。21行目では集合Esに遷移を代入する。その遷移は、集合Mに含まれる3つ組連結元の遷移,連結先の遷移,重みのうち、連結先の遷移edがErに含まれているような連結元の遷移esである。22行目では集合Mに含まれる3つ組のうち、連結元の遷移esがEsに含まれているような3つ組を集合Mから削除する。遷移esの前状態から出て行く遷移を連結元の遷移とするような集合Mに含まれる3つ組を集合Mから削除することで、決定化に必要な記憶領域をさらに削減することもできる。23行目では遷移の集合EからErに含まれる遷移を削除する。また、状態の集合Qから状態qnを削除する。24行目では遷移の集合EからEσを削除する。25行目では24行目までの処理で削除できなかった状態と遷移を削除する。削除する状態は、初期状態から到達できない状態である。また、削除する遷移は、初期状態から到達できない状態が前状態か次状態であるような遷移である。言い換えると、初期状態から辿って通過することができない遷移である。25行目の削除処理は、4行目による5行目から24行目までの繰り返し処理が一定回数完了するたびに実施するよう構成することもできるし、15行目から24行目までの処理が一定回数完了するたびに実施するよう構成することもできる。すなわち、任意の予め定められた頻度で、初期状態から到達できない状態と遷移とを削除するように構成することができる。図5は、関数mergeInitialsの詳細な擬似コードの一例を示す図である。1行目では初期状態が1つだけか否かを判定する。1つだけなら何もせず、2行目でこの関数での処理を終え、3行目以降の処理が行われることはない。3行目では新たな初期状態を作成するためQに含まれない新しい状態qnewを生成する。4行目では初期状態の集合Iに含まれる各状態に対応する初期重みを演算によって計算し、その結果をqnewの初期重みとしてλqnewに記録する。5行目は各初期状態について6行目から10行目を処理することを示す。6行目はqから出て行く各遷移eについて7行目から10行目を処理することを示す。7行目では新しい遷移enewを生成する。ここで遷移enewは、前状態をqnew、次状態を遷移eの次状態、入力記号を遷移eの入力記号、重みをλqnewの×に対する逆元とλqと遷移eの重みを×で演算した結果とする。8行目ではenewを集合Eに追加する。9行目はIに含まれるすべての初期状態が、入ってくる遷移を持っている場合、10行目を処理することを表す。入ってくる遷移が1つも存在しない初期状態が1つでも存在する場合、qnewと等価な状態がこれ以降の処理で現れることがない。このため、等価な状態の判定のために使う集合Mに3つ組を追加する必要がなく、10行目を処理する必要がない。10行目では3つ組enew,e,wenewをMに追加する。11行目は初期状態であり、かつ、終了状態でもあるような状態が存在するか否かを判定する。初期状態かつ終了状態である状態が存在すれば12行目の処理を行う。12行目ではqnewを終了状態の集合Fに追加する。さらに、終了重みρqnewを設定する。終了重みに設定される値は、終了状態でもある各初期状態qに対して、qnewの初期重みの逆元とqの初期重みとqの終了重みを×で演算し、各状態に対して得られたすべての値をで演算した結果とする。13行目ではIをqnewのみから成る集合にし、qnewをQに追加する。入ってくる遷移を持つ初期状態以外の状態をQから削除する。さらに削除した状態から出て行く遷移を削除する。図6は、関数mergeTransitionsの詳細な擬似コードの一例を示す図である。1行目ではQに含まれない新しい状態qnewを生成する。2行目では集合Eσに含まれる遷移の重みをで演算した結果をwpに代入する。すなわち、wpには集合Eσに含まれる遷移の重みの最良値が代入される。3行目ではEσに含まれる遷移の次状態に終了状態が含まれている場合、4行目の処理を行う。4行目では終了状態の集合Fにqnewを追加する。さらに、Eσに含まれる遷移の次状態が終了状態であるような遷移の重みwと次状態qnに対して次のような重みの計算を行い、ρqnewに代入する。その重みとは、wpの逆元とwとqnの終了重みρqnを×で演算した結果である。5行目では前状態がq、次状態がqnew、入力記号がσ、重みがwpであるような遷移をedetとする。6行目ではEにedetを、Qにqnewを追加する。7行目ではMに含まれる3つ組es,ed,wのうち、esがEσに含まれるような3つ組のみを集合Msに代入する。同様に、Mに含まれる3つ組es,ed,wのうち、edがEσに含まれるような3つ組のみを集合Mdに代入する。8行目ではMsに含まれる各3つ組es,ed,wのesをedetに変えた3つ組から成る集合をMに追加し、MsをMから削除する。さらに、Mdに含まれる各3つ組es,ed,wのedをedetに変えた3つ組から成る集合をMに追加し、MdをMから削除する。9行目はEσに含まれる遷移の次状態の集合に含まれる各状態qnについて10行目から13行目を処理することを表す。10行目はEσに含まれる遷移のうち、次状態がqnであるような遷移の重みをすべてで演算し、その結果をwbに代入する。11行目はqnから出て行く各遷移enについて12行目から13行目を処理することを表す。12行目では前状態がqnew、次状態がnen、入力記号がenの入力記号、重みがwpの逆元とweσとwenを×で演算した結果である遷移をenewとする。13行目ではenewを集合Eに追加する。さらに、Mに3つ組enew,en,wenewを追加する。enおよびenewを含む3つ組をMに追加することが、例えば、生成される遷移enewと遷移生成の根拠となる遷移enとを関連づける関連づけ部153の機能に相当する。14行目ではqnewを戻り値として返す。図7は、関数mergeWeightの詳細な擬似コードの一例を示す図である。Eσに含まれる遷移の前状態と次状態、入力記号はすべて同じであることを前提としている。また、Eσには1個以上の遷移が含まれているものとしている。1行目は遷移eがEσに含まれる遷移であることを示している。2行目ではEσに含まれる遷移の数が1か否かを判定しており、1なら8行目へ進み、それ以外であれば、すなわち遷移の数が2以上であれば3行目から7行目を処理することを示している。3行目ではEσに含まれる遷移の重みをすべてによって演算し、その結果をwpに代入する。4行目では遷移eの重みをwpに変更した遷移をedetに代入する。5行目では集合Mに含まれる3つ組連結元の遷移,連結先の遷移,重みのうち、連結先の遷移edがEσに含まれるような3つ組から成る集合をMdに代入する。6行目ではMdに含まれる3つ組を集合Mから削除し、Mdに含まれる3つ組の連結先の遷移をedetに変更した3つ組を集合Mに追加する。7行目では遷移の集合EからEσに含まれる遷移を削除し、その後、Eにedetを追加する。8行目はこの関数の戻り値として遷移eの次状態を返すことを示している。図8は、関数reconnectの詳細な擬似コードの一例を示す図である。1行目では状態qから出て行く遷移をEoutに代入する。2行目ではMに含まれている3つ組es,ed,wのesから成る遷移の集合にEoutに含まれている遷移がすべて含まれているか否かを判定し、すべて含まれていれば3行目から13行目を処理することを示している。そうでない場合はqと等価な状態は存在しないため、14行目へ処理を移す。3行目ではMに含まれる3つ組es,ed,wのうち、esがEoutに含まれる3つ組に関して2つ組ed,wを生成し、その集合を集合Dに代入する。4行目ではDに含まれる2つ組の1つ目の値edがMに含まれる3つ組の2つ目の値と一致する3つ組に関して、その3つ組の1つ目の値である遷移esから成る集合からEoutを取り除いた集合をEmに代入する。5行目ではEmに含まれる遷移の前状態から構成される集合をQmに代入する。6行目はQmに含まれる各状態qmについて7行目から13行目まで処理することを表している。7行目ではqmから出て行く遷移をEm’に代入する。8行目ではMに含まれている3つ組es,ed,wのesから成る遷移の集合にEm’に含まれている遷移がすべて含まれているか否かを判定し、含まれていれば9行目から13行目を処理することを示している。9行目ではMに含まれる3つ組のうち、1つ目の値esがEm’に含まれる3つ組の2つ目の値edと3つ目の値wを、それぞれ1つ目と2つ目の値とする2つ組から成る集合をDmに代入する。10行目ではDとDmが等しいか否かを判定し、さらに、qとqmに対応する終了重みが等しいか否かを判定する。両方とも等しければ状態qと状態qmとは等価な状態である。その場合、11行目から13行目までを処理する。qまたはqmがいずれも終了状態でない場合、最初に述べた終了重み関数ρの定義により同じ値が得られρq=ρqmとなる。一方が終了状態である場合、終了状態に対する終了重み関数ρで得られる値は重みの集合Kに含まれ、終了状態でない状態に対するρの値は集合Kに含まれないので、常にρq≠ρqmである。両方ともが終了状態のときは、終了重みの値に応じてρqとρqmが等しいか否かが決まる。11行目ではqへ入ってくる遷移をEinに代入する。12行目ではEinとEoutに含まれる遷移を集合Eから取り除く。また、Einに含まれる遷移の次状態をqmに変更した遷移をEに追加する。さらに状態qを状態の集合Qから取り除く。擬似コードには記載していないが、集合Mに含まれる3つ組の1番目の要素がEoutに含まれている3つ組を集合Mから取り除いても良い。すなわち、{es,ed,w∈M|es∈Eout}をMから取り除いても良い。13行目ではtrueを戻り値として返し、この関数の処理を終える。Qmに含まれるすべての状態に対して7行目から13行目を処理してもqと等価な状態が存在しなければ14行目でfalseを戻り値として返す。以上のように、決定化を行いながら不要になった状態や遷移を逐次削除することで従来より少ない記憶領域で決定化処理を実行することができる。これまでに説明した決定化処理の具体例を以下に説明する。図9は、決定化する非決定性WFSAの一例を示す図である。図9の例では重みの半環がトロピカル半環であるものとする。丸が状態、太線の丸が初期状態、二重丸が終了状態、矢印が遷移、矢印付近の文字のうち/の左側が入力記号、右側が重みである。丸の中の数字は状態の番号である。図4の1行目から処理を始める。1行目では後に使用する3つ組の集合Mを空集合で初期化する。2行目では初期状態を1つに併合するが、初期状態は1つなので何も起きない。3行目を処理すると、S={1}、Q’={1}となる。Sは空集合ではないので、5行目に進む。Sから1つ要素を取り出すと、q=1、S={}となる。6行目と7行目の処理を終えると、Eout={1,a,1,2,1,b,3,2,1,a,3,3,1,b,5,3}、Σout={a,b}となる。9行目から24行目について、まずσ=aの場合から処理を行うbから処理しても良い。9行目を処理するとEσ={1,a,1,2,1,a,3,3}となる。Eσに含まれる遷移の次状態の集合は{2,3}であるため、|nEσ|=2となり、10行目の条件を満たさない。従って15行目に進む。関数mergeTransitionsに進む。引数の値は、q=1、σ=a、Eσ={1,a,1,2,1,a,3,3}である。図6の1行目で新しい状態を生成する。これをqnew=7とする。2行目の計算は次のようになる。この例ではトロピカル半環を用いるのでは最小値minの計算になり、wp=13=min1,3=1となる。Eσの次状態の集合nEσ={2,3}とF={6}との積集合は空集合なので3行目の条件は満たさず、5行目へと進む。5行目では、edet=1,a,1,7となる。6行目ではedetとqnewをそれぞれEとQに追加する。この結果、WFSAは、図10のようになる。M=φなので7行目によりMs=φ、Md=φとなる。従って、8行目の処理後もM=φである。9行目ではまずqn=2について10行目から13行目の処理を行う。なお、qn=3の場合を先に処理してもかまわない。10行目では次状態が2であるEσに含まれる遷移は1,a,1,2のみであるので、その重み1がwbの値となる。次にpen=2であるような遷移について12行目と13行目を処理する。ここではen=2,c,1,4のみを処理すれば良い。12行目で新しい遷移enew=7,c,1,4を生成する。重みはwp-1=-1、wb=1、wen=1なので、-111=1と計算される。13行目でEにenewを追加し、Mに3つ組enew,en,1を追加する。遷移は4つ組として記録することもできるし、Eに含まれる要素への参照として記録することもできる。qn=3についても同様に10行目から13行目を処理する。10行目でwb=3となる。12行目と13行目はen=3,c,2,5について処理すれば良い。12行目で新しい遷移enew=7,c,4,5を生成する。重みはwp-1=-1、wb=3、wen=2なので、-132=4と計算される。13行目でEにenewを、Mに3つ組enew,en,4を追加する。最後に14行目でqnewを戻り値としてこの関数での処理を終了する。この時点でM={7,c,1,4,2,c,1,4,1、7,c,4,5,3,c,2,5,4}であり、WFSAは図11のようになる。点線矢印は、Mに記録している3つ組に対応する。矢印の元が3つ組の1つ目の値、矢印の先が3つ組の2つ目の値、矢印の付近の値が3つ組の3つ目の値と一致している。すなわち、点線矢印の元の遷移と点線矢印の先の遷移とが、相互に関連づけられていることを表している。図4の15行目に戻る。qnew=7となる。16行目で関数reconnectに進む。図8の1行目でEout={7,c,1,4,7,c,4,5}となる。今、Mに含まれる3つ組の1番目の値にはEoutに含まれる値がすべて含まれているので2行目の条件を満たす。3行目でD={2,c,1,4,1,3,c,2,5,4}となる。4行目でEm=φとなる。Mに含まれる3つ組の2番目の値がDに含まれる2つ組の1番目の値であるような3つ組の1番目の値の集合はEoutと等しく、Eoutとの差集合をとると空集合になるためである。Em=φであるので5行目ではQm=φとなる。これは、状態7と等価な状態である可能性がある状態が存在しないことを意味している。その結果、7行目から13行目の処理は行われない。そして14行目でfalseを戻り値としてこの関数の処理を終え、図4の16行目に戻る。16行目の結果はfalseであるので、17行目でSに状態7を追加すると、S={7}となる。今、Eσ={1,a,1,2,1,a,3,3}である。nEσ={2,3}なので、この2つの状態について19行目から23行目を処理する。まずqn=2について処理する。状態2へ入ってくる遷移は1,a,1,2と1,b,3,2が存在する。1,a,1,2はEσに含まれているが、1,b,3,2は含まれていないので、19行目の条件を満たさない。また、qn=3についても19行目の条件を満たさない。従って24行目に進み、EσをEから取り除くと、図12のようになる。8行目に戻り、σ=bで9行目から24行目までを先ほどと同じように処理する。10行目の条件は満たさないので、15行目を処理すると図13のようになる。このときqnew=8、M={7,c,1,4,2,c,1,4,1,7,c,4,5,3,c,2,5,4,8,c,1,4,2,c,1,4,1,8,c,4,5,3,c,2,5,4}である。16行目の関数reconnectを引数qnew=8で処理する。図8の1行目でEout={8,c,1,4,8,c,4,5}となるので、2行目の条件を満たす。3行目でD={2,c,1,4,1,3,c,2,5,4}となる。Dに含まれる2つ組の1番目の要素は2,c,1,4と3,c,2,5である。これらのうちいずれかを2番目の要素とするMに含まれる3つ組の1番目の要素は7,c,1,4、7,c,4,5、8,c,1,4、8,c,4,5である。ここからEoutに含まれる遷移を取り除くと、Em={7,c,1,4,7,c,4,5}となる。これが4行目の結果である。5行目でQm={7}となる。Qmの要素の数は1なので、qm=7についてのみ7行目から13行目を処理すれば良い。7行目でEm’にqmから出て行く遷移を代入し、Em’={7,c,1,4,7,c,4,5}となる。8行目の条件は満たすので、9行目以降に進む。9行目でDm={2,c,1,4,1,3,c,2,5,4}となる。DとDmは等しく、状態7、8は共に終了状態ではないので10行目の条件を満たし、11行目以降に進む。10行目の条件を満たすということは状態q=8と状態qm=7が等価であるということである。一方が不要なので、11行目と12行目で状態8と、状態8から出て行く遷移をすべて削除する。状態8へ入ってくる遷移は、そのすべてについて次状態を状態7に変更する。13行目で戻り値をtrueとして図4の16行目へ戻る。16行目の処理が完了すると、図14のようになる。trueが戻ってくるので17行目は処理されずS={7}のままである。18行目の条件を満たす状態は状態2と3である。これらの状態について19行目から23行目を処理する。まず、qn=2の場合について処理する。状態2に入ってくる遷移は1,b,3,2のみであり、これはEσ={1,b,3,2,1,b,5,3}に含まれている。従って、19行目の条件を満たすので、20行目以降の処理を行う。その処理では、状態2と関連する遷移とそれら遷移に関連する集合Mの要素を削除する。まず20行目で状態2から出て行く遷移をErに代入する。Er={2,c,1,4}となる。この時点ではM={7,c,1,4,2,c,1,4,1,7,c,4,5,3,c,2,5,4,8,c,1,4,2,c,1,4,1,8,c,4,5,3,c,2,5,4}である。図8の12行目の処理時に、そこで削除された状態8から出て行く遷移を3つ組の1番目の要素に持つ3つ組をMから取り除いていれば、M={7,c,1,4,2,c,1,4,1,7,c,4,5,3,c,2,5,4}である。前者の場合、21行目でEs={7,c,1,4,8,c,1,4}となり、後者の場合、Es={7,c,1,4}となる。図14は後者の場合を表している。Mに含まれる3つ組の1番目の要素がEsに含まれている3つ組をMから削除する。そのような3つ組は前者の場合は{7,c,1,4,2,c,1,4,1,8,c,1,4,2,c,1,4,1}である。後者の場合は7,c,1,4,2,c,1,4,1のみである。22行目ではそれらをMから削除する。23行目ではErを遷移の集合Eから取り除き、状態2も状態の集合Qから取り除く。19行目から23行目を状態3についても同様に処理すると、この場合は図8の12行目の処理がいずれであってもM={}となる。24行目でEσをEから削除すると、図15のようになる。次にS={7}なのでq=7として5行目から24行目を処理する。17行目まで処理すると、図16のようになる。S={9}、M={9,a,3,4,a,3,3,9,d,4,5,d,1,4}である。ここでは分かりやすくするため新しく作成する状態の番号を1つずつ増やしているが、削除した状態の番号を再利用することで使用する記憶領域を削減しても良い。状態4と5について19行目から23行目を処理することになり、いずれの場合も19行目の条件を満たすので、状態4と5とそれらから出て行く遷移が削除され、22行目に従ってMの要素が取り除かれる。さらに24行目でEσに含まれる遷移を削除すると、図17のようになる。次にS={9}なのでSから9を取り出し、q=9として6行目から24行目の処理を行う。Σout={a,d}であるが、それぞれの入力記号につき遷移が1本しか存在しないので、いずれの場合も10行目の条件を満たし、11行目以降を処理する。11行目ではいずれの場合でもqn=6となる。いずれか一方の処理時に13行目に進み、Sに状態6が加えられ、S={6}となる。4行目に戻るがSが空集合ではないので5行目に進み、q=6として6行目以降を処理する。状態6から出て行く遷移は存在しないので、8行目以降は処理されない。4行目に戻り、S={}であるので、最後に25行目を処理する。しかしながらすべての状態と遷移が初期状態から到達することができるので、何も起きない。以上で決定化が完了する。以上の決定化処理過程で発生する状態数の最大値は8個となり、遷移数の最大値は12本となる。従来の方法で決定化を行うと、発生する状態数の最大値は決定化前の状態数と決定化後の状態数を足した値である10個となり、同様に遷移数は13本となる。従って、本実施形態の方法によれば、処理途中で発生する状態数と遷移数が従来法よりも少なくなり、その結果、従来法よりも使用する記憶領域が少なくなる。本実施形態ではWFSAを対象として説明したが、重みの処理をなくすことでアクセプタの決定化が同様に可能である。また、重みを出力記号列であるとし、演算を前方最長一致とし、×を連結演算とすることでFSTの決定化も可能である。先に述べたように、2つ組重み、出力記号列を重みとみなせばWFSTについても決定化が同様に可能である。FSTの決定化の場合、例えば重み算出部154が、複数の第1遷移それぞれの出力記号列の最長前方一致の記号列を、第2遷移の出力記号列として算出する。また、重み算出部154が、複数の第1遷移それぞれの出力記号列の最長前方一致の記号列を、第1遷移の出力記号列の前方から取り除いた記号列を、第4遷移の出力記号列の前方に連結する。図18は、本実施形態の音声認識装置100のハードウェア構成の一例を示したブロック図である。図18に示されるように、音声認識装置100は、CPUCentralProcessingUnit1、操作部2、表示部3、ROMReadOnlyMemory4、RAMRandomAccessMemory5、記憶部6、バス7等を備えている。各部はバス7により接続されている。本装置構成における記憶領域とはROM4、RAM5、記憶部6のいずれにかかわらずFSAを記憶するために用いられる装置内の記憶領域を指す。CPU1は、RAM5の所定領域を作業領域として、ROM4または記憶部6に予め記憶された各種制御プログラムとの協働により各種処理を実行し、音声認識装置100を構成する各部の動作を統括的に制御する。またCPU1は、ROM4または記憶部6に予め記憶された所定のプログラムとの協働により後述する各機能部の機能を実現させる。操作部2は、マウスやキーボード、マイク等の入力デバイスであって、ユーザから操作入力された情報を指示信号として受け付け、その指示信号をCPU1に出力する。表示部3は、LCDLiquidCrystalDisplay等の表示装置により構成され、CPU1からの表示信号に基づいて、各種情報を表示する。ROM4は、音声認識装置100の制御にかかるプログラムや各種設定情報等を書き換え不可能に記憶する。RAM5は、SDRAM等の揮発性の記憶媒体であって、CPU1の作業エリアとして機能する。具体的には、決定化処理時に生成される各種変数やパラメータの値等を一時記憶するバッファ等の役割を果たす。記憶部6は、フラッシュメモリ等の半導体による記憶媒体や、磁気的または光学的に記録可能な記憶媒体を有し、音声認識装置100の制御にかかるプログラムや各種設定情報等を書き換え可能に記憶する。また記憶部6は、FSAに係る各種の情報を予め記憶したり、決定化処理の処理結果であるFSAを記録したりする。このように、第1の実施形態にかかるオートマトン決定化装置では、従来の方法に比べ、決定化処理の途中に保持しなければならない状態数や遷移数が少なくなるので、従来の方法より少ない記憶領域で決定化を行うことができる。第2の実施形態第1の実施形態では遷移を用いて等価な状態の判定を行うように構成した。第2の実施形態にかかるオートマトン決定化装置は、従来のサブセット構成法のように、状態を用いて等価な状態の判定を行うように構成する。状態を用いて状態の等価を判定する場合、第1の実施形態で用いた集合Mの要素である3つ組連結元の遷移、連結先の遷移、重みの1番目と2番目を変更し、連結元の状態、連結先の状態、重みのようにする。また、擬似コードを以下に述べるように書き換える。図4の21行目と22行目をそれぞれ、Qs←{qs|qs,qd,w∈M,qd=qn}、および、M←M\{qs,qd,w∈M|qs∈Qs}に変更する。図5の10行目をM←M∪{qnew,q,λqnew-1×λq}に変更する。図6の7行目と8行目を削除する。10行目と11行目の間に次の処理を追加する。Mに含まれる3つ組の1番目の要素にqnが存在するときは処理aを、そうでないときは処理bを行う。処理aでは、Mに含まれる3つ組の1番目の要素がqnであるような全ての3つ組についてM←M∪{qnew,qd,wp-1×wb×wd}を処理する。ここで、当該3つ組の2番目の要素をqd、3番目の要素をwdとしている。処理bはM←M∪{qnew,qn,wp-1×wb}である。等価な状態が一部発見できないことがあるが、処理を簡単にするために処理bだけを行うようにすることも可能である。13行目をE←E∪{enew}のみに変更する。図7の5行目と6行目を削除する。図8を図19のように変更する。1行目ではMに含まれる3つ組の1番目の要素からなる集合にqが含まれているか否かを判定し、含まれていれば2行目から9行目を処理する。2行目ではMに含まれる3つ組の1番目の要素qsがqであるような2番目の要素qdと3番目の要素wから成る2つ組の集合をDに代入する。3行目ではDに含まれる2つ組の1番目の要素qdが2番目の要素となるMに含まれる3つ組の1番目の要素をQmとする。Qmに含まれる状態はqと等価な状態の候補であり、それらの状態がqと等価であるか否かを5行目以降で判定する。4行目は5行目から9行目をQmに含まれる各状態qmについて処理することを表している。5行目ではMに含まれる3つ組の1番目の要素qsがqmであるような2番目の要素qdと3番目の要素wから成る2つ組の集合をDmに代入する。6行目でDとDmが同じであるかを判定し、同じであればqとqmが等価な状態であるので、状態qと関連する遷移を削除または変更するため、7行目から9行目を処理する。7行目ではqに入ってくる遷移をEinに、qから出て行く遷移をEoutに代入する。8行目ではEoutを集合Eから削除し、Einの次状態をqmに変更し、Qからqを削除する。等価な状態が見つかりqを削除したので戻り値をtrueとして9行目でこの関数での処理が完了する。10行目はqと等価な状態が見つからなかった場合に実行される。この場合、戻り値をfalseとしてこの関数での処理が完了する。以上で示した方法により、サブセット構成法をベースとする場合でも処理途中で発生する状態や遷移の数を従来法より少なくすることができる。すなわち、従来法よりも使用する記憶領域が少なくなる。第1の実施形態と同様に、本実施形態においても、アクセプタ、FST、および、WFSTの決定化が可能である。アクセプタの場合は重みに関する処理を取り除けば良い。FSTやWFSTの場合は第1の実施形態で述べたように重みの半環をそれぞれ対応する半環へと変更するだけである。第3の実施形態第1の実施形態で重みの処理を省くとアクセプタに対しても第1の実施形態の方法を用いることができることを述べた。第3の実施形態ではアクセプタの決定化処理の例を示す。アクセプタは状態の集合Q、遷移の集合E、入力記号の集合Σ、初期状態の集合I、および、終了状態の集合Fから成る5つ組Q,E,Σ,I,Fから構成される。遷移は3つ組前状態,入力記号,次状態で構成される。第1の実施形態で用いた集合Mの要素は3つ組であったが、ここでは2つ組連結元の遷移,連結先の遷移で構成される。第3の実施形態では、擬似コードを以下に述べるように書き換える。図4は21行目および22行目をそれぞれ、Es←{es|es,ed∈M,ed∈Er}およびM←M\{es,ed∈M|es∈Es}に変更する。図5は4行目を削除する。7行目をenew←qnew,ine,neに変更する。10行目をM←M∪{enew,e}に変更する。12行目をF←F∪{qnew}に変更する。図6は2行目と10行目を削除する。4行目および5行目をそれぞれ、F←F∪{qnew},および、edet←q,σ,qnewに変更する。7行目および8行目をそれぞれ、Ms←{es,ed∈M|es∈Eσ}、Md←{es,ed∈M|ed∈Eσ}、および、M←M∪{edet,ed|es,ed∈Ms}\Ms∪{es,edet|es,ed∈Md}\Mdに変更する。12行目および13行目をそれぞれ、enew←qnew,inen,nen、および、E←E∪{enew},M←M∪{enew,en}に変更する。図7は3行目を削除する。4行目から6行目を順に、edet←pe,ine,ne、Md←{es,ed∈M|ed∈Eσ}、および、M←M\Md∪{es,edet|es,ed∈Md}に変更する。重みに関する処理を取り除くため、図8を図20のように変更する。重み関数ρが存在しないため、10行目の重み関数を使った判定が終了状態か否かの判定に置き換わっている。状態qと状態qmがいずれも終了状態である場合、または、いずれも終了状態でない場合はq∈F=qm∈Fは真となる。一方が終了状態で他方が終了状態でない場合は偽となる。以上で示した方法により、アクセプタの場合でも処理途中で発生する状態や遷移の数を従来法より少なくすることができるので、従来法よりも使用する記憶領域が少なくできる。以上説明したとおり、第1から第3の実施形態によれば、決定化処理の途中で発生する状態や遷移の数を従来法より少なくし、使用する記憶領域を少なくすることができる。本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。"