(57)【要約】　　　（修正有）【課題】文法を表す重み付き有限状態オートマトンを生成するためのシステムおよび方法を提供する。【解決手段】文脈自由文法の規則から有限状態トランスデューサを生成し、有限状態トランスデューサから依存関係グラフを生成し、依存関係グラフの強く結び付いた構成要素に基づいてオートマトンを生成する。いくつかの状態を定義し、文脈自由文法の非終端記号のアクティブな記号をその状態間のラベルとして使用するトポロジが定義される。遷移、ならびに遷移の開始状態および終了状態を、その遷移に対するラベルとして使用される記号を状態として含むオートマトンで置き換えることにより、そのトポロジが拡張される。特定の入力ストリングを認識するのに必要とされるのに応じて、そのトポロジを十分に拡張することができる。【選択図】図３１
2004004521.tif 000002
【特許請求の範囲】
【請求項１】
文法の１組の規則から有限状態オートマトンを生成するシステムであって、
前記１組の規則から第１の有限状態トランスデューサを生成する第１の有限状態オートマトンを生成する回路、ルーチン、またはアプリケーションと、
前記第１の有限状態トランスデューサから依存関係グラフを生成する依存関係グラフを生成する回路、ルーチン、またはアプリケーションと、
前記依存関係グラフの強く結び付いた構成要素を識別する強く結び付いた構成要素を識別する回路、ルーチン、またはアプリケーションと、
前記依存関係グラフの前記少なくとも１つの識別された強く結び付いた構成要素に基づいて少なくとも１つの有限状態オートマトンを生成する第２の有限状態オートマトンを生成する回路、ルーチン、またはアプリケーションとを含むシステム。
【請求項２】
前記少なくとも１つの第２の有限状態オートマトンに基づき、定義されたトポロジに対応する第３の有限状態オートマトンを拡張する有限状態オートマトンを拡張する回路、ルーチン、またはアプリケーションをさらに含む請求項１に記載の文法の１組の規則から有限状態オートマトンを生成するシステム。
【請求項３】
前記有限状態オートマトンを拡張する回路、ルーチン、またはアプリケーションが、前記文法の記号の入力シーケンスに基づいて前記第３の有限状態オートマトンを動的に拡張する請求項１に記載の文法の１組の規則から有限状態オートマトンを生成するシステム。
【請求項４】
前記第１の有限状態オートマトンを最小化する有限状態オートマトンを最小化する回路、ルーチン、またはアプリケーションをさらに含み、前記第１の有限状態オートマトンが、前記依存関係グラフを生成する回路、ルーチン、またはアプリケーションが、前記第１の有限状態オートマトンから前記依存関係グラフを生成する前に最小化される請求項１に記載の文法の１組の規則から有限状態オートマトンを生成するシステム。
【請求項５】
前記第１の有限状態オートマトンを少なくとも局所的に決定する有限状態オートマトンを決定する回路、ルーチン、またはアプリケーションをさらに含み、前記第１の有限状態オートマトンが、前記依存関係グラフを生成する回路、ルーチン、またはアプリケーションが、前記第１の有限状態オートマトンから前記依存関係グラフを生成する前に少なくとも局所的に決定される請求項１に記載の文法の１組の規則から有限状態オートマトンを生成するシステム。
【請求項６】
非終端記号および終端記号を有し、かつ１組の規則を有する文脈自由文法を前記文脈自由文法を表す有限状態オートマトンに変換するための方法であって、
前記１組の規則から第１の有限状態オートマトンを生成するステップ、および前記第１の有限状態オートマトンから、前記文脈自由文法の複数の前記非終端記号に関する遅延アクセプタをそれぞれが定義する少なくとも１つの第２の有限状態オートマトンを生成するステップを含む方法。
【請求項７】
前記文脈自由文法のアプリケーションを定義するトポロジを受け取ること、
前記受け取られたトポロジを表す第３の有限状態オートマトンを生成すること、および
前記少なくとも１つの生成された第２の有限状態オートマトンの少なくとも１つに基づいて前記第３の有限状態オートマトンを拡張することをさらに含む請求項６に記載の方法。
【請求項８】
前記受け取られたトポロジが、前記文脈自由文法が、前記文法の記号の入力ストリングに適用される少なくとも１つの条件を定義する請求項７に記載の方法。
【請求項９】
前記入力トポロジが、前記文脈自由文法に課せられた少なくとも１つの制約を識別する請求項７に記載の方法。
【請求項１０】
前記第３の有限状態オートマトンを生成することが、
前記トポロジに基づいて少なくとも１つの初期状態を定義すること、
前記トポロジに基づいて少なくとも１つの最終状態を定義すること、および
前記トポロジに基づき、前記アクティブな非終端記号を表し、前記アクティブな非終端記号のどれかでそれぞれにラベルが付けられ、前記第３の有限状態オートマトンの初期状態および最終状態の少なくともどちらかからそれぞれが延びる複数のエッジを定義することを含む請求項７に記載の方法。
【請求項１１】
前記少なくとも１つの生成された第２の有限状態オートマトンの少なくとも１つに基づいて前記第３の有限状態オートマトンを拡張することが、前記第３の有限状態オートマトンの前記複数のエッジのそれぞれに関して、前記エッジにラベルとして付けられた前記非終端記号に基づき、前記少なくとも１つの第２の有限状態オートマトンの１つで前記エッジを置き換えることを含む請求項１０に記載の方法。
【請求項１２】
前記少なくとも１つの生成された第２の有限状態オートマトンの少なくとも１つに基づいて前記第３の有限状態オートマトンを拡張することが、前記文法の非終端記号でラベルが付けられた前記拡張された第３の有限状態オートマトンの各エッジに関して前記置き換えるステップを繰り返すことをさらに含む請求項１１に記載の方法。
【請求項１３】
前記複数のエッジの１つを前記エッジにラベルとして付けられた前記非終端記号に基づいて前記少なくとも１つの第２の有限状態オートマトンの前記１つで置き換えることが、
前記第２の有限状態オートマトンを変更して、前記エッジにラベルとして付けられた前記非終端記号を受け入れる新しいオートマトンにすること、および
前記エッジを前記新しいオートマトンで置き換えることを含む請求項１１に記載の方法。
【請求項１４】
前記少なくとも１つの生成された第２の有限状態オートマトンの少なくとも１つに基づいて前記第３の有限状態オートマトンを拡張することが、前記第３の有限状態オートマトンによって認識されるべき前記文脈自由文法の複数の記号を含む入力ストリングに基づいて前記第３の有限状態オートマトンを動的に拡張することを含む請求項１０に記載の方法。
【請求項１５】
前記少なくとも１つの生成された第２の有限状態オートマトンの少なくとも１つに基づいて前記第３の有限状態オートマトンを拡張することが、
前記第３の有限状態オートマトンのエッジを選択し、前記選択されたエッジに、前記文脈自由文法の前記非終端記号の１つでラベルが付けられていること、
前記選択されたエッジにラベルとして付けられた前記非終端記号に対応する前記少なくとも１つの第２の有限状態オートマトンの１つを選択すること、
前記選択されたエッジを前記選択された第２の有限状態オートマトンで置き換えること、および
前記文法の前記非終端記号の１つでラベルが付けられたエッジが、前記第３の有限状態オートマトンにおいて全く残っていないようになるまで、前記選択するステップおよび前記置き換えるステップを繰り返すことを含む請求項１０に記載の方法。
【請求項１６】
前記少なくとも１つの第２の有限状態オートマトンを生成することが、
前記第１の有限状態オートマトンから依存関係グラフを生成すること、
前記依存関係グラフに基づいて前記文法の少なくとも１つの強く結び付いた構成要素を識別すること、および
前記少なくとも１つの識別された強く結び付いた構成要素のそれぞれから、前記少なくとも１つの第２の有限状態オートマトンの１つを生成することを含む請求項６に記載の方法。
【請求項１７】
前記第１の有限状態オートマトンから前記依存関係グラフを生成することが、
前記文脈自由文法の前記入力規則の各非終端記号に関して依存関係グラフ状態を生成すること、
前記第１の有限状態オートマトンの前記状態の１つを選択すること、
前記選択された状態から延びる少なくとも１つのエッジの１つを第１の選択されたエッジとして選択し、前記第１の選択されたエッジに前記非終端記号の１つでラベルが付けられており、前記第１の選択されたエッジが、前記エッジが延びる先の第１の終了状態を有していること、
前記第１の終了状態から延びる少なくとも１つのエッジの１つを第２の選択されたエッジとして選択し、前記第２の選択されたエッジに前記非終端記号の１つでラベルが付けられており、前記第２の選択されたエッジが、前記エッジが延びる先の第２の終了状態を有していること、
前記第２の選択されたエッジに非終端記号でラベルが付けられているかどうかを判定すること、および
前記第２の選択されたエッジに非終端記号でラベルが付けられている場合、前記第１の選択されたエッジにラベルとして付けられている前記非終端記号に関する依存関係グラフ状態から、前記第２の選択されたエッジにラベルとして付けられている前記非終端記号に関する依存関係グラフ状態まで延びる前記依存関係グラフにおけるエッジを生成することを含む請求項１６に記載の方法。
【請求項１８】
前記第１の有限状態オートマトンから前記依存関係グラフを生成することが、
前記第２の終了状態が、前記第１の有限状態トランスデューサの最終状態であるかどうかを判定すること、および
前記第２の終了状態が、前記第１の有限状態トランスデューサの最終状態ではない場合、
前記第１の終了状態を前記選択された状態として選択すること、
前記第２の選択されたエッジを前記第１の選択されたエッジとして選択すること、および
前記第２のエッジを選択するステップ、前記第２の選択されたエッジの記号を判定するステップ、および前記依存関係グラフのエッジを生成するステップを繰り返すことをさらに含む請求項１７に記載の方法。
【請求項１９】
前記依存関係グラフに基づいて前記文法の少なくとも１つの強く結び付いた構成要素を識別することが、
前記依存関係グラフの非終端状態を現行の強く結び付いた構成要素に関する初期状態として選択すること、
前記初期状態から延びるエッジを第１のエッジとして選択し、前記第１のエッジが、第１の終了状態まで延びていること、
前記第１の終了状態を現行の状態およびパス状態として選択すること、
前記第１の終了状態から延びるエッジを第２のエッジとして選択し、前記第２のエッジが、第２の終了状態まで延びていること、
前記第２の終了状態が、前記初期状態であるか、または前記現行の強く結び付いた構成要素の状態として前に識別されているかどうかを判定すること、および前記第２の終了状態が、前記初期状態であるか、または前記現行の強く結び付いた構成要素の状態として前に識別されている場合、前記初期状態およびあらゆるパス状態に関連する前記非終端記号を前記現行の強く結び付いた構成要素の非終端記号として識別することを含む請求項１６に記載の方法。
【請求項２０】
前記少なくとも１つの第２の有限状態オートマトンの１つを生成することが、
前記少なくとも１つの強く結び付いた構成要素の１つを現行の強く結び付いた構成要素として選択すること、
前記選択された強く結び付いた構成要素に対応する現行の第２の有限状態オートマトンに関して、前記現行の強く結び付いた構成要素の各非終端記号に関する状態を生成すること、
前記第１の有限状態オートマトンの初期状態から延び、前記現行の強く結び付いた構成要素の前記非終端記号の１つでラベルが付けられた前記第１の有限状態トランスデューサから延びるエッジを第１のエッジとして選択し、前記第１のエッジが、第１の終了状態を有していること、
前記第１の終了状態を前記現行の状態として選択すること、
前記現行の状態から延びるエッジを第２のエッジとして選択し、前記第２のエッジが、第２の終了状態を有していること、
前記第２のエッジをパス・エッジとして識別すること、
前記第２の終了状態が、前記第１の有限状態オートマトンの最終状態であるかどうかを判定すること、および
前記第２の終了状態が、前記第１の有限状態オートマトンの終了状態ではない場合、
前記第２のエッジを前記現行のエッジとして選択し、また前記第２の終了状態を前記現行の状態として選択すること、および
前記第２のエッジを選択するステップ、前記識別するステップ、および前記判定するステップを繰り返すことを含む請求項１６に記載の方法。
【請求項２１】
前記少なくとも１つの制約が、前記文脈自由文法が前記文法の記号の入力ストリングに適用される前記文法に課せられた少なくとも１つの初期条件を定義する請求項９に記載の方法。
【請求項２２】
前記第３の有限状態オートマトンによって認識されるべき入力ストリングに基づいて前記第３の有限状態オートマトンを動的に拡張することが、
前記入力ストリングを入力すること、
前記入力ストリングの記号を選択すること、
前記選択された記号に基づき、前記第３の有限状態オートマトンを拡張することが望ましいかどうかを判定すること、および
前記第３の有限状態オートマトンを拡張することが望ましい場合、前記選択された記号でラベルが付けられた前記第３の有限状態オートマトンのエッジを、前記選択された記号を含む前記少なくとも１つの第２の有限状態オートマトンの１つで置き換えることを含む請求項１４に記載の方法。
【請求項２３】
前記少なくとも１つの第２の有限状態オートマトンの１つを生成することが、
何らかの識別されたパス・エッジが前記現行の強く結び付いた構成要素の非終端記号である出力記号を有するかどうかを判定すること、
何らかの識別されたパス・エッジが、前記現行の強く結び付いた構成要素の非終端記号である出力記号を有する場合、前記現行の強く結び付いた構成要素において右リニア・パスが存在するかどうかを判定すること、および
前記現行の強く結び付いた構成要素において右リニア・パスが全く存在しない場合、前記現行の第２の有限状態オートマトンにおいて、前記第１のエッジの入力記号に対応する前記現行の第２の有限状態オートマトンの非最終状態から、前記現行の第２の有限状態オートマトンの最終状態までのパスを生成することをさらに含む請求項２０に記載の方法。
【請求項２４】
前記少なくとも１つの第２の有限状態オートマトンの１つを生成することが、
何らかの識別されたパス・エッジが、前記現行の強く結び付いた構成要素の非終端記号である出力記号を有するかどうかを判定すること、
何らかの識別されたパス・エッジが、前記現行の強く結び付いた構成要素の非終端記号である出力記号を有する場合、前記現行の強く結び付いた構成要素において右リニア・パスが存在するかどうかを判定すること、および
前記現行の強く結び付いた構成要素において右リニア・パスが存在する場合、前記現行の第２の有限状態オートマトンにおいて、前記現行の第２の有限状態オートマトンの初期状態から、前記第１のエッジの入力記号に対応する前記現行の第２の有限状態オートマトンの非最終状態までのパスを生成することをさらに含む請求項２０に記載の方法。
【請求項２５】
前記少なくとも１つの第２の有限状態オートマトンの１つを生成することが、
前記現行の強く結び付いた構成要素の非終端記号である出力記号を有する識別されたパス・エッジが存在しない場合、または何らかの識別されたパス・エッジが、前記現行の強く結び付いた構成要素の非終端記号である出力記号を有し、かつ前記現行の強く結び付いた構成要素において右リニア・パスが存在する場合、複数のパス・エッジが、前記現行の強く結び付いた構成要素の非終端記号である出力記号を有するかどうかを判定すること、および
複数のパス・エッジが、前記現行の強く結び付いた構成要素の非終端記号である出力記号を有する場合、前記文法が適格ではないと判定することをさらに含む請求項２４に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、文法を表すのに使用される重み付き有限状態オートマトンを構成するためのシステムおよび方法を対象とする。
【０００２】
【従来の技術】
言語学、音声認識、および音声合成（テキストを音声に変換する）などの様々な技術分野で、文脈自由文法および文脈依存文法を使用して１組の記号の別の１組の記号への変換を表している。例えば、文脈依存言語書換え規則では、言語の要素が現れる文脈に基づいてどのようにその要素を組み合わせることができるかを文法が定義する。同様に、文脈自由文法を使用して音響信号を認識される音声に変換することができる。
【０００３】
文法は、一般に、多数の規則を含み、各規則が、異なる一続きの記号からどのように所与のストリングの記号を生成することができるかを定義する。多くのコンピュータ実施態様では、そのような文法は、有限状態オートマトンを使用して表現または実装される。文法が重み付き文法である場合、その重み付き文法は、有限状態トランスデューサとして表現される。有限状態オートマトンまたは有限状態トランスデューサを使用して文法を表すことは、有限状態オートマトンまたは有限状態トランスデューサを圧縮すること、決定すること、および最小化することによって有限状態オートマトンまたは有限状態トランスデューサを最適化することができるので、しばしば、極めて重要である。
【０００４】
所与の文脈自由文法から有限状態オートマトンまたは有限状態トランスデューサを生成することは、特に、音声認識システムまたは音声合成システムを実施するのに必要な文法規則の数が大きいことから、取るに足らない作業ではない。文脈依存文法の規則から有限状態オートマトンまたは有限状態トランスデューサを生成するための一般的な技法は、例えば、米国特許第５８０６０３２号で説明されているが、文脈自由文法の規則を表す有限状態トランスデューサから有限状態オートマトンまたは有限状態トランスデューサを生成するためのそのような一般的な技法は存在しない。
【０００５】
【発明が解決しようとする課題】
本発明は、文脈自由文法から、文脈自由文法を表す有限状態オートマトンまたは有限状態トランスデューサを生成するシステムおよび方法を提供する。
【０００６】
さらに、本発明は、重み付き文脈自由文法から、その文脈自由文法を表す重み付き有限状態トランスデューサを生成するシステムおよび方法を提供する。
【０００７】
別途に、本発明は、文脈自由文法を表す有限状態オートマトンまたは有限状態トランスデューサから、その文脈自由文法によって記述されるストリングを認識する遅延アクセプタを生成するシステムおよび方法を提供する。
【０００８】
さらに、本発明は、文脈自由文法を表す重み付き有限状態トランスデューサから、その文脈自由文法によって記述されるストリングを認識する遅延重み付きアクセプタを生成するシステムおよび方法を提供する。
【０００９】
別途に、本発明は、文脈自由文法を表す有限状態オートマトンまたは有限状態トランスデューサをコンパイルして、その文脈自由文法によって記述されるストリングを認識する遅延アクセプタにするシステムおよび方法を提供する。
【００１０】
さらに、本発明は、文脈自由文法を表す重み付き有限状態トランスデューサをコンパイルして、その文脈自由文法によって記述されるストリングを認識する遅延重み付きアクセプタにするシステムおよび方法を提供する。
【００１１】
別途に、本発明は、再コンパイルを必要とすることなく遅延アクセプタを動的に定義し、かつ／または変更できるようにするシステムおよび方法を提供する。
【００１２】
別途に、本発明は、遅延重み付きアクセプタを使用して入力ストリングを認識する際にその遅延重み付きアクセプタを動的に拡張できるようにするシステムおよび方法を提供する。
【００１３】
別途に、本発明は、文脈自由文法の規則から依存関係グラフを生成するシステムおよび方法を提供する。
【００１４】
別途に、本発明は、文脈自由文法を表す依存関係グラフの強く結び付いた構成要素を判定するシステムおよび方法を提供する。
【００１５】
別途に、本発明は、文脈自由文法を表す依存関係グラフの識別された強く結び付いた構成要素からオートマトンを構成するシステムおよび方法を提供する。
【００１６】
別途に、本発明は、文脈自由文法の１組のアクティブな非終端記号を受け入れる単純なオートマトンを可能にし、その単純なオートマトンの遷移を、文脈自由文法を表す依存関係グラフの識別された強く結び付いた構成要素から構成された対応するオートマトンで置き換えるシステムおよび方法を提供する。
【００１７】
さらに、本発明は、単純なオートマトンの選択された遷移を、文法の入力記号に基づき、文脈自由文法を表す依存関係グラフの識別された強く結び付いた構成要素から構成されたオートマトンのうちの対応するオートマトンで動的に置き換えるシステムおよび方法を提供する。
【００１８】
【課題を解決するための手段】
様々な例としての実施形態では、本発明によるシステムおよび方法が、文脈自由文法の規則を入力する。様々な例としての実施形態では、規則は、各規則に関して、左側の非終端記号、右側の非終端記号、および終端記号、ならびに文脈自由文法に重み付けが行われている場合、その規則の重みを指定する特定の形式を使用して入力される。次に、入力された規則から依存関係グラフが生成され、その依存関係グラフの強く結び付いた構成要素が識別される。識別された強く結び付いた構成要素に基づき、それぞれ強く結び付いた構成要素に関してオートマトンが生成される。
【００１９】
様々な例としての実施形態では、いくつかの状態を定義し、文脈自由文法の非終端記号のうち１組のアクティブな記号をオートマトンまたはトポロジの状態間のラベルとして使用するオートマトンまたはトポロジが定義される。定義されたオートマトンまたはトポロジが十分に拡張される様々な例としての実施形態では、各遷移、および各遷移の開始状態および終了状態が、その遷移に対するラベルとして使用される記号を表すオートマトンで置き換えられる。オートマトンまたはトポロジの元の遷移のすべてが置き換えられた後、拡張されたオートマトンまたはトポロジの遷移のどれかに、文法の非終端記号でラベルが付けられている場合、それぞれのそのような遷移、およびその遷移の開始状態および終了状態は、その遷移に対するラベルとして使用される記号を表すオートマトンで置き換えられる。拡張されたオートマトンまたはトポロジにおいて文脈自由文法の非終端記号でラベルが付けられた遷移が全くなくなるまで、これが続けられる。
【００２０】
定義されたオートマトンまたはトポロジが動的に、すなわち、オンザフライで拡張される他の様々な例としての実施形態では、文脈自由文法の終端記号が入力される。ストリングの各記号が順に選択される。選択された記号により、動的に拡張されたオートマトンまたはトポロジの現行のアクティブな状態を所与として、文脈自由文法の非終端記号でラベルが付けられた遷移をトラバースすることが必要とされる場合、その遷移、およびその遷移の開始状態および終了状態が、その遷移に対するラベルとして使用される記号を表すオートマトンで置き換えられる。入力ストリングの最後の記号が選択されるまで、これが続けられる。
【００２１】
様々な例としての実施形態では、定義されたオートマトンまたはトポロジは、文脈自由文法の識別された強く結び付いた構成要素に関して生成されたオートマトンを全く再判定する必要なしに、任意の時点で変更することができる。したがって、定義されたオートマトンまたはトポロジは、文法の記号の所与の入力ストリングが認識されるにつれ、動的に変更することができる。
【００２２】
本発明の以上の特徴および利点ならびにその他の特徴および利点については、本発明によるシステムおよび方法の様々な例としての実施形態の以下の詳細な説明で述べ、その説明から明白となる。
【００２３】
本発明のシステムおよび方法の様々な例としての実施形態を添付の図面を参照して詳細に説明する。
【００２４】
【発明の実施の形態】
本発明によるシステムおよび方法は、入力された、または受け取られた文脈自由文法から有限状態オートマトンを生成する。本発明では、文法とは、音声をテキストに変換する、または第１の言語のテキストを第２の言語のテキストに変換するなどの、データの入力ストリングをデータの出力ストリングに変換するための１組の規則である。図１は、文法Ｇの一例を示している。文法Ｇは、文脈自由である。また、文法Ｇは、重み付けされていない文法に対比される重み付き文法である。重み付き文法は、各規則に割り当てられたコストを有する文法である。これにより、その文法を実装するシステムが、同一の入力に対する相異なる出力を伴う複数の規則を有することが可能になる。各出力には、異なる重みが割り当てられ、後の規則が、出力判定が行われる前にその重みを変更することができる。
【００２５】
本発明では、文法における記号には、特定の定義が割り当てられる。規則の右側でだけ現れる記号は、「終端」記号と呼ばれ、図１で示す文法Ｇにおいて小文字記号を使用して表現されている。規則の左側で現れることが排他的に許され、規則の右側で現れる可能性がある文法におけるその他の記号は、「非終端」記号と呼ばれる。規則においてすべての終端記号が生じた後、その規則の右側で単一の非終端記号が生じた場合、その規則は、「右リニア」である。一方、すべての終端記号の前に生じる出力における単一の非終端記号を伴う規則は、「左リニア」である。規則の右側に終端記号だけ、または非終端記号だけを有する規則は、右リニアか、または左リニアである。以上のケースのどれも生じない場合、規則は、右リニアでも左リニアでもない。
【００２６】
文法におけるサブセットの規則は、そのサブセットの中の非終端記号が、そのサブセットの１つまたは複数の規則の左側、およびそのサブセットの１つまたは複数の他の規則の右側に出現して、それらの規則が、その文法の規則の相互依存するサブセットを形成する場合、「強く結び付いた構成要素」を形成する。例えば、図１で示した文法Ｇにおいて、第４の行で、Ｘが規則の左側に現れ、一方、Ｙが規則の右側に現れる。一方、第５の行では、Ｙが規則の左側に現れ、一方、Ｘが規則の右側に現れる。したがって、ＸおよびＹは、規則４および５を含む文法Ｇのサブセットに対応する強く結び付いた構成要素のメンバである。
【００２７】
図２は、本発明によるシステムおよび方法の様々な例としての実施形態で使用可能である文法Ｇの入力形式の一例としての実施形態を示している。図２では、図１で示した文法Ｇにおける各規則に関して、文法Ｇに関する入力形式において１行が存在する。文法Ｇの規則の入力形式の第１の列１２１０の中の値は、入力文法における記号の固有表現である。この入力形式では、入力文法Ｇにおける各記号に、番号が割り当てられる。例えば、図２で示した入力形式の例としての実施形態では、非終端記号「Ｔ」、「Ｘ」、「Ｙ」、および「Ｚ」にそれぞれ、番号１〜４が割り当てられている。その他の非終端記号および終端記号にも、同様に参照番号が割り当てられている。第２の列１２２０は、入力文法に重み付けが行われている場合、コスト値を表す。重み付けの行われない文法の場合、第２の列１２２０は省略されることを理解されたい。
【００２８】
有限状態オートマトンは、試験処理、音声処理および音声認識、イメージ処理などの様々な大規模の適用例で使用される通常の計算デバイスである。テキスト、音声、およびイメージの処理および認識におけるいくつかの適用例は、データの変動を考慮に入れ、処理中または認識プロセス中に生成された様々な仮説にランク付けを行うのに、より一般的なデバイスである重み付き有限状態オートマトンを必要とする。重み付き有限状態オートマトンは、２つの状態間の各遷移または各エッジに通常の入力記号に加えて何らかの重みでラベルが付けられた有限状態オートマトンである。有限状態トランスデューサは、遷移またはエッジが出力ラベルをさらに備える有限状態オートマトンである。
【００２９】
図３は、文法Ｇを表す有限状態トランスデューサＴＧの一例としての実施形態を示している。初期状態０から有限状態トランスデューサＴＧの最終状態１２までの有限状態トランスデューサＴＧにおける各パスが、図１で示した文法Ｇの規則の１つを表している。つまり、文法Ｇにおける各規則に対して有限状態トランスデューサＴＧにおいてパスが存在する。文法Ｇの所与の規則上で現れる各記号に関して、その特定の規則を表す有限状態トランスデューサＴＧを通るパスにおける対応するエッジが存在する。各エッジに関して、有限状態トランスデューサＴＧにおけるそのエッジに、文法Ｇ規則からの記号、またはその記号が表す規則でラベルが付けられる。所与の規則に関して、その規則に対応するパスにおけるそれぞれラベル付きのエッジが、その規則で記号が現れるのと同じシーケンスで出現する。
【００３０】
図４は、最小化された後の図３で示した有限状態トランスデューサＴＧ′を示している。図３で示した元の有限状態トランスデューサＴＧから、図４で示した最小化された有限状態トランスデューサＴＧ′を形成する際、同様の入力記号または出力記号を有するエッジを組み合わせて、元の有限状態トランスデューサＴＧにおける冗長性を縮減する。詳細には、図４で示した最小化された有限状態トランスデューサＴＧ′を生成する際、図３で示した元の有限状態トランスデューサＴＧの状態１および２がそれぞれ、同じ記号でラベルが付けられ、同じ初期状態から延びるエッジを有する。この結果、図３で示した元の有限状態トランスデューサＴＧのこれらの状態が結合されて、図４で示した最小化された有限状態トランスデューサＴＧ′におけるように、その記号でラベルが付けられ、状態１で終了するエッジを有する単一の状態１にされる。
【００３１】
図３で示した元の有限状態トランスデューサＴＧの状態７、９、および１１はそれぞれ、同じ記号を有し、同じ終了状態で終了するエッジを有する。この結果、図３で示した元の有限状態トランスデューサＴＧの状態７、９、および１１が結合されて、同じ記号でラベルが付けられ、その終了状態まで延びるエッジを有する図４で示した最小化された有限状態トランスデューサＴＧ′の状態６が形成される。
【００３２】
本発明による依存関係グラフは、文法における規則の左側にある非終端記号のその規則の右側における非終端記号に対する依存関係を表す有限状態マシンである。依存関係グラフは、それぞれ特定の入力された非終端記号の出力される非終端記号に対する関係に関するエッジを有する。図５は、文法Ｇを表す依存関係グラフの一例としての実施形態を示している。図５で示した依存関係グラフは、文法Ｇにおける各非終端記号に関する状態を有する。また、図５で示した依存関係グラフは、非終端記号を表す状態で終了し、規則の左側で非終端記号を表す状態で開始する規則の右側に現れる各非終端記号に関するエッジも有する。例えば、図１で示した文法Ｇにおける第１の規則は、Ｔという入力の非終端記号を有し、また出力において非終端記号ＺおよびＹを有する。この結果、図５で示す状態Ｔから状態Ｚまでのエッジ、および状態Ｔから状態Ｙまでのエッジが、依存関係グラフの中に存在する。
【００３３】
図６および７は、文法Ｇの強く結び付いた構成要素Ｓ｛Ｔ，Ｚ｝およびＳ｛Ｘ，Ｙ｝の１つをそれぞれ表す有限状態オートマトンＫ（Ｓ）の例としての実施形態を示している。図６および７で示す有限状態オートマトンＫ（Ｓ）は、図４で示した最小化された有限状態トランスデューサＴＧ′のサブセクションである。図６および７で示す有限状態オートマトンＫ（Ｓ）は、対応する強く結び付いた構成要素Ｓ｛Ｘ，Ｙ｝またはＳ｛Ｔ，Ｚ｝の相互依存関係を定義する最小化された有限状態トランスデューサＴＧ′のパスを含む。図６および７で示した有限状態オートマトンＫ（Ｓ）のそれぞれは、対応する強く結び付いた構成要素における各非終端記号に関する状態を有する。図４で示した最小化された有限状態トランスデューサＴＧ′からのパスが、図６および７で示した有限状態オートマトンに組み込まれる。各終端記号、および強く結び付いた構成要素のメンバではない各非終端記号に関して、その強く結び付いた構成要素に関する有限状態オートマトンにエッジが追加される。また、その強く結び付いた構成要素において現れない文法のどの非終端記号も、その強く結び付いた構成要素との関係で終端記号として扱われることを理解されたい。
【００３４】
本発明によれば、トポロジは、入力文法を適用しようとするユーザに課される特定の１組の条件を定義する。トポロジは、文法が適用される際に開始点として必要とされる可能性がある文法規則に対する特定の制約を明らかにする。図８は、文法Ｇを適用する際に使用されるユーザによって入力されたトポロジを表す単純な有限状態オートマトンの一例としての実施形態を示している。図８で示した単純な有限状態オートマトンは、初期状態、最終状態、およびアクティブな非終端記号、つまり適用される文法の第１の規則を表すエッジを有する。
【００３５】
図９は、強く結び付いた構成要素Ｓ｛Ｘ，Ｙ｝に対応する図７で示した有限状態オートマトンＫ（Ｓ）の変更された形態Ｍ（Ｙ）の第１の例としての実施形態を示している。入力トポロジを表す図８で示した単純な有限状態オートマトンを文法Ｇを適用するのに使用する拡張されたオートマトンに拡張する際、図９で示した有限状態オートマトンＭ（Ｙ）を使用して、記号Ｙでラベルが付けられたエッジ、ならびにそのエッジの開始状態および終了状態を置き換える。強く結び付いた構成要素Ｓ｛Ｘ，Ｙ｝は、右リニアであるので、図７で示した対応する有限状態オートマトンＫ（Ｓ）は、既に最終状態を有している。次に、図７で示した有限状態オートマトンＫ（Ｓ）が、Ｙでラベルを付けられた状態を初期状態に変えることによって変更される。したがって、この時点で、図９で示した有限状態オートマトンＭ（Ｙ）が、初期状態および最終状態を有する。したがって、図９で示した有限状態オートマトンＭ（Ｙ）を、非終端Ｙでラベルが付けられたエッジ、ならびにそのエッジの開始状態および終了状態の代わりに使用することができる。
【００３６】
図１０は、図７で示した強く結び付いた構成要素Ｓ｛Ｘ，Ｙ｝に対応する有限状態オートマトンＫ（Ｓ）の変更された形態Ｍ（Ｙ）′の第２の例としての実施形態を示している。図１０で示した有限状態オートマトンＭ（Ｙ）′の目的も、図８で示した単純な有限状態オートマトンを拡張する際、記号Ｙでラベルが付けられたエッジを置き換えることである。強く結び付いた構成要素Ｓ｛Ｘ，Ｙ｝は、右リニアであるので、図７で示した対応する有限状態オートマトンＫ（Ｓ）は、既に最終状態を有している。次に、図７で示した有限状態オートマトンＫ（Ｓ）が、Ｙでラベルが付けられた状態から開始するエッジと同一のエッジを有する新しい初期状態を生成し、その新しい初期状態で終了するエッジが全く存在しないようにすることにより、変更される。したがって、この時点で、図１０で示した有限状態オートマトンＭ（Ｙ）′は、初期状態を有し、その初期状態から延びるエッジに関連するコストは、図７で示した有限状態オートマトンＫ（Ｓ）における元のエッジに関連するコストを変えることなしに変更することができる。したがって、図１０で示した有限状態オートマトンＭ（Ｙ）′は、非終端記号Ｙでラベルが付けられたエッジ、ならびにそのエッジの開始状態および終了状態の代わりに使用することができ、同じコストが前のエッジと挿入された有限状態オートマトンの両方に関連している。
【００３７】
図１１は、強く結び付いた構成要素Ｓ｛Ｘ，Ｙ｝に対応する図７で示した有限状態オートマトンＫ（Ｓ）の変更された形態Ｍ（Ｘ）の第１の例としての実施形態を示している。図１１で示した有限状態オートマトンＭ（Ｘ）も同様に、図８で示した単純な有限状態オートマトンを拡張する際、非終端記号Ｘでラベルが付けられたエッジの代わりに使用することができる。強く結び付いた構成要素Ｓ｛Ｘ，Ｙ｝は、右リニアであるので、図７で示した有限状態オートマトンＫ（Ｓ）は、既に最終状態を有している。次に、図７で示した有限状態オートマトンＫ（Ｓ）は、Ｘでラベルが付けられた状態から開始するエッジと同一のエッジを有する新しい初期状態を生成し、その新しい初期状態で終了するエッジが全く存在しないようにすることにより、変更される。したがって、この時点で、図１１で示した有限状態オートマトンＭ（Ｘ）は、初期状態を有し、その初期状態から延びるエッジに関連するコストは、図７で示した有限状態オートマトンＫ（Ｓ）における元のエッジに関連するコストを変えることなしに変更することができる。したがって、図１１で示した有限状態オートマトンＭ（Ｘ）は、非終端記号Ｘでラベルが付けられたエッジ、ならびにそのエッジの開始状態および終了状態の代わりに使用することができ、同じコストが前のエッジと挿入された有限状態オートマトンの両方に関連している。
【００３８】
図１２は、強く結び付いた構成要素Ｓ｛Ｔ，Ｚ｝に対応する図６で示した有限状態オートマトンＫ（Ｓ）の変更された形態Ｍ（Ｔ）の第１の例としての実施形態を示している。図１２で示した有限状態オートマトンＭ（Ｔ）も同様に、図８で示した単純な有限状態オートマトンを拡張する際、非終端記号Ｔでラベルが付けられたエッジの代わりに使用することができる。強く結び付いた構成要素Ｓ｛Ｔ，Ｚ｝は、左リニアであるので、図６で示した有限状態オートマトンＫ（Ｓ）は、既に初期状態を有している。次に、図６で示した有限状態オートマトンＫ（Ｓ）は、Ｔでラベルが付けられた状態を最終状態に変えることによって変更される。したがって、この時点で、図１２で示した有限状態オートマトンＭ（Ｔ）は、初期状態および最終状態を有する。したがって、図１２で示した有限状態オートマトンＭ（Ｔ）は、非終端記号Ｔでラベルが付けられたエッジ、ならびにそのエッジの開始状態および終了状態の代わりに使用することができる。
【００３９】
図１３は、図８で示した単純な有限状態オートマトンから拡張された有限状態オートマトンの一例としての実施形態を示している。図８で示した単純な有限状態オートマトンは、強く結び付いた構成要素Ｓ｛Ｘ，Ｙ｝に関連する文法Ｇの規則が適用されるとき、そのように拡張される。この理由は、置き換えられるエッジに非終端記号Ｘでラベルが付けられているからである。この拡張は、非終端記号Ｘでラベルが付けられたエッジを図１１で示した有限状態オートマトンＭ（Ｘ）で置き換えることによって行われる。非終端記号Ｘでラベルが付けられたエッジが延びる始まりの状態が、有限状態オートマトンＭ（Ｘ）に関する初期状態として使用される。非終端記号Ｘでラベルが付けられたエッジが終了する状態が、有限状態オートマトンＭ（Ｘ）の終端状態として使用される。この置換えのため、有限状態オートマトンＭ（Ｘ）は、新しい初期状態を生成するようにさらに変更されている。これが行われる理由は、変更なしでは、図７で示した有限状態オートマトンＫ（Ｓ）におけるＸでラベルが付けられた状態が、図８で示した単純なオートマトンと組み合わされたとき、図８で示した単純なオートマトンの初期状態の挙動を誤った形で変更する状態で終了することになるエッジを有するからである。
【００４０】
図１４は、図１３で示した有限状態オートマトンから拡張された有限状態オートマトンの一例としての実施形態を示している。図１３で示した有限状態オートマトンは、強く結び付いた構成要素Ｓ｛Ｔ，Ｚ｝に関連する文法Ｇの規則が適用されるとき、そのように拡張される。この理由は、置き換えられるエッジに非終端記号Ｔでラベルが付けられているからである。この拡張は、非終端記号Ｔでラベルが付けられたエッジを図１２で示した有限状態オートマトンＭ（Ｔ）で置き換えることによって行われる。非終端記号Ｔでラベルが付けられたエッジが延びる始まりの状態が、有限状態オートマトンＭ（Ｔ）に関する初期状態として使用される。新しい終端状態が、有限状態オートマトンＭ（Ｔ）に関する終端状態として使用される。そうしなければ、有限状態オートマトンＭ（Ｔ）において終端状態を離れるエッジが、図１３で示した有限状態オートマトンの終端状態を誤った形で変更することになる。
【００４１】
図１５は、図１４で示した有限状態オートマトンから拡張された有限状態オートマトンの一例としての実施形態を示している。図１４で示した有限状態オートマトンは、強く結び付いた構成要素Ｓ｛Ｘ，Ｙ｝に関連する文法Ｇの規則が適用されるとき、そのように拡張される。この理由は、置き換えられるエッジに非終端記号Ｘでラベルが付けられているからである。この拡張は、非終端記号Ｘでラベルが付けられ、３の重みを有するエッジを図１１で示した有限状態オートマトンＭ（Ｘ）で置き換えることによって行われる。非終端記号Ｘでラベルが付けられ、３の重みを有するエッジが延びる始まりの状態が、有限状態オートマトンＭ（Ｘ）に関する初期状態として使用される。非終端記号Ｘでラベルが付けられ、３の重みを有するエッジが終了する状態が、有限状態オートマトンＭ（Ｘ）に関する終端状態として使用される。非終端記号Ｘでラベルが付けられたエッジの重み３が、有限状態オートマトンＭ（Ｘ）の初期状態から延びるエッジの重みに追加される。この置換えのため、有限状態オートマトンＭ（Ｘ）は、新しい初期状態を生成するように変更されており、図１１で示した有限状態オートマトンＭ（Ｘ）が初期状態を有して、新しい初期状態から延びるエッジのコストを図７で示した有限状態オートマトンＫ（Ｓ）における元のエッジの重みを変えることなしに変更できるようにしている。
【００４２】
図１６は、図１５で示した有限状態オートマトンから拡張された有限状態オートマトンの一例としての実施形態を示している。図１５で示した有限状態オートマトンは、強く結び付いた構成要素Ｓ｛Ｘ，Ｙ｝に関連する文法Ｇの規則が適用されるとき、そのように拡張される。この理由は、置き換えられるエッジに非終端記号Ｙでラベルが付けられているからである。この拡張は、非終端記号Ｙでラベルが付けられ、０の重みを有するエッジを図９で示した有限状態オートマトンＭ（Ｙ）で置き換えることによって行われる。非終端記号Ｙでラベルが付けられ、０の重みを有するエッジが延びる始まりの状態が、有限状態オートマトンＭ（Ｙ）に関する初期状態として使用される。非終端記号Ｙでラベルが付けられ、０の重みを有するエッジが終了する状態が、有限状態オートマトンＭ（Ｙ）に関する終端状態として使用される。
【００４３】
図１７は、図１６で示した有限状態オートマトンから拡張された有限状態オートマトンの一例としての実施形態を示している。図１６で示した有限状態オートマトンは、強く結び付いた構成要素Ｓ｛Ｘ，Ｙ｝に関連する文法Ｇの規則が適用されるとき、そのように拡張される。この理由は、置き換えられるエッジに非終端記号Ｙでラベルが付けられているからである。この拡張は、非終端記号Ｙでラベルが付けられ、１の重みを有するエッジを図１０で示した有限状態オートマトンＭ（Ｙ）で置き換えることによって行われる。非終端記号Ｙでラベルが付けられ、１の重みを有するエッジが延びる始まりの状態が、有限状態オートマトンＭ（Ｙ）に関する初期状態として使用される。非終端記号Ｙでラベルが付けられ、１の重みを有するエッジが終了する状態が、有限状態オートマトンＭ（Ｙ）に関する終端状態として使用される。非終端記号Ｙでラベルが付けられたエッジの重み１は、有限状態オートマトンＭ（Ｙ）の初期状態から延びるエッジの重みに追加される。この置換えのため、有限状態オートマトンＭ（Ｙ）は、新しい初期状態を生成するように変更されており、図１０で示した有限状態オートマトンＭ（Ｙ）が初期状態を有して、新しい初期状態から延びるエッジのコストを図７で示した有限状態オートマトンＫ（Ｓ）における元のエッジの重みを変えることなしに変更できるようにしている。図１７で示した有限状態オートマトンには、文法の非終端記号でラベルが付けられたエッジが全く残っていないため、図９〜１２で示した有限状態オートマトンＭ（Ｘ）、Ｍ（Ｙ）、Ｍ（Ｚ）、またはＭ（Ｔ）のどれかで置換えを必要とするエッジは、全く存在しない。
【００４４】
図１８は、本発明による文脈依存文法および／または文脈自由文法から重み付き有限状態アクセプタおよび有限状態トランスデューサを生成するための方法の一例としての実施形態の概要を示す流れ図である。図１８で示すとおり、この方法の動作は、ステップ１００で開始し、文法が入力されるステップ２００に進む。次に、ステップ３００で、入力された文法が、文脈自由文法であるか、または文脈依存文法であるかの判定が行われる。入力された文法が文脈自由文法である場合、動作は、ステップ４００に進む。そうでない場合、動作は、ステップ９００にジャンプする。
【００４５】
ステップ４００で、図２で示した文法Ｇ入力ファイルのような文脈自由文法が、図４で示した最小化された有限状態トランスデューサＴＧ′のような有限状態トランスデューサに変換される。次に、ステップ５００で、有限状態トランスデューサの強く結び付いた構成要素が識別され、コンパイルされて、図６および７で示した有限状態オートマトンのような識別された強く結び付いた構成要素を表す有限状態オートマトンになる。次に、ステップ６００で、文法の使用を定義する所望のトポロジを有する有限状態オートマトンまたは有限状態トランスデューサを動的に拡張するかどうかの判定が行われる。この有限状態オートマトンまたは有限状態トランスデューサを動的に拡張する場合、動作は、ステップ８００にジャンプする。そうでなく、有限状態オートマトンまたは有限状態トランスデューサを拡張した後、拡張された形態で記憶する場合、動作は、ステップ７００に進む。
【００４６】
ステップ７００で、ステップ５００で生成された有限状態オートマトンを使用して、所望のトポロジを有する入力の有限状態オートマトンまたは有限状態トランスデューサから十分に拡張された有限状態オートマトンを生成する。次に、動作は、ステップ１０００にジャンプする。一方、ステップ８００では、ステップ５００で生成された有限状態オートマトンを使用して、所望のトポロジを有する入力の有限状態オートマトンまたは有限状態トランスデューサの特定の部分から有限状態オートマトンを動的に、また選択的に拡張する。次に、動作は、再びステップ１１００にジャンプする。
【００４７】
ステップ７００およびステップ８００とは対照的に、ステップ９００では、文脈依存文法をコンパイルして有限状態トランスデューサを生成する。参照によりその全体が本明細書に組み込まれる米国特許第６０３２１１１号が、文脈依存文法から有限状態トランスデューサをコンパイルするための方法の一例としての実施形態を開示している。
【００４８】
ステップ１０００で、有限状態トランスデューサが、局所的に決定される。参照によりその全体が本明細書に組み込まれる米国特許第６２４３６７９号が、有限状態トランスデューサを決定するための方法の一例としての実施形態を開示している。次に、動作は、ステップ１１００に進み、この方法の動作が終了する。
【００４９】
ステップ１００〜５００は、文法をコンパイルして、組み合わせて特定のストリングを受け入れることができる１組の有限状態オートマトンにするための方法を表すことを理解されたい。ステップ１００〜５００で生成されるこの有限状態オートマトンは、以下で概要を述べるとおり、初期のトポロジに応じて異なる仕方で組み合わせることができる。したがって、様々な例としての実施形態では、文法をコンパイルして有限状態オートマトンまたは有限状態トランスデューサにするための方法は、ステップ５００の後、停止することが可能である。その場合は、ステップ７００および１０００が、コンパイルされた文法を静的な仕方で使用するための方法の一例としての実施形態を形成し、一方、ステップ８００は、コンパイルされた文法を動的な仕方で使用するための方法の一例としての実施形態を形成する。したがって、ステップ１００〜５００の後、任意の特定の時点でステップ６００〜１０００のどれかが続く必要はないことを理解されたい。つまり、ステップ１００〜５００とステップ６００〜１０００のどのステップとの間にも、特定の時間的関係は存在しない。さらに、ステップ１０００も省略できることを理解されたい。その場合、動作は、ステップ７００または９００のどちらかから、ステップ１１００に直接にジャンプする。
【００５０】
図１９は、本発明によるステップ４００の図２で示したもののような入力文法ファイルから、図４で示したもののような有限状態トランスデューサを生成するための方法の一例としての実施形態の概要をより詳細に示す流れ図である。図１９で示すとおり、この方法の動作は、ステップ４００で開始してステップ４１０に進み、図３で示したもののような有限状態トランスデューサが生成される。次に、ステップ４２０で、ステップ４１０で生成された有限状態トランスデューサが最小化され、図４で示したもののような最小化された有限状態トランスデューサを形成する。次に、動作は、ステップ４３０に進み、動作は、ステップ５００に戻る。
【００５１】
ステップ４１０で、有限状態トランスデューサの初期状態から最終状態までの別個の有限状態トランスデューサ・パスが、各文法規則から生成される。各パスにおける第１のエッジには、そのエッジの入力ラベルとして設定された規則の左側記号、そのエッジの出力ラベルとして設定された空、そのエッジのコストとして設定された規則の重みが割り当てられている。各パスにおける次のエッジには、そのエッジの入力ラベルとしての空ストリング、そのエッジの出力ラベルとして設定された文法規則の右側の第１の記号、およびゼロに設定された重みが割り当てられている。新しい状態が追加され、現行のエッジが、その状態で終了する。文法規則の右側のそれぞれ追加の記号に関して追加のエッジが生成され、そのエッジにラベルが付けられて重み付けが行われ、また前に概要を述べたとおり、新しい終了状態が生成される。追加のエッジおよび新しい状態は、その文法においてもはや記号が存在しなくなるまで生成される。ただし、規則の最後の記号に関しては、その記号に関して生成されたエッジは、有限状態トランスデューサの終端状態で終了することを理解されたい。
【００５２】
すべての文法規則に関してすべてのパスが生成されたとき、有限状態トランスデューサが完成し、動作は、ステップ４２０に進む。最小化が、同じ入力ラベルを有する同じ状態で開始するエッジを結合し、また同じ出力ラベルを有する同じ状態で終了するエッジを結合することにより、有限状態トランスデューサにおける状態の数を削減する。結合されるエッジの重みが同一でない場合、重みの差は、そのパスの次のエッジまでそのパスで押し下げられる。組み込まれる６７９号の特許が、有限状態トランスデューサを最小化するための方法の一例としての実施形態をより詳細に開示している。
【００５３】
図２０は、本発明によるステップ５００の図１８の有限状態トランスデューサをコンパイルしてクラス置換え有限状態オートマトンを形成するための方法の一例としての実施形態の概要をより詳細に示す流れ図である。図２０で示すとおり、この方法の動作は、ステップ５００で開始してステップ５１０に進み、図５で示したもののような依存関係グラフが、ステップ４００で生成された有限状態トランスデューサを使用して生成される。次に、ステップ５３０で、ステップ５１０で生成された依存関係グラフを使用して、有限状態トランスデューサの強く結び付いた構成要素が判定される。次に、ステップ５５０で、図６および７で示したもののような有限状態オートマトンが、ステップ５３０で判定されたそれぞれ強く結び付いた構成要素から構成される。次に、動作は、ステップ５９０に進み、動作は、ステップ６００に戻る。
【００５４】
図２１は、本発明によるステップ７００の、所望のトポロジを有する有限状態トランスデューサまたは有限状態オートマトンを入力して、その所望のトポロジを有する有限状態トランスデューサまたは有限状態オートマトンを表す有限状態オートマトンを十分に拡張するための方法の一例としての実施形態の概要をより詳細に示す流れ図である。図２１で示すとおり、この方法の動作は、ステップ７００で開始してステップ７１０に進み、所望のトポロジを有する有限状態トランスデューサまたは有限状態オートマトンが入力される。次に、ステップ７２０で、図８で示したもののような単純な有限状態オートマトンが、現行の有限状態オートマトンとして所望のトポロジを有する有限状態トランスデューサまたは有限状態オートマトンから構成される。次に、動作は、ステップ７３０に進む。
【００５５】
ステップ７３０で、現行の有限状態オートマトンからエッジが選択され、そのエッジの非終端記号ラベルが、現行の非終端記号ラベルＡとして選択される。次に、ステップ７４０で、図６および７で示したもののどれかのような現行の非終端記号Ａを含む強く結び付いた構成要素を表す有限状態オートマトンＫ（Ｓ）が変更されて、図９〜１２で示すもののどれかのような現行の非終端記号Ａを受け入れる有限状態オートマトンＭ（Ａ）になる。有限状態オートマトンの変更された形態Ｍ（Ａ）は、有限状態オートマトンＭ（Ａ）の初期状態および終端状態が、現行の有限状態オートマトンの現行の形態に適合するようになっている。次に、ステップ７５０で、有限状態オートマトンＭ（Ａ）が、選択されたエッジ、ならびにそのエッジの開始状態および終了状態の代わりに現行の有限状態オートマトンに挿入され、これにより、現行の有限状態オートマトンが拡張されて、図１３〜１７で示したもののどれかのような新しい現行の有限状態オートマトンになる。次に、動作は、ステップ７６０に進む。
【００５６】
ステップ７６０で、拡張する必要がある何らかの非終端記号が現行の有限状態オートマトンにおいてまだ存在するかどうかが判定される。存在する場合、動作は、ステップ７３０に戻る。存在しない場合、動作は、ステップ７７０に進む。ステップ７７０で、現行の有限状態オートマトンが、十分に拡張された有限状態オートマトンとして出力される。次に、動作は、ステップ７８０に進み、動作は、ステップ１０００に戻る。
【００５７】
図２２は、本発明によるステップ８００の、対応する文法の所望の使用を定義する所望のトポロジを入力し、その所望のトポロジを有する有限状態オートマトンを動的に拡張するための方法の一例としての実施形態の概要をより詳細に示す流れ図である。図２２で示すとおり、この方法の動作は、ステップ８００で開始してステップ８１０に進み、トポロジが入力される。次に、ステップ８２０で、図８で示したもののような単純な有限状態オートマトンが、所望のトポロジから構成され、現行の有限状態オートマトンとして識別される。次に、動作は、ステップ８３０に進む。
【００５８】
ステップ８３０で、所望のトポロジから生成された現行のオートマトンによって処理されるストリングが、入力される。次に、ステップ８４０で、そのストリングの第１の記号または次の記号が選択される。次に、ステップ８５０で、選択された記号に基づき、現行の有限状態オートマトンの拡張が必要であるかどうかの判定が行われる。拡張が必要でない場合、動作は、ステップ８９０にジャンプする。必要な場合、動作は、ステップ８６０に進む。
【００５９】
ステップ８６０で、選択された記号に基づき、選択された記号に対応する非終端記号ラベル「Ａ」を有するエッジが、現行の有限状態オートマトンから選択される。次に、ステップ８７０で、図６および７で示したもののような非終端記号Ａを含む強く結び付いた構成要素を表す有限状態オートマトンＫ（Ｓ）が変更されて、図９〜１２で示したもののどれかのような非終端記号Ａを受け入れる有限状態オートマトンＭ（Ａ）になる。有限状態オートマトンの変更された形態Ｍ（Ａ）は、初期状態および終端状態が、現行の有限状態オートマトンに適合するようになっている。次に、ステップ８８０で、有限状態オートマトンＭ（Ａ）が、選択されたエッジ、ならびにそのエッジの開始状態および終了状態の代わりに現行の有限状態オートマトンに挿入され、これにより、現行の有限状態オートマトンが拡張されて、図１３〜１７で示したもののどれかのような新しい現行の有限状態オートマトンになる。次に、動作は、ステップ８９０に進む。
【００６０】
ステップ８９０で、入力ストリングにおいて何らかの記号がまだ存在するかどうかの判定が行われる。存在する場合、動作は、ステップ８４０に戻る。存在しない場合、動作は、ステップ８９５に進み、動作は、ステップ１１００に戻る。
【００６１】
図２３および２４は、ステップ５１０の依存関係グラフを生成するための方法の一例としての実施形態の概要を示す流れ図である。図２３および２４で示すとおり、この方法の動作は、ステップ５１０で開始してステップ５１１に進み、入力の有限状態トランスデューサの各非終端記号に関して依存関係グラフの中で、ある状態またはあるノードが生成される。次に、ステップ５１２で、入力の有限状態トランスデューサの初期状態が選択される。次に、ステップ５１３で、有限状態トランスデューサの初期状態からの第１のエッジが選択される。次に、動作は、ステップ５１４に進む。
【００６２】
ステップ５１４で、選択されたエッジの終了状態が、現行の状態として選択される。次に、ステップ５１５で、現行の状態から延びるエッジが、新しいエッジとして選択される。次に、ステップ５１６で、新しいエッジの出力ラベルが、非終端記号であるかどうかの判定が行われる。新しいエッジの出力ラベルが、非終端記号である場合、動作は、ステップ５１７に進む。そうでない場合、動作は、ステップ５１８に直接にジャンプする。
【００６３】
ステップ５１７で、依存関係グラフの中で、第１のエッジの入力ラベルである非終端記号に対応する状態から、新しいエッジの出力ラベルである非終端記号に対応する状態までのエッジが、生成される。次に、ステップ５１８で、新しいエッジの終了状態が終端状態であるかどうかの判定が行われる。新しいエッジの終了状態が、終端状態である場合、動作は、ステップ５１９に進む。そうではない場合、動作は、ステップ５１４に戻る。ステップ５１９に動作を進めることにより、終端状態に達したとき、その他のパスが検査される。ステップ５１４に戻ることにより、現行のパスが、別のエッジおよび別の状態について継続して検査される。
【００６４】
ステップ５１９で、検査されていない現行の状態からの残りのエッジが存在するかどうかの判定が行われる。検査されるべき何らかのエッジが残っている場合、動作は、ステップ５２０に進む。残っていない場合、動作は、ステップ５２３にジャンプする。ステップ５２０で、現行の状態が初期状態であるかどうかの判定が行われる。現行の状態が初期状態である場合、動作は、ステップ５２１に進む。初期状態ではない場合、動作は、ステップ５２２にジャンプする。ステップ５２１で、初期状態からの新しい未検査のエッジが、第１のエッジとして選択され、動作は、ステップ５１４に戻る。一方、ステップ５２２では、新しい未検査のエッジは、新しいエッジとして選択され、動作は、ステップ５１６に戻る。
【００６５】
ステップ５２３で、現行の状態が初期状態であるかどうかの判定が行われる。初期状態ではない場合、動作は、ステップ５２４に進み、前の現行の状態が、現行の状態として選択される。次に、動作は、ステップ５１９に戻る。そうでなければ、現行の状態は、初期状態であり、すべてのパスが検査済みである。したがって、動作は、ステップ５２５に進み、動作は、ステップ５３０に戻る。
【００６６】
図２５および２６は、ステップ４３０の有限状態トランスデューサの強く結び付いた構成要素を判定するための方法の一例としての実施形態の概要をより詳細に示す流れ図である。この判定は、ステップ５１０で生成された依存関係グラフを調べることによって行われる。図２５および２６で示すとおり、この方法の動作は、ステップ５３０で開始してステップ５３１に進み、依存関係グラフの中のある状態が、現行の強く結び付いた構成要素Ｓｉに関する初期状態として選択される。次に、ステップ５３２で、依存関係グラフの初期状態からの第１のエッジが選択される。次に、ステップ５３３で、そのエッジの終了状態が、現行の状態として選択される。次に、動作は、ステップ５３４に進む。
【００６７】
ステップ５３４で、現行の状態が、パス状態として識別され、これは、その状態がＳｉにおける非終端記号である可能性を意味する。次に、ステップ５３５で、現行の状態から延びるエッジが、新しいエッジとして選択される。次に、ステップ５３６で、新しいエッジの終了状態が、初期状態であるか、またはＳｉにおける非終端記号として既に識別されているかどうかの判定が行われる。初期状態であるか、またはＳｉにおける非終端記号として既に識別されている場合、閉じたパスが識別され、動作は、ステップ５３７に進む。そうでない場合、動作は、ステップ５３８にジャンプする。
【００６８】
ステップ５３７で、初期状態および新規パス状態が、Ｓｉにおける非終端記号として識別される。次に、動作は、ステップ５３９にジャンプする。一方、ステップ５３８では、新しいエッジの終了状態が、Ｓｉの現行の状態として検査済みであるか、または前に識別された強く結び付いた構成要素の非終端記号として識別されているかどうかの判定が行われる。どちらも該当しない場合、動作は、ステップ５３３に戻る。どちらかが該当する場合、動作は、再びステップ５３９に進む。
【００６９】
ステップ５３９で、検査されるべき現行の状態からの残りのエッジがまだ存在するかどうかの判定が行われる。存在する場合、動作は、ステップ５４０に進む。存在しない場合、動作は、ステップ５４１にジャンプする。ステップ５４０で、現行の状態から延びる次のエッジが、新しいエッジとして選択される。次に、動作は、ステップ５３６に戻る。一方、ステップ５４１では、現行の状態が初期状態であるかどうかの判定が行われる。初期状態ではない場合、動作は、ステップ５４２に進む。初期状態である場合、動作は、ステップ５４４にジャンプする。ステップ５４２で、現行の状態が、Ｓｉにおける非終端記号である可能性がないと明らかにされた場合、その状態は、もはやパス状態として識別されない。次に、ステップ５４３で、直前の現行の状態が、再び現行の状態として選択される。次に、動作は、ステップ５３９に戻る。
【００７０】
一方、ステップ５４４では、依存関係グラフの中のその他のすべての状態が、初期状態として検査済みであるか、または強く結び付いた構成要素の非終端記号として識別されているかどうかの判定が行われる。初期状態として検査済みではなく、強く結び付いた構成要素の非終端記号として識別されていない場合、動作は、ステップ５４５に進み、初期状態として検査済みではない、または強く結び付いた構成要素の非終端記号として識別されていない非終端記号が、初期状態として選択される。次に、動作は、ステップ５３２に戻る。初期状態として検査済みである、または強く結び付いた構成要素の非終端記号として識別されている場合、動作は、ステップ５４６にジャンプし、動作は、ステップ５５０に戻る。
【００７１】
図２７〜３０は、ステップ５５０のそれぞれ強く結び付いた構成要素を表す有限状態オートマトンＫ（Ｓ）を構成するための方法の一例としての実施形態の概要をより詳細に示す流れ図である。図２７〜３０で示すとおり、この方法の動作は、ステップ５５０で開始してステップ５５１に進み、第１の強く結び付いた構成要素Ｓｉまたは次の強く結び付いた構成要素Ｓｉが選択される。次に、ステップ５５２で、選択された強く結び付いた構成要素Ｓｉにおける各非終端記号に関して、ある有限状態オートマトン状態が生成される。次に、ステップ５５３で、選択された強く結び付いた構成要素Ｓｉにおける非終端記号のどれかでラベルが付けられ、ステップ４３０で使用された入力の有限状態トランスデューサの初期状態から延びる第１のエッジまたは次のエッジが、第１のエッジとして、また現行のエッジとして選択される。次に、ステップ５５４で、現行のエッジの終了状態が、現行の状態として選択される。次に、動作は、ステップ５５５に進む。
【００７２】
ステップ５５５で、現行の状態から延びるエッジが、新しいエッジとして選択される。次に、ステップ５５６で、その新しいエッジが、パス・エッジとして識別される。次に、ステップ５５７で、その新しいエッジの終了状態が最終状態であるかどうかの判定が行われる。最終状態である場合、完成したパスが識別され、動作は、ステップ５５９にジャンプする。最終状態ではない場合、動作は、ステップ５５８に進み、その新しいエッジは、新しい現行のエッジになる。次に、動作は、ステップ５５４に戻る。
【００７３】
ステップ５５９で、選択された強く結び付いた構成要素Ｓｉにおける非終端記号である出力ラベルを有するパス・エッジが存在するかどうかの判定が行われる。存在しない場合、そのパスは、右リニアまたは左リニアのどちらかである。したがって、動作は、ステップ５６０に進む。存在する場合、動作は、ステップ５６３にジャンプする。
【００７４】
ステップ５６０で、右リニアであることが明らかになった現行の強く結び付いた構成要素Ｓｉにおける前のパスが存在するかどうかの判定が行われる。存在する場合、選択された強く結び付いた構成要素Ｓｉは、右リニアである。したがって、動作は、ステップ５６１に進む。存在しない場合、選択された強く結び付いた構成要素Ｓｉは、左リニアであり、動作は、ステップ５６２にジャンプする。ステップ５６１で、有限状態オートマトンＫ（Ｓｉ）において、第１のエッジ上の入力記号に対応する非終端状態からＫ（Ｓｉ）の最終状態までのパスが生成される。有限状態オートマトンＫ（Ｓｉ）のこのパスは、選択された強く結び付いた構成要素Ｓｉの非終端記号でラベルが付けられていないあらゆるパス・エッジに関するエッジを含まなければならない。必要に応じてエッジ間で新しい状態が生成される。次に、動作は、ステップ５７５にジャンプする。
【００７５】
一方、ステップ５６１では、有限状態オートマトンＫ（Ｓｉ）において、Ｋ（Ｓｉ）の初期状態から第１のエッジ上の入力記号に対応する非最終状態までのパスが生成される。有限状態オートマトンＫ（Ｓｉ）のこのパスは、選択された強く結び付いた構成要素Ｓｉの非終端記号でラベルが付けられていない各パス・エッジに関するエッジを含まなければならない。必要に応じてエッジ間で新しい状態が生成される。次に、動作は、ステップ５７６にジャンプする。
【００７６】
ステップ５６０で、パスは、右リニアまたは左リニアの両方として（すなわち、どちらとしても）扱うのが可能であることを理解されたい。したがって、選択された強く結び付いた構成要素Ｓｉにおける別のパスが、右リニアまたは左リニアとして識別される前に、ステップ５６０に達した場合には、そのパスに関するパス・エッジ情報を保存しなければならない。その場合、ステップ５６０、およびステップ５６１または５６２のどちらかが、選択された強く結び付いた構成要素Ｓｉが右リニアまたは左リニアであることが判定された後になって初めて、そのパスに関して実行される。
【００７７】
ステップ５６３で、選択された強く結び付いた構成要素Ｓｉの非終端記号である出力を有する複数のパス・エッジが存在するかどうかの判定が行われる。存在する場合、そのパスは、適格でない。したがって、動作は、ステップ５７１にジャンプする。存在しない場合、動作は、ステップ５６４に進み、複数のパス・エッジが存在するかどうかの判定が行われる。複数のパス・エッジが存在する場合、そのパスは、右リニアまたは左リニアであるはずである。したがって、動作は、ステップ５７３にジャンプする。存在しない場合、動作は、ステップ５６５に進む。
【００７８】
ステップ５６５で、最後に判定されたパス・エッジに、選択された強く結び付いた構成要素Ｓｉの非終端記号でラベルが付けられているかどうかの判定が行われる。付けられている場合、そのパスは、右リニアである。したがって、動作は、ステップ５６７にジャンプする。付けられていない場合、動作は、ステップ５６６に進む。ステップ５６６で、最初に判定されたパス・エッジが、選択された強く結び付いた構成要素Ｓｉにおける非終端記号である出力を有するかどうかの判定が行われる。有する場合、そのパスは、左リニアである。したがって、動作は、ステップ５６９にジャンプする。有さない場合、その文法は、適格ではなく、動作は、再びステップ５７１にジャンプする。
【００７９】
ステップ５６７で、そのパスが、右リニアとして識別される。次に、ステップ５６８で、左リニアであると判定された何らかの前のパスが、現行の強く結び付いた構成要素Ｓｉにおいて存在するかどうかの判定が行われる。存在する場合、その文法は、適格ではなく、動作は、再びステップ５７１にジャンプする。存在しない場合、動作は、ステップ５７４にジャンプする。
【００８０】
一方、ステップ５６９では、そのパスが、左リニアとして識別される。次に、ステップ５７０で、右リニアであると判定された何らかの前のパスが、現行の強く結び付いた構成要素Ｓｉにおいて存在するかどうかの判定が行われる。存在しない場合、その文法は、適格であり、動作は、ステップ５７５にジャンプする。存在する場合、その文法は、やはり適格ではなく、動作は、ステップ５７１に進む。ステップ５７１で、文法が適格ではないという出力指示が生成される。次に、動作は、ステップ５７２に進み、この方法の動作は、ステップ１１００に戻る。
【００８１】
ステップ５７３で、右リニアである検査された何らかの前のパスが存在するかどうかの判定が行われる。存在する場合、選択された強く結び付いた構成要素Ｓｉは、右リニアである。したがって、動作は、ステップ５７４に進む。存在しない場合、選択された強く結び付いた構成要素Ｓｉは、左リニアであり、動作は、ステップ５７５に進む。ステップ５７３で、パスは、右リニアまたは左リニアとして扱うのが可能であることを理解されたい。したがって、選択された強く結び付いた構成要素Ｓｉにおける別のパスが右リニアまたは左リニアであると識別される前に、ステップ５７３に達した場合には、そのパスに関するパス・エッジ情報を保存しなければならない。選択された強く結び付いた構成要素Ｓｉが、右リニアまたは左リニアであると判定された後になって初めて、ステップ５７３、およびステップ５７４または５７５のどちらかが、そのパスに関して実行される。
【００８２】
ステップ５７４で、有限状態オートマトンＫ（Ｓｉ）において、第１のエッジの入力記号に対応する非終端状態から最後のパス・エッジの出力記号に対応する非終端状態までのパスが生成される。有限状態オートマトンＫ（Ｓｉ）におけるこのパスは、選択された強く結び付いた構成要素Ｓｉの非終端記号でラベルが付けられていない各パス・エッジに関するエッジを含まなければならない。必要に応じてエッジ間で新しい状態が生成される。次に、動作は、ステップ５７６にジャンプする。
【００８３】
ステップ５７５で、有限状態オートマトンＫ（Ｓｉ）において、最後のパス・エッジの出力ラベルに対応する非終端状態から、第１のエッジの入力ラベルに対応する非終端状態までのパスが生成される。有限状態オートマトンＫ（Ｓｉ）におけるこのパスは、選択された強く結び付いた構成要素Ｓｉの非終端記号でラベルが付けられていない各パス・エッジに関するエッジを含まなければならない。必要に応じてエッジ間で新しい状態が生成される。次に、動作は、ステップ５７６に進む。
【００８４】
ステップ５７６で、現行の新しいエッジは、そのパスの最後のエッジであり、したがって、パス・エッジとして除去される。次に、ステップ５７７で、検査されるべき現行の状態からの残りのエッジがまだ存在するかどうかの判定が行われる。存在する場合、動作は、ステップ５７８に進む。存在しない場合、動作は、ステップ５７９にジャンプする。ステップ５７８で、現行の状態から延びる次のエッジが、新しいエッジとして選択される。次に、動作は、ステップ５５４に戻る。
【００８５】
一方、ステップ５７９では、終了状態が現行の状態である最後の選択されたエッジの開始状態が、新しい現行の状態として選択される。次に、ステップ５７０で、現行の状態が初期状態であるかどうかの判定が行われる。初期状態ではない場合、動作は、ステップ５７６に戻る。初期状態である場合、動作は、ステップ５８１に進む。ステップ５８１で、選択された強く結び付いた構成要素Ｓｉの非終端記号のどれかを入力ラベルとして有する入力の有限状態トランスデューサの初期状態からの別の第１のエッジが存在するかどうかの判定が行われる。存在する場合、動作は、ステップ５５３に戻る。存在しない場合、動作は、ステップ５８２に進む。
【００８６】
ステップ５８２で、自らのために有限状態オートマトンＫ（Ｓｉ）が構成される必要がある別の強く結び付いた構成要素が存在するかどうかの判定が行われる。存在する場合、動作は、ステップ５５１に戻る。存在しない場合、動作は、ステップ５８３に進み、動作は、ステップ５９０に戻る。
【００８７】
図３１は、本発明による文法を表す重み付き有限状態オートマトンを生成するのに使用可能な文法−有限状態オートマトン生成システム１３００の一例としての実施形態を示す図である。図３１で示すとおり、文法変形システム１３００は、入力／出力インターフェース１３０５と、コントローラ１３１０と、メモリ１３２０と、有限状態トランスデューサを生成する回路、ルーチン、またはアプリケーション１３３０と、有限状態を最小化または局所的に決定する回路、ルーチン、またはアプリケーション１３３５と、依存関係グラフを生成する回路、ルーチン、またはアプリケーション１３４０と、強く結び付いた構成要素を識別する回路、ルーチン、またはアプリケーション１３５０と、有限状態オートマトンを生成する回路、ルーチン、またはアプリケーション１３６０と、有限状態を拡張する回路、ルーチン、またはアプリケーション１３７０とを含み、以上のそれぞれが、１つまたは複数のコントロールおよび／またはデータ・バスおよび／またはアプリケーション・プログラム・インターフェース１３１５で互いに接続されている。
【００８８】
図３１で示すとおり、文法データ・ソース１４００、有限状態オートマトン・データ・シンク１５００、および１つまたは複数のユーザ入力デバイス１６００がそれぞれ、リンク１４０５、１５０５、および１６０５で文法−有限状態オートマトン生成システム１３００に接続されている。
【００８９】
一般に、文法データ・ソース１４００および有限状態オートマトン・データ・シンク１５００は、汎用コンピュータなどのいくつかの異なるデバイスの任意のもの、あるいはネットワークまたはインターネットつまりＷｏｒｌｄ　ＷｉｄｅＷｅｂのクライアントまたはサーバなどの文法データを記憶し、かつ／または伝送するのに適したデバイスであることが可能である。例えば、文法データ・ソース１４００または有限状態オートマトン・データ・シンク１５００は、文法データを含む磁気記憶ディスク、ＣＤ−ＲＯＭなどのデータ媒体、またはホスト・コンピュータであることが可能である。
【００９０】
一般に、文法データ・ソース１４００および有限状態オートマトン・データ・シンク１５００は、本発明の文法−有限状態オートマトン生成システム１３００に文法データを提供すること、または本発明の文法−有限状態オートマトン生成システム１３００から文法データを受け取ることができる任意の周知のデバイスまたは将来に開発されるデバイスであることが可能である。図３１の文法データ・ソース１４００または有限状態オートマトン・データ・シンク１５００は、同じタイプのデバイスである必要はないことを理解されたい。
【００９１】
文法データ・ソース１４００または有限状態オートマトン・データ・シンク１５００は、内部磁気記憶ディスクを備えた汎用コンピュータとしてなど、文法−有限状態オートマトン生成システム１３００に統合することができる。さらに、文法−有限状態オートマトン生成システム１３００は、音声認識システムなどの文法を使用してデータを処理するより大型のシステムとして、文法データ・ソース１４００または有限状態オートマトン・データ・シンク１５００に加えて追加の機能を提供するデバイスに統合することができる。
【００９２】
１つまたは複数のユーザ入力デバイス１６００は、キーボード、マウス、ジョイ・スティック、トラックボール、タッチ・パッド、タッチ・スクリーン、ペン・ベースのシステム、マイクロホンおよび関連の音声認識ソフトウェアの１つまたは複数の任意の組合せ、あるいはユーザ・コマンドおよび／またはデータを文法−有限状態オートマトン生成システム１３００に入力するための任意の他の周知のデバイスまたは将来に開発されるデバイスであることが可能である。
【００９３】
文法データ・ソース１４００、有限状態オートマトン・データ・シンク１５００、および１つまたは複数の入力デバイス１６００をそれぞれ、文法−有限状態オートマトン生成システム１３００に接続するリンク１４０５、１５０５、および１６０５のそれぞれは、直接ケーブル接続、モデム、ローカル・エリア・ネットワーク、ワイド・エリア・ネットワーク、イントラネット、ストーレッジ・エリア・ネットワーク、エクストラネット、インターネット、任意の他の分散処理ネットワーク、あるいは任意の他の周知の接続デバイスまたは将来に開発される接続デバイスであることが可能である。以上の接続のどれも、有線または無線であるのが可能であることを理解されたい。一般に、リンク１４０５、１５０５、および１６０５のそれぞれは、それぞれのデバイスを文法−有限状態オートマトン生成システム１３００に接続するのに使用可能な任意の周知の、または将来に開発される接続システムもしくは接続構造を使用して実装することができる。リンク１４０５、１５０５、および１６０５は、同じタイプである必要はないことを理解されたい。
【００９４】
メモリ１３２０は、可変メモリ、揮発性メモリ、または不揮発性メモリ、あるいは可変ではないメモリ、つまり固定メモリの任意の適切な組合せを使用して実装することができる。揮発性または不揮発性の可変メモリは、スタティックＲＡＭまたはダイナミックＲＡＭ、フロッピー（登録商標）・ディスクおよびフロッピー（登録商標）・ディスク・ドライブ、書込み可能または書換え可能の光ディスクおよび光ディスク・ドライブ、ハード・ドライブ、フラッシュ・メモリ等の任意の１つまたは複数を使用して実装することができる。同様に、可変でない、つまり固定のメモリは、ＲＯＭ、ＰＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭの任意の１つまたは複数を使用して実装することができ、ＣＤ−ＲＯＭディスクまたはＤＶＤ−ＲＯＭディスクおよびＣＤ−ＲＯＭディスク・ドライブまたはＤＶＤ−ＲＯＭディスク・ドライブなどの光ＲＯＭディスクをギャップする。
【００９５】
文法−有限状態オートマトン生成システム１３００の様々な構成要素のそれぞれは、プログラミングされた汎用コンピュータ、特殊目的コンピュータ、マイクロプロセッサ等の上で実行されるソフトウェアとして実装することができる。あるいは、文法−有限状態オートマトン生成システム１３００の様々な構成要素のそれぞれは、ライブラリに埋め込まれたルーチン、またはサーバ上に常駐するリソース等として実装することができる。また、文法−有限状態オートマトン生成システム１３００は、文法−有限状態オートマトン生成システム１３００を、コンピュータまたは通信デバイスの音声認識システムまたは言語翻訳システムなどのソフトウェアおよび／またはハードウェア・システムに物理的に組み込むことによって実装することもできる。文法−有限状態オートマトン生成システム１３００の様々な構成要素のそれぞれは、同じ仕方で実装する必要はないことを理解されたい。
【００９６】
また、図３１で示す回路、ルーチン、オブジェクト、アプリケーション、またはマネージャおよび構成要素１３０５〜１３７０のそれぞれは、適切にプログラミングされた汎用コンピュータの部分としてそれぞれ実装できることも理解されたい。あるいは、図３１で示した回路、ルーチン、アプリケーション、またはマネージャのそれぞれは、デジタル信号プロセッサ（ＤＳＰ）を使用して、ＦＰＧＡ、ＰＬＤ、ＰＬＡ、および／またはＰＡＬを使用して、あるいは別個の論理要素または別個の回路要素を使用して、ＡＳＩＣ内部の物理的に別個のハードウェア回路として実装することができる。図３１で示した様々な構成要素の回路、ルーチン、オブジェクト、アプリケーション、またはマネージャ１３０５〜１３７０がとる特定の形態は、設計上の選択であり、当分野の技術者にとって明白で、予測可能であろう。
【００９７】
文法−有限状態オートマトン生成システム１３００を動作させる際、図２で示したもののような形式の正規ではない文法を表す入力の文法規則が、リンク１４０５を介して文法データ・ソース・デバイス１４００から出力される。入力／出力インターフェース１３０５が、受け取った文法規則を入力し、コントローラ１３１０の制御の下で、受け取った文法規則をメモリ１３２０の入力文法部１３２１に転送するか、あるいは有限状態トランスデューサを生成する回路、ルーチン、またはアプリケーション１３３０に直接に転送する。
【００９８】
コントローラ１３１０の制御の下で、有限状態トランスデューサを生成する回路、ルーチン、またはアプリケーション１３３０が、入力文法部１３２１から入力文法規則を取り出すか、または入力の文法規則を直接に受け取る。有限状態トランスデューサを生成する回路、ルーチン、またはアプリケーション１３３０は、受け取った文法規則に基づき、図３で示したもののような有限状態トランスデューサを生成する。入力の文法における各規則に関して、この有限状態トランスデューサにおいてパスが生成される。所与の入力の文法規則に関して、その規則における各文法記号に関して、その規則を表す有限状態トランスデューサ・パスにおいてエッジが生成される。有限状態トランスデューサ・パスにおけるこのエッジには、そのパスが表し、その規則において記号が出現するのと同じシーケンスで生じる入力の文法規則からの対応する記号でラベルが付けられる。次に、有限状態トランスデューサは、コントローラ１３１０の制御の下で、メモリ１３２０の有限状態トランスデューサ部１３２２の中に記憶されるか、あるいは有限状態マシンを最小化もしくは局所的に決定する回路、ルーチン、またはアプリケーション１３３５に直接に出力される。
【００９９】
したがって、コントローラ１３１０の制御の下で、有限状態マシンを最小化または局所的に決定する回路、ルーチン、またはアプリケーション１３３５が、有限状態トランスデューサ部１３２２から有限状態トランスデューサを取り出すか、または有限状態トランスデューサを直接に受け取る。最小化または局所的に決定する回路、ルーチン、またはアプリケーション１３３５は、元の有限状態トランスデューサを最小化して、図４で示すもののような新しい最小化された有限状態トランスデューサを生成する。元の有限状態トランスデューサから最小化された有限状態トランスデューサを生成するため、同様の入力記号または出力記号を有するエッジを結合して、元の有限状態トランスデューサにおける冗長性が削減される。有限状態マシンを最小化するための任意の１つまたは複数の周知の方法または将来に開発される方法を使用できることを理解されたい。有限状態マシンを最小化するための方法の一例としての実施形態が、組み込まれる６７９号の特許でより詳細に開示されている。次に、最小化された有限状態トランスデューサは、コントローラ１３１０の制御の下で、メモリ１３２０の有限状態トランスデューサ部１３２２の中に記憶されるか、または依存関係グラフを生成する回路、ルーチン、またはアプリケーション１３４０に直接に出力される。
【０１００】
したがって、コントローラ１３１０の制御の下で、依存関係グラフを生成する回路、ルーチン、またはアプリケーション１３４０は、有限状態トランスデューサ部１３２２から最小化された有限状態トランスデューサを取り出すか、または最小化された有限状態トランスデューサを直接に受け取る。依存関係グラフを生成する回路、ルーチン、またはアプリケーション１３４０は、図５で示したもののような依存関係グラフを生成する。依存関係グラフを生成する回路、ルーチン、またはアプリケーション１３４０は、非終端記号でラベルが付けられた最小化された有限状態トランスデューサの各エッジに関してある状態を有する有限状態オートマトンを生成する。また、依存関係グラフを生成する回路、ルーチン、またはアプリケーション１３４０は、有限状態トランスデューサの初期状態で開始せず、非終端記号でラベルが付けられた最小化された有限状態トランスデューサにおける各エッジに関する依存関係グラフにおけるエッジも生成する。依存関係グラフの各エッジは、非終端記号を表す依存関係グラフの状態で終了し、有限状態トランスデューサ初期状態で開始する有限状態トランスデューサ・エッジの非終端記号ラベルを表す依存関係グラフ状態で開始する。次に、依存関係グラフは、コントローラ１３２０の制御の下で、メモリ１３２０の依存関係グラフ部１３２３の中に記憶されるか、または強く結び付いた構成要素を識別する回路、ルーチン、またはアプリケーション１３５０に直接に出力される。
【０１０１】
コントローラ１３１０の制御の下で、強く結び付いた構成要素を識別する回路、ルーチン、またはアプリケーション１３５０は、依存関係グラフを取り出すか、または直接に受け取る。強く結び付いた構成要素を識別する回路、ルーチン、またはアプリケーション１３５０は、その依存関係グラフに基づいて入力の文法の強く結び付いた構成要素を識別する。強く結び付いた構成要素を識別する回路、ルーチン、またはアプリケーション１３５０は、依存関係グラフを探索して、選択された開始状態から１つまたは複数の他の状態を通ってその選択された開始状態まで戻るようにエッジを辿ることができる依存関係グラフのすべてのパスを識別する。少なくとも１つの共通状態を共用するすべてのそのようなパスが、単一の強く結び付いた構成要素として識別される。単一の強く結び付いた構成要素に含まれる状態を表す非終端記号が、その強く結び付いた構成要素の非終端記号として識別される。次に、強く結び付いた構成要素、およびその構成要素の非終端記号が、コントローラ１３１０の制御の下で、メモリ１３２０の強く結び付いた構成要素部１３２４の中に記憶される。
【０１０２】
次に、コントローラ１３１０の制御の下で、有限状態オートマトンを生成する回路、ルーチン、またはアプリケーション１３６０が、メモリ１３２０の有限状態トランスデューサ部１３２２から有限状態トランスデューサを取り出し、また強く結び付いた構成要素の非終端記号をメモリ１３２０の強く結び付いた構成要素部１３２４から取り出すか、または強く結び付いた構成要素を識別する回路、ルーチン、またはアプリケーション１３５０から直接に取得する。次に、有限状態オートマトンを生成する回路、ルーチン、またはアプリケーション１３６０は、それぞれ強く結び付いた構成要素に関して、その強く結び付いた構成要素の相互依存関係を定義する最小化された有限状態トランスデューサのパスを含む有限状態オートマトンを生成する。有限状態オートマトンを生成する回路、ルーチン、またはアプリケーション１３６０は、その強く結び付いた構成要素における各非終端記号に関してある状態を生成する。有限状態オートマトンを生成する回路、ルーチン、またはアプリケーション１３６０は、入力の有限状態トランスデューサからのパスを、各終端記号に関して、またその強く結び付いた構成要素のメンバではない各非終端記号に関してエッジを追加することによって有限状態オートマトンに組み込む。次に、生成された有限状態オートマトンが、コントローラ１３１０の制御の下で、メモリ１３２０の有限状態オートマトン部１３２５の中に記憶されるか、または様々な例としての実施形態では、リンク１５０５を介して有限状態オートマトン・データ・シンク・デバイス１５００に直接または間接に出力される。
【０１０３】
コントローラ１３１０の制御の下で、有限状態オートマトンを拡張する回路、ルーチン、またはアプリケーション１３７０が、１つまたは複数のユーザ入力デバイス１６００の１つまたは複数を使用してユーザによって入力されたか、または有限状態オートマトン部１３２５の中に記憶された生成された有限状態オートマトンを使用して完了されるべきタスクに基づいて自動的に生成されたトポロジを受け取る。有限状態オートマトンを拡張する回路、ルーチン、またはアプリケーション１３７０は、入力のトポロジを受け入れる単純なオートマトンを生成する。単一のオートマトンが使用される前に十分に拡張される様々な例としての実施形態では、有限状態オートマトンを拡張する回路、ルーチン、またはアプリケーション１３７０は、その単一のオートマトンの各エッジを拡張するか、または有限状態オートマトンを生成する回路、ルーチン、またはアプリケーション１３６０によって生成され、有限状態オートマトン部１３２５の中に記憶された有限状態オートマトンの対応するものでそのエッジ、ならびにそのエッジの開始状態および終了状態を置き換えることにより、有限状態オートマトンを拡張する回路、ルーチン、またはアプリケーション１３７０によって生成された中間オートマトンを拡張する。有限状態オートマトンを拡張する回路、ルーチン、またはアプリケーション１３７０は、拡張することが可能な非終端記号でラベルが付けられたすべてのエッジが拡張されるまで、中間オートマトンのエッジを拡張することを続ける。
【０１０４】
一方、様々な他の例としての実施形態では、単純なオートマトンが、文法の入力された非終端記号のシーケンスまたはストリングを認識するのに使用されるのにつれ、有限状態オートマトンを拡張する回路、ルーチン、またはアプリケーション１３７０を使用して、その単純なオートマトンが動的に拡張される。その場合、受け取られた文法記号に基づき、有限状態オートマトンを拡張する回路、ルーチン、またはアプリケーション１３７０は、入力のトポロジを表す単純なオートマトン、または前の拡張動作によって得られたオートマトンの現行のパスにおける次のエッジを、そのエッジを拡張する必要がある場合、動的に拡張する。そのエッジを拡張する必要がない場合、そのエッジは、単にトラバースされ、次の記号が入力される。
【０１０５】
入力記号に基づき、単純なオートマトン、または単純なオートマトンの拡張されたバージョンのエッジを拡張するため、有限状態オートマトンを拡張する回路、ルーチン、またはアプリケーション１３７０は、コントローラ１３１０の制御の下で、その入力の非終端記号を状態として含む有限状態オートマトンをメモリ１３２０の有限状態オートマトン部１３２５から取り出す。次に、この有限状態オートマトンを変更して、対応する強く結び付いた構成要素が右リニアである場合、その入力記号に対応する状態を初期状態にする。あるいは、有限状態オートマトンを変更して、対応する強く結び付いた構成要素が左リニアである場合、その入力記号に対応する状態を終了状態にする。次に、変更された有限状態オートマトンで、拡張されるべき入力記号に対応するエッジが置き換えられる。変更された有限状態オートマトンの初期状態が、置き換えられるエッジの開始状態になり、また変更された有限状態オートマトンの終了状態が、置き換えられるエッジの終了状態になる。次に、拡張された有限状態オートマトンが、コントローラ１３１０の制御の下で、メモリ１３２０の拡張された有限状態オートマトン部１３２６の中に記憶されるか、またはリンク１５０５を介して有限状態オートマトン・データ・シンク１５００に直接に出力される。
【０１０６】
有限状態オートマトンを拡張する回路、ルーチン、またはアプリケーション１３７０は、省略するのが可能であることを理解されたい。その場合、文法−有限状態オートマトン生成システム１３００を使用して、有限状態オートマトンを生成する回路、ルーチン、またはアプリケーション１３６０によって生成される有限状態オートマトンを生成することができる。また、有限状態マシンを最小化または局所的に決定する回路、ルーチン、またはアプリケーション１３３５も省略するのが可能であることも理解されたい。その場合、依存関係グラフを生成する回路、ルーチン、またはアプリケーション１３４０、および有限状態オートマトンを生成する回路、ルーチン、またはアプリケーション１３６０は、有限状態トランスデューサを生成する回路、ルーチン、またはアプリケーション１３３０によって生成された元の有限状態トランスデューサを使用する。
【０１０７】
本発明を以上に概要を述べた例としての実施形態に関連して説明してきたが、当分野の技術者には、多くの代替形態、修正形態、および変形形態が明白であることが明らかである。したがって、以上に提示した本発明の例としての実施形態は、例示するものであり、制限するものではない。本発明の趣旨および範囲を逸脱することなく、様々な変更を加えることができる。
【図面の簡単な説明】
【図１】文法Ｇの一例としての実施形態を示す図である。
【図２】本発明による文法Ｇを重み付き有限状態トランスデューサに変換する文法−有限状態トランスデューサ変換システムに文法を入力するのに使用可能な形式の一例としての実施形態を示す図である。
【図３】本発明による例としての文法Ｇから生成された重み付き有限状態トランスデューサの一例としての実施形態を示す図である。
【図４】本発明による図３で示した重み付き有限状態トランスデューサから生成された最小化された重み付き有限状態トランスデューサの一例としての実施形態を示す図である。
【図５】本発明による図４で示した有限状態トランスデューサから生成された依存関係グラフの一例としての実施形態を示す図である。
【図６】本発明による図５で示した依存関係グラフを使用して識別された、図４で示した有限状態トランスデューサの強く結び付いた構成要素Ｓ｛Ｔ，Ｚ｝を表す重み付き有限状態オートマトンの一例としての実施形態を示す図である。
【図７】本発明による図５で示した依存関係グラフを使用して識別された、図４で示した有限状態トランスデューサの強く結び付いた構成要素Ｓ｛Ｘ，Ｙ｝を表す重み付き有限状態オートマトンの一例としての実施形態を示す図である。
【図８】本発明による図４で示した有限状態トランスデューサのサブセットのアクティブな非終端記号を受け入れる入力されたトポロジを表す有限状態オートマトンの一例としての実施形態を示す図である。
【図９】本発明による図７で示した有限状態オートマトンから得られた、アクティブな終端記号として非終端記号Ｙを受け入れる有限状態オートマトンＭ（Ｙ）の第１の例としての実施形態を示す図である。
【図１０】本発明による図７で示した有限状態オートマトンから得られた、アクティブな終端記号として非終端記号Ｙを受け入れる有限状態オートマトンＭ（Ｙ）の第２の例としての実施形態を示す図である。
【図１１】本発明による図７で示した有限状態オートマトンから得られた、アクティブな終端記号として非終端記号Ｘを受け入れる有限状態オートマトンＭ（Ｘ）の一例としての実施形態を示す図である。
【図１２】本発明による図６で示した有限状態オートマトンから得られた、アクティブな終端記号として非終端記号Ｔを受け入れる有限状態オートマトンＭ（Ｔ）の一例としての実施形態を示す図である。
【図１３】本発明による図８で示した有限状態オートマトンにおける記号Ｘでラベルが付けられたエッジを図１１で示した有限状態オートマトンで置き換えることによって生成された、拡張された有限状態オートマトンの第１の例としての実施形態を示す図である。
【図１４】本発明による図１３で示した記号Ｔでラベルが付けられたエッジを図１２で示した有限状態オートマトンで置き換えることによって生成された、拡張された有限状態オートマトンの第２の例としての実施形態を示す図である。
【図１５】本発明による図１４で示した記号Ｘおよび重み３でラベルが付けられたエッジを図１１で示した有限状態オートマトンで置き換えることによって生成された、拡張された有限状態オートマトンの第３の例としての実施形態を示す図である。
【図１６】本発明による図１５で示した記号Ｙおよび重みゼロでラベルが付けられたエッジを図９で示した有限状態オートマトンで置き換えることによって生成された、拡張された有限状態オートマトンの第４の例としての実施形態を示す図である。
【図１７】本発明による図１６で示した記号Ｙおよび重み１でラベルが付けられたエッジを図１０で示した有限状態オートマトンで置き換えることによって生成された、拡張された有限状態オートマトンの第５の例としての実施形態を示す図である。
【図１８】本発明による文法を有限状態オートマトンに変換するための方法の一例としての実施形態の概要を示す流れ図である。
【図１９】本発明による入力文法から圧縮された有限状態トランスデューサを生成するための方法の一例としての実施形態の概要をより詳細に示す流れ図である。
【図２０】本発明による図１８の文脈自由文法を表す有限状態トランスデューサをコンパイルして１つまたは複数の有限状態オートマトンにするための方法の一例としての実施形態の概要をより詳細に示す流れ図である。
【図２１】本発明によるトポロジを入力し、図２０の文脈自由文法を表す有限状態オートマトンを十分に拡張するための方法の一例としての実施形態の概要をより詳細に示す流れ図である。
【図２２】本発明によるトポロジを入力し、図２０の文脈自由文法を表す有限状態オートマトンをオンザフライで拡張するための方法の一例としての実施形態の概要をより詳細に示す流れ図である。
【図２３】本発明による図２０の文脈自由文法を表す依存関係グラフを生成するための方法の一例としての実施形態の概要をより詳細に示す流れ図である。
【図２４】本発明による図２０の文脈自由文法を表す依存関係グラフを生成するための方法の一例としての実施形態の概要をより詳細に示す流れ図である。
【図２５】本発明による図２０の文脈自由文法を表す強く結び付いた構成要素を判定するための方法の一例としての実施形態の概要をより詳細に示す流れ図である。
【図２６】本発明による図２０の文脈自由文法を表す強く結び付いた構成要素を判定するための方法の一例としての実施形態の概要をより詳細に示す流れ図である。
【図２７】本発明による図２５および２６の強く結び付いた構成要素を表す有限状態オートマトンを生成するための方法の一例としての実施形態の概要をより詳細に示す流れ図である。
【図２８】本発明による図２５および２６の強く結び付いた構成要素を表す有限状態オートマトンを生成するための方法の一例としての実施形態の概要をより詳細に示す流れ図である。
【図２９】本発明による図２５および２６の強く結び付いた構成要素を表す有限状態オートマトンを生成するための方法の一例としての実施形態の概要をより詳細に示す流れ図である。
【図３０】本発明による図２５および２６の強く結び付いた構成要素を表す有限状態オートマトンを生成するための方法の一例としての実施形態の概要をより詳細に示す流れ図である。
【図３１】本発明による文法−有限状態オートマトン生成システムの一例としての実施形態の概要を示すブロック図である。
【図１】
2004004521.tif 000003
【図２】
2004004521.tif 000004
【図３】
2004004521.tif 000005
【図４】
2004004521.tif 000006
【図５】
2004004521.tif 000007
【図６】
2004004521.tif 000008
【図７】
2004004521.tif 000009
【図８】
2004004521.tif 000010
【図９】
2004004521.tif 000011
【図１０】
2004004521.tif 000012
【図１１】
2004004521.tif 000013
【図１２】
2004004521.tif 000014
【図１３】
2004004521.tif 000015
【図１４】
2004004521.tif 000016
【図１５】
2004004521.tif 000017
【図１６】
2004004521.tif 000018
【図１７】
2004004521.tif 000019
【図１８】
2004004521.tif 000020
【図１９】
2004004521.tif 000021
【図２０】
2004004521.tif 000022
【図２１】
2004004521.tif 000023
【図２２】
2004004521.tif 000024
【図２３】
2004004521.tif 000025
【図２４】
2004004521.tif 000026
【図２５】
2004004521.tif 000027
【図２６】
2004004521.tif 000028
【図２７】
2004004521.tif 000029
【図２８】
2004004521.tif 000030
【図２９】
2004004521.tif 000031
【図３０】
2004004521.tif 000032
【図３１】
2004004521.tif 000033