(57)【特許請求の範囲】
【請求項１】
１または複数の有限状態オートマトン( 以下、FSAと記す)の状態数を最小化する状態数最小化部と、
該状態数最小化部で最小化された１または複数のメインFSAから等価な部分FSAを抽出し、該等価な部分FSAのシンボルを用いて表した１または複数のメインFSAと該等価な部分FSAとに分割するFSA分割部とを具備し、
該FSA分割部は、分割された複数のFSAの状態数の総和が、分割前のFSAの状態数の総和に比較して少なくなるFSAを生成することを特徴とするFSA作成装置。
【請求項２】
複数の有限状態オートマトン( 以下、FSAと記す)の状態数を最小化する状態数最小化部と、
該状態数最小化部で最小化された複数のメインFSAから等価な部分FSAを抽出し、該等価な部分FSAを用いて合成するFSA合成部とを具備し、
該FSA合成部は、合成されたFSAの状態数が、合成前の複数のFSAの状態数の総和に比較して少なくなるFSAを生成することを特徴とするFSA作成装置。
【請求項３】
１または複数の有限状態オートマトン( 以下、FSAと記す)の状態数を最小化する状態数最小化部と、
該状態数最小化部で最小化された１または複数のメインFSAから等価な部分FSAを抽出し、該等価な部分FSAのシンボルを用いて表した１または複数のメインFSAと該等価な部分FSAとに分割するFSA分割部と、
該FSA分割部で分割されたメインFSAまたは部分FSAを合成する合成部とを具備し、
合成されたFSAの状態数が、分割前のFSAの状態数の総和に比較して少なくなるFSAとなるようにしたことを特徴とするFSA作成装置。
【請求項４】
請求項１または３に記載のFSA作成装置において、
前記FSA分割部は、部分FSAからさらにその部分FSAを分割するようにしたことを特徴とするFSA作成装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、有限状態オートマトン作成装置(Finite State Automaton、 以下FSA作成装置と記す)に関し、特に、FSAの状態数を少なくすることにより、FSAを記憶するメモリ量を削減することが可能なFSA作成装置に関するものである。
【０００２】
【従来の技術】
従来は、図９に示すように、FSA格納部31に格納された１つのFSA(例えば、FSA−A)を状態数最小化部32で状態数を最小化した１つのFSAに変換し、出力FSA格納部33に１つのFSA(FSA−A')として格納していた。状態数最小化部32の最小化手法は、１つのFSAの最簡形を求めるアルゴリズム(例えば、“オートマトン・言語理論” 2.4節 “有限状態オートマトンの最簡形”、本多波雄著、コロナ社)を用いて容易に実現することができる。
【０００３】
【発明が解決しようとする課題】
しかし、従来は、１つのFSAにおける冗長な状態遷移を前記状態数最小化部32で取り除いて１つのFSAを作成することに留まっていたため、１つのFSAを複数のFSAに分割することによりFSAの状態数をさらに減らすこと、あるいは、複数のFSAを合成することにより、複数のFSAの総状態数を減らすことはできなかった。
【０００４】
本発明は、前記した従来技術に鑑みてなされたものであり、その目的は、FSAの分割、または／および合成により、FSAの状態数の総和を削減し、状態数の削減によってFSAの記憶に係るメモリ量を削減することができるFSA作成装置を提供することにある。
【０００５】
【課題を解決するための手段】
前記した目的を達成するために、本発明は、１または複数の有限状態オートマトン( 以下、FSAと記す)の状態数を最小化する状態数最小化部と、該状態数最小化部で最小化された１または複数のメインFSAから等価な部分FSAを抽出し、該等価な部分FSAのシンボルを用いて表した１または複数のメインFSAと該等価な部分FSAとに分割するFSA分割部とを具備し、該FSA分割部は、分割された複数のFSAの状態数の総和が、分割前のFSAの状態数の総和に比較して少なくなるFSAを生成するようにした点に第１の特徴がある。
【０００６】
また、  本発明は、前記状態数最小化部で最小化された複数のメインFSAから等価な部分FSAを抽出し、該等価な部分FSAを用いて合成するFSA合成部を具備し、該FSA合成部は、合成されたFSAの状態数が、合成前の複数のFSAの状態数の総和に比較して少なくなるFSAを生成するようにした点に第２の特徴がある。
【０００７】
前記第１、第２の特徴によれば、FSAの状態数を従来のFSA作成装置によるものより削減することができるようになり、FSAの記憶に係るメモリ量を削減することができるようになる。
【０００８】
【発明の実施の形態】
以下に、本発明を図面を参照して説明する。図１は、本発明の一実施形態の概略の構成を示すブロック図である。
【０００９】
図１の実施形態は、複数のFSA（FSA−A1〜An）を格納しているFSA格納部１と、状態数最小化部２と、FSA分割部３と、出力FSA格納部４とから構成されている。
【００１０】
次に、本実施形態の動作を説明する。まず、従来手法により、FSA格納部1に格納されている全てのFSAについて、状態数最小化部２で各FSAの状態数を最小化する。続いてFSA分割部３で各FSAに対して1つのFSAを複数のFSAに分割する処理を施す。例えば、図２に示されている状態１から状態１８に至る１つのFSA（main１）から、等価な部分FSA、すなわち状態２から状態１６に至る部分FSAと状態３から状態１７に至る部分FSAを抽出する。そして、該部分FSAをFSA（main１）から分割し、該部分FSAを１つの状態遷移に置き換える。なお、FSAの等価性は、FSAの等価性を求めるアルゴリズム(例えば、“オートマトン・言語理論” 2.4節 “有限状態オートマトンの最簡形”、本多波雄著、コロナ社)によって容易に求めることができる。このことは、以下の例でも、同様である。
【００１１】
前記等価な部分FSAは(sub1)として分割し、(main1)の状態2と状態16との間を部分FSAを表すシンボルsub1に置き換える。同様に、(main1)の状態３と状態17との間を部分FSAを表すシンボルsub1に置き換える。そして、シンボルを置き換えたFSAを新たに(main2)とする。この操作によって、状態数18の１つのFSA(main1)は、状態数6のFSA(main2)と状態数8の部分FSA(sub1)に分割される。分割された2つのFSAの状態数の総和は14で、分割前のFSA(状態数18)より、少なくなっている。
【００１２】
次に、図３を参照して本実施形態の他の具体例を説明する。図3は、複数のFSAから等価な複数の部分FSAを分割する例を示す。図３では、FSA(main1)の状態１から状態８に至る部分FSAと、FSA(main2)の状態１から状態８に至る部分FSAが等価である。そこで、部分FSAを(sub1)として分割し、(main1)の状態2と状態16との間を部分FSAを表すシンボルsub1に置き換え、新たにFSA(main3)とする。同様に、(main2)の状態１と状態８との間を部分FSAを表すシンボルsub1に置き換え、新たにFSA(main4)とする。この操作によって、２つのFSA(main1とmain2)の状態数の和は18であるが、分割されたFSA(main3とmain4とsub1)の状態数の和は14となり、分割前の状態数より少なくなっている。なお、FSA分割部は分割後のFSAの状態数の総和を分割前の状態数の総和より少なくすることが目的であるから、分割操作によって状態数が減少しないような場合は、必ずしも分割操作を行う必要はない。
【００１３】
次に、本発明の第２実施形態を図４を参照して説明する。この実施形態は、FSA合成部５で複数のFSAを１つのFSAに合成することにより状態数を減らすようにしたものである。
【００１４】
FSA合成部５は、図５に示すように、２つ以上のFSAの状態遷移を合成することによって、状態数の総和が減少することが期待される場合、FSA合成によって、２つ以上のFSAを1つのFSAに合成する。FSA合成によって状態数の総和が削減可能かどうかは実際に任意のFSAの組み合わせにおいて、合成操作を行い、合成前後の状態数の総和を比較することで実現することができる。
【００１５】
図５は、２つのFSA(main1とmain2)を合成して、1つのFSA(main3)を生成する例を示す。図５では、２つのFSA(main1とmain2)を合成すると1つのFSA(main3)が得られる。この操作によって、２つのFSA(main1とmain2)の状態数の和は８であるが、合成されたFSA(main3)の状態数は5となり、合成前の状態数より少なくなっている。なお、FSA合成部は合成後のFSAの状態数の総和を合成前の状態数の総和より少なくすることが目的であるから、合成操作によって状態数が減少しないような場合は、必ずしも合成操作を行う必要はない。
【００１６】
次に、本発明の第３実施形態を図６を参照して説明する。この実施形態は、FSA分割部３で分割することにより状態数を減らしたFSAをFSA合成部５に入れて合成することにより、さらに状態数を減らすようにしたものである。
【００１７】
次に、図７を参照して、図１または図６のFSA分割部３の処理フローの一例を説明する。まず、全てのFSAについて、最も状態数の大きな部分FSAを抽出する(ステップS1)。部分FSAが抽出できたかどうかをチェックし(ステップS2)、部分FSAが存在すれば仮に部分FSA分割処理を行う(ステップS3)。次に、部分FSA分割により状態数が減少したかどうかチェックし(ステップS4)、状態数が減少する場合は部分FSAをFSAから分割する(ステップS5)。この操作を、部分FSAの抽出に失敗するか(ステップS2の判定が否定)、部分FSAの分割により状態数が減少しなくなる(ステップS4の判定が否定)まで繰り返す。
【００１８】
次に、図８を参照して、図４または図６のFSA合成部５の処理フローの一例を説明する。まず、全てのFSAについて、任意の２つのFSAを選択する(ステップS11)。選択された２つのFSAに対して仮にFSA合成処理を行う(ステップS12)。次に、FSA合成により状態数が減少したかどうかチェックし(ステップS13)、状態数が減少する場合はFSAを合成する(ステップS14)。この操作を、全てのFSAの組み合わせについてチェックするまで繰り返す(ステップS15)。
【００１９】
以上、本発明を好適な実施形態により説明したが、本発明は該実施形態に限定されることなく、本発明の趣旨に属する種々の変形も、本発明の範囲内であることは明らかである。
【００２０】
【発明の効果】
以上の説明から明らかなように、本発明によれば、FSAの分割および／または合成により、FSAの状態数の総和を削減することができるという効果がある。また、この状態数の削減によって、FSAの記憶に係るメモリ量を削減することができるという効果がある。
【図面の簡単な説明】
【図１】  本発明の第１実施形態の概略の構成を示すブロック図である。
【図２】  本発明の第１実施形態の一具体例の説明図である。
【図３】  本発明の第１実施形態の他の具体例の説明図である。
【図４】  本発明の第２実施形態の概略の構成を示すブロック図である。
【図５】  本発明の第２実施形態の一具体例の説明図である。
【図６】  本発明の第３実施形態の概略の構成を示すブロック図である。
【図７】  前記第１実施形態の動作を示すフローチャートである。
【図８】  前記第２実施形態の動作を示すフローチャートである。
【図９】  従来装置の概略の構成を示すブロック図である。
【符号の説明】
１・・・FSA格納部、２・・・状態数最小化部、３・・・FSA分割部、４・・・出力FSA格納部、５・・・FSA合成部。
【図１】
0003827067.tif 000002
【図２】
0003827067.tif 000003
【図３】
0003827067.tif 000004
【図４】
0003827067.tif 000005
【図５】
0003827067.tif 000006
【図６】
0003827067.tif 000007
【図７】
0003827067.tif 000008
【図８】
0003827067.tif 000009
【図９】
0003827067.tif 000010