JPH1124902A

JPH1124902A - 状態遷移図合成装置及び状態遷移図合成方法

Info

Publication number: JPH1124902A
Application number: JP18721397A
Authority: JP
Inventors: Junji Yamada; 潤二山田; Yoichi Iwabuchi; 洋一岩渕; Toshio Yabe; 俊夫矢部; Masahiro Ogawara; 将広大河原
Original assignee: Canon Inc
Current assignee: Canon Inc
Priority date: 1997-06-30
Filing date: 1997-06-30
Publication date: 1999-01-29

Abstract

(57)【要約】【課題】あるオブジェクトに対して作成された全ての
状態遷移図を自動合成して１つの状態遷移図を作成する
ことができる状態遷移図合成装置を提供する。【解決手段】１つの対象物に対して幾つかの側面から
記述された複数の状態遷移図を格納する状態遷移図格納
部Ｅ５と、状態遷移図格納部Ｅ５に格納された状態遷移
図の中から任意の２つの状態遷移図を取り出し、その２
つの状態遷移図を自動合成して１つの状態遷移図にする
状態遷移図自動合成部Ｅ６とを備えた。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、システムの分析・
設計を行う際に、各対象物のライフサイクルとして作成
した状態遷移図を合成する状態遷移図合成装置、及び状
態遷移図合成方法に関する。

【０００２】

【従来の技術】例えばオブジェクト指向設計などにおい
て、システムの分析・設計を行なうに際し、複数のイベ
ントシーケンス図を記述し、その後、記述したした複数
のイベントシーケンス図の情報を基に各オブジェクトの
状態遷移図を作成する（オブジェクト指向方法論ＯＭＴ
（Ｊ，ランボー著、トッパン社）など参照）。従来で
は、この一連の作業のうち、１つ１つのイベントシーケ
ンスを基にそれぞれ１つずつの状態遷移図が作成された
時に、あるオブジェクトに対して作成された全ての状態
遷移図を合成して１つの状態遷移図を作成する作業は、
人の経験とカンによる、手作業で行なわれていた。

【０００３】また、複数のオブジェクトを合成して１つ
のタスク（プログラムの実行単位）を作り上げる時など
に、各オブジェクト毎に記述されたそれぞれの状態遷移
図を合成して、タスクとしての１つの状態遷移図を作成
する作業についても、人の経験とカンによる、手作業で
行なわれていた。

【０００４】イベントシーケンス図から状態遷移図を作
成する方式に関しては、「オブジェクト指向分析支援装
置（特開平６−１７５８３７）」があるが、これは、１
枚のイベントシーケンス図に対して、１つの状態遷移図
を自動生成することはできるが、生成した複数の状態遷
移図を合成して、１つの状態遷移図を自動的に作成する
ことはできない。

【０００５】また、「オブジェクト指向分折・設計支援
システム（特開平６−３４８４８２）」では、状態遷移
図の情報を解析してベトリネットに変換する方式が記載
されているが、複数の状態遷移図を合成して新たな状態
遷移図を作成するものではない。

【０００６】さらに、「オブジェクト指向分折・設計支
援装置（特開平６一１６８１０９）」では、状態遷移図
の情報を解析し、オブジュクト図に反映させるアルゴリ
ズムが記載されているが、複数の状態遷移図を合成して
新たな状態遷移図を作成するものではない。

【０００７】

【発明が解決しようとする課題】このような点から、上
記の各従来例では、例えば、１つ１つのイベントシーケ
ンスを基にそれぞれ１つずつの状態遷移図が作成された
時に、あるオブジェクトに対して作成された全ての状態
遷移図を合成して１つの状態遷移図を作成する場合や、
複数のオブジュクトを合成して１つのタスクを作り上げ
る時に各オブジェクト毎に記述されたそれぞれの状態遷
移図を合成して、タスクとしての１つの状態遷移図を作
成する場合などに、多大な労力と時間を要していた。

【０００８】また、人手によりこの作業を行なっている
ため、誤った合成を行なう危険もあった。

【０００９】本発明は上記従来の問題点に鑑み、あるオ
ブジェクトに対して作成された全ての状態遷移図を自動
合成して１つの状態遷移図を作成することができる状態
遷移図合成装置、及び状態遷移図合成方法を提供するこ
とを目的とする。また、各オブジェクト毎に記述された
それぞれの状態遷移図を自動合成して、タスクとしての
１つの状態遷移図を作成することできる状態遷移図合成
装置、及び状態遷移図合成方法を提供することを目的と
する。

【００１０】

【課題を解決するための手段】上記目的を達成するため
に、第１の発明は、１つの対象物に対して幾つかの側面
から記述された複数の状態遷移図を格納する状態遷移図
格納部と、前記状態遷移図格納部に格納された状態遷移
図の中から任意の２つの状態遷移図を取り出し、その２
つの状態遷移図を自動合成して１つの状態遷移図にする
状態遷移図自動合成部とを備えたものである。

【００１１】第２の発明では、上記第１の発明におい
て、前記状態遷移図自動合成部は、前記２つの状態遷移
図を構成する項目である、現在の状態、入力イベント、
アクション、及び次の状態の組からなる各遷移レコード
について、前記現在の状態、前記入力イベント、及び前
記アクションが等しい遷移レコードは同じ遷移であると
判断するものである。

【００１２】第３の発明では、上記第１の発明におい
て、前記状態遷移図自動合成部は、前記２つの状態遷移
図を構成する項目である、現在の状態、入力イベント、
アクション、次の状態の組からなる各遷移レコードにつ
いて、前記現在の状態及び前記入力イベントが等しいに
もかかわらず、前記アクションが異なる遷移レコード
は、整合性エラーであると判断するものである。

【００１３】第４の発明では、上記第１の発明におい
て、前記状態遷移図自動合成部は、前記２つの状態遷移
図の中で共通の状態を外部より指定したとき、またはそ
の指定がないときは該２つの状態遷移図の初期状態は共
通であると判断し、その状態を起点として合成作業を始
めるものである。

【００１４】第５の発明では、複数の対象物の各々に対
してそれぞれ１枚ずつ記述された状態遷移図を格納する
状態遷移図格納部と、前記状態遷移図格納部に格納され
た状態遷移図の中から任意の２つの状態遷移図を第１及
び第２の状態遷移図として取り出し、その第１と第２の
状態遷移図を自動合成して１つの状態遷移図にする状態
遷移図自動合成部とを備えたものである。

【００１５】第６の発明では、上記第５の発明におい
て、前記状態遷移図自動合成部は、前記第１の状態遷移
図中の状態と前記第２の状態遷移図中の状態との全ての
組み合わせを作成し、それを合成後の状態遷移図の全て
の状態とするものである。

【００１６】第７の発明では、上記第５の発明におい
て、前記第１及び第２の状態遷移図は、現在の状態、入
力イベント、アクション、及び次の状態の各項目から構
成されるものである。

【００１７】第８の発明では、上記第７の発明におい
て、前記状態遷移図自動合成部は、前記第１の状態遷移
図中のイベントの集合と前記第２の状態遷移図中のイベ
ントの集合との論理和を作り、それを合成後の状態遷移
図中に出てくる全てのイベントであるとしたものであ
る。

【００１８】第９の発明では、上記第７の発明におい
て、前記状態遷移図自動合成部は、各対象物の現在の状
態をデータとして持ち、各対象物の状態遷移図データを
個別に保持したままで、入力イベントと各対象物の現在
の状態データとを基に、前記各対象物の状態遷移図デー
タを動的に検索し、イベントに対するアクションと次の
状態を計算する唯一のアルゴリズムを持つことにより、
合成する対象である第１と第２の状態遷移図自体を合成
するのではなく、見かけ上で状態遷移図の合成を行うも
のである。

【００１９】第１０の発明では、１つの対象物に対して
幾つかの側面から記述された複数の状態遷移図を格納す
る状態遷移図格納処理と、前記状態遷移図格納処理によ
って格納された状態遷移図の中から任意の２つの状態遷
移図を取り出し、その２つの状態遷移図を自動合成して
１つの状態遷移図にする状態遷移図自動合成処理とを実
行するものである。

【００２０】第１１の発明では、上記第１０の発明にお
いて、前記状態遷移図自動合成処理は、前記２つの状態
遷移図を構成する項目である、現在の状態、入力イベン
ト、アクション、及び次の状態の組からなる各遷移レコ
ードについて、前記現在の状態、前記入力イベント、及
び前記アクションが等しい遷移レコードは同じ遷移であ
ると判断するものである。

【００２１】第１２の発明では、上記第１０の発明にお
いて、前記状態遷移図自動合成処理は、前記２つの状態
遷移図を構成する項目である、現在の状態、入力イベン
ト、アクション、次の状態の組からなる各遷移レコード
について、前記現在の状態及び前記入力イベントが等し
いにもかかわらず、前記アクションが異なる遷移レコー
ドは、整合性エラーであると判断するものである。

【００２２】第１３の発明では、上記第１０の発明にお
いて、前記状態遷移図自動合成処理は、前記２つの状態
遷移図の中で共通の状態を外部より指定したとき、また
はその指定がないときは該２つの状態遷移図の初期状態
は共通であると判断し、その状態を起点として合成作業
を始めるものである。

【００２３】第１４の発明では、複数の対象物の各々に
対してそれぞれ１枚ずつ記述された状態遷移図を格納す
る状態遷移図格納処理と、前記状態遷移図格納処理によ
って格納された状態遷移図の中から任意の２つの状態遷
移図を第１及び第２の状態遷移図として取り出し、その
第１と第２の状態遷移図を自動合成して１つの状態遷移
図にする状態遷移図自動合成処理とを実行するものであ
る。

【００２４】第１５の発明では、上記第１４の発明にお
いて、前記状態遷移図自動合成処理は、前記第１の状態
遷移図中の状態と前記第２の状態遷移図中の状態との全
ての組み合わせを作成し、それを合成後の状態遷移図の
全ての状態とするものである。

【００２５】第１６の発明では、上記第１４の発明にお
いて、前記第１及び第２の状態遷移図は、現在の状態、
入力イベント、アクション、及び次の状態の各項目から
構成されるものである。

【００２６】第１７の発明では、上記第１６の発明にお
いて、前記状態遷移図自動合成処理は、前記第１の状態
遷移図中のイベントの集合と前記第２の状態遷移図中の
イベントの集合との論理和を作り、それを合成後の状態
遷移図中に出てくる全てのイベントであるとしたもので
ある。

【００２７】第１８の発明では、上記第１６の発明にお
いて、前記状態遷移図自動合成処理は、各対象物の現在
の状態をデータとして持ち、各対象物の状態遷移図デー
タを個別に保持したままで、入力イベントと各対象物の
現在の状態データとを基に、前記各対象物の状態遷移図
データを動的に検索し、イベントに対するアクションと
次の状態を計算する唯一のアルゴリズムを持つことによ
り、合成する対象である第１と第２の状態遷移図自体を
合成するのではなく、見かけ上で状態遷移図の合成を行
うものである。

【００２８】

【発明の実施の形態】以下、図面を参照して本発明の実
施の形態を説明する。

【００２９】図１は、本発明の第１実施形態に係る状態
遷移図合成装置の概略構成を示すブロック図である。

【００３０】この状態遷移図合成装置は、ＣＰＵ１、バ
ス２、ＲＯＭ３、ＲＡＭ４、入力インターフェース５、
入力デバイス６、出力インターフェース７、出力デバイ
ス８、外部記憶装置インターフェース９、及び外部記憶
デバイス１０から構成されている。

【００３１】図２は、本発明の状態遷移図合成装置の状
態遷移図自動合成機能を実現するための情報処理システ
ムの機能ブロック図である。

【００３２】Ｅ１はコンピュータ端末である。Ｅ２は図
面情報などの入出力部であり、イベントシーケンス格納
部Ｅ３に格納する情報を作る。このイベントシーケンス
格納部Ｅ３に、入出力部Ｅ２を通じてユーザーが入力し
たイベントシーケンスが格納される。Ｅ４は、状態遷移
図作成部であり、イベントシーケンス格納部Ｅ３から状
態遷移図を作る。Ｅ５は、作成された状態遷移図を格納
する状態遷移図格納部である。Ｅ６は、複数の状態遷移
図を合成する状態遷移図自動合成部であり、状態遷移図
格納部Ｅ５の中の複数の状態遷移図を基に状態遷移図を
合成し、合成後の状態遷移図を状態遷移図格納部Ｅ５に
格納する。

【００３３】図３は、図２の情報処理システムにおける
状態遷移図自動合成処理を示すフローチャートである。

【００３４】ステップＳ１では、イベントシーケンス
と、その繰り返し情報をユーザーインターフェースの機
能を利用して作成する。ステップＳ２では、ステップＳ
１で入力された情報を基に状態遷移図を作成する。ステ
ップＳ３では、状態遷移図格納部Ｅ５の中の複数の状態
遷移図を基に状態遷移図を合成する。その詳細のアルゴ
リズムは図４乃至図７に記述する。

【００３５】図４乃至図７は、図３のステップＳ３の詳
細アルゴリズムであり、状態遷移図格納部Ｅ５の中の複
数の状態遷移図を基に状態遷移図を合成する。図４乃至
図７のアルゴリズムを説明する前に、図４のアルゴリズ
ムの入力となるデータ構造に関して説明をする。

【００３６】図８（ａ），（ｂ）は、合成する状態遷移
の一例を示す図であり、同図（ａ）が状態遷移テーブ
ル、同図（ｂ）が状態遷移図である。また、図９
（ａ），（ｂ）も同様に合成する状態遷移の他の例を示
す図である。ここで、これら状態遷移テーブルは状態遷
移図と等価な情報を持っている。以後、本文では、「状
態遷移図」と「状態遷移テーブル」は、同じ意味の言葉
として用いることにする。テーブルの中の項目として
は、「現在の状態」、「入力イベント」、「アクショ
ン」、「次の状態」項目がある。

【００３７】図１０（ａ），（ｂ）は、図８及び図９の
状態遷移図を基に、図４乃至図７のアルゴリズムを用い
て合成された後の状態遷移を示す図であり、同図（ａ）
が状態遷移テーブル、同図（ｂ）が状態遷移図である。

【００３８】この図１０（ａ）の状態遷移テーブルは、
図１０（ｂ）の状態遷移図と等価な情報を持っている。
テーブルの中の項目としては、「現在の状態」、「入力
イベント」、「アクション」、「次の状態」項目があ
る。

【００３９】図４乃至図７のアルゴリズムの説明に戻
る。まずはアルゴリズムの概要について述べる。図４乃
至図７は、図３のステップＳ３の詳細アルゴリズムであ
り、複数の状態遷移テーブルを論理的に矛盾なく合成し
て１つの状態遷移テーブルにしている。ここでは、合成
する状態遷移テーブルとして、Ｘ、Ｙとしている。ま
た、合成した結果の状態遷移テーブルをＺと呼ぶ。２つ
の状態遷移図を構成する、「現在の状態」、「入力イベ
ント」、「アクション」、「次の状態」の組からなる各
遷移レコードについて「現在の状態」、「入力イベン
ト」、「アクション」が等しいレコードは同じ遷移であ
ると判断してＺに登録し、「現在の状態」、「入力イベ
ント」、が等しいにもかかわらず、「アクション」が異
なるレコードは整合性エラーであると判断する。

【００４０】また、ある遷移レコードについて「現在の
状態」、「入力イベント」、「アクション」が等しいレ
コードが他に存在しなければ、その遷移レコードをＺに
登録する。その手順の一例を以下に示す。なお、手順に
ついては、上記の内容が実行できれば、図４乃至図７の
ものに対して、多少順序が入れ替わっても構わない。

【００４１】具体的には、図４に示すステップＳ１０で
は、Ｚの初期状態を決定している。ステップＳ１０の中
では、図５に示すように、ステップＳ１１で、ユーザー
にＸ，Ｙの中から同じ意味の状態を指定してもらい、ス
テップＳ１２で、指定があれば、ステップＳ１３に行
き、Ｘについて指定された状態名をＺの現在の状態とす
る。そして、もう片方のＹの状態遷移テーブルの「現在
の状態」と「次の状態」項目の中で、Ｙについて指定さ
れた状態名と同じラベルを持つ状態名を、全て、Ｘにつ
いて指定された状態名で置き換える。もし、指定がない
場合には、ステップＳ１４に行き、片方Ｘの初期状態名
をＺの現在の状態とする。そして、もう片方のＹの状態
遷移テーブルの「現在の状態」と「次の状態」項目の中
で、Ｙの中での初期状態名と同じラベルを持つ状態名を
全てＸの初期状態名で置き換える。以上の操作は、Ｘと
Ｙが逆になっていても構わない。

【００４２】図４に戻り、ステップＳ２１からステップ
Ｓ６１の間のアルゴリズムは、Ｚの状態遷移図の中で、
ある状態の先のイベント、アクション、次の状態に関し
て、末探索である１つの状態について、その状態を現在
の状態としたときの状態遷移レコードを計算して、登録
するアルゴリズムが書かれている。

【００４３】ステップＳ２１では、Ｘ、Ｙの中で現在の
状態がＺの現在の状態に等しいレコードをすべて取り出
してくる。ステップＳ２３では、ステップＳ２１で取り
出したあるレコードＸ１に対して、今取り出してきたレ
コード群の中にイベントが同じレコードが他に存在する
かどうかを調べる。もし、存在すれば、ステップＳ２４
で更にアクションも等しいかどうかを調べる。

【００４４】アクションも等しければ同一遷移であると
判断し、状態遷移テーブルＺにそのレコードＸ１のみを
登録する。状態遷移テーブルＺにレコードＸ１を登録す
る方法にはいくつかあるが、要は、「現在の状態」、
「入力イベント］、「アクション」、「次の状態」の組
を登録することであり、図６に示すステップＳ３１から
ステップＳ３５の手順には固執しない。例えば、この登
録の具体的な内容については、ステップＳ３１からステ
ップＳ３５で説明する。

【００４５】ステップＳ３１では、Ｚ中の次の状態番号
を取得している。取得方法については、例えば、Ｘ１の
次の状態名がＺ中に存在しないときは、Ｘ、Ｙ、Ｚ中の
状態番号とは別の番号を獲得し、Ｎｅｘｔ−ｓｔａｔｅ
に代入する。これが後にＺ中の新しい状態番号となる。

【００４６】その後、ステップＳ３２で、Ｚにレコード
（ＲＥＣ）の登録をする。即ち、（１）ＲＥＣ．現在の
状態←Ｚ．現在の状態、（２）ＲＥＣ．入力イベント←
Ｘ１．入力イベント、（３）ＲＥＣ．アクション←Ｘ
１．アクション、（４）ＲＥＣ．次の状態←Ｎｅｘｔ−
ｓｔａｔｅ、と代入する。

【００４７】ステップＳ３３では、Ｚの次の状態リスト
にＮｅｘｔ−ｓｔａｔｅを追加する。ステップＳ３３を
実行するタイミングについてもステップＳ３１からステ
ップＳ６１の間であればどこでもよい。

【００４８】ステップＳ３４では、状態番号の整合性を
とる。即ち、Ｘ１の属する状態遷移テーブルの中で［Ｘ
１．次の状態］と等しい値を持つ状態を全て［Ｎｅｘｔ
−ｓｔａｔｅ］にする。ステップＳ３４の処理はステッ
プＳ３１の処理の後であれば処理をする場所はどこにあ
ってもよい。ステップＳ３５では、登録しなかった方の
レコードが所属する状態遷移テーブルの中で、登録しな
かった方のレコードの次の状態項目の値と等しい値を持
つ状態をすべて［Ｎｅｘｔ−ｓｔａｔｅ］にする。

【００４９】図４のステップＳ４０に遷移したときに
は、２つの状態遷移図を構成する、「現在の状態」、
「入力イベント」、「アクション」、「次の状態」の組
からなる各遷移レコードについて、「現在の状態」と
「入力イベント」が等しいにもかかわらず、「アクショ
ン」が異なるレコードは、整合性エラーであると判断
し、警告を出す。

【００５０】ステップＳ２３で、ステップＳ２１で取り
出したあるレコードＸ１に対して、今取り出してきたレ
コード群の中に、イベントの同じレコードが他に存在し
なければＸ１をＺに登録する。状態遷移テーブルＺにレ
コードＺを登録する方法にはいくつかあるが、要は、
「現在の状態」、「入力イベント」、「アクション」、
「次の状態」の組を登録することであり、ステップＳ５
１からステップＳ５４の手順には固執しない。例えば、
図７に示すステップＳ５１からステップＳ５４までの登
録作業は、ステップＳ３１からステップＳ３４までの作
業と同様である。例えば、この登録の具体的な内容につ
いては、以下に述べる。

【００５１】ステップＳ５１では、Ｚ中の次の状態番号
を取得している。取得方法については、例えば、Ｘ１の
次の状態名がＺ中に存在しないときは、Ｘ、Ｙ、Ｚ中の
状態番号とは別の番号を獲得し、Ｎｅｘｔ−ｓｔａｔｅ
に代入する。これが後にＺ中の新しい状態番号となる。
その後、ステップＳ５２で、Ｚにレコード（ＲＥＣ）の
登録をする。即ち、（１）ＲＥＣ．現在の状態←Ｚ．現
在の状態、（２）ＲＥＣ．入力イベント←Ｘ１．入力イ
ベント、（３）ＲＥＣ．アクション←Ｘ１．アクショ
ン、（４）ＲＥＣ．次の状態←Ｎｅｘｔ−ｓｔａｔｅ、
と代入する。

【００５２】ステップＳ５３では、Ｚの次の状態リスト
にＮｅｘｔ−ｓｔａｔｅを追加する。ステップＳ５３を
実行するタイミングについてもステップＳ５１からステ
ップＳ６１の間であればどこでもよい。ステップＳ５４
では、状態番号の整合性をとる。即ち、Ｘ１の属する状
態遷移テーブルの中で［Ｘ１．次の状態］と等しい値を
持つ状態を全て［Ｎｅｘｔ−ｓｔａｔｅ］にする。な
お、ステップＳ５４の処理はステップＳ５１の処理の後
であれば処理をする場所はどこにあってもよい。

【００５３】ステップＳ６１では、ステップＳ２３で取
り出してきた全てのレコードについて処理をしたかどう
かを判断し、この時、Ｚの次の状態リストが空の場合
は、Ｚの現在の状態に対する合成処理は終了となる。ま
だ処理をしていないレコードがあればステップＳ２３に
戻る。

【００５４】処理をしていないレコードがもうなくなっ
た場合には、ステップＳ６２でＺの次の状態リストから
１つ未探索の状態を取り出してきてＺの現在の状態と
し、ステップＳ２１に戻る。ステップＳ６２において、
未探索の状態を取り出して来る方法については、リスト
の先頭から取り出す、リストの後端から取り出す、任意
の１要素を取り出すなどのいくつかのやり方がある。ま
た、Ｚの次の状態リストをステップＳ３１及びステップ
Ｓ５１で動的に計算しているが、あらかじめ、Ｘ、Ｙの
全ての状態の組み合わせを考えてＺの状態リストを作っ
ておくというやり方もある。

【００５５】Ｚの次の状態リストが空であるときは（ス
テップＳ６３）、ステップＳ６４では、見栄えを良くす
るために、空いた状態番号を分を前に詰めて、テーブル
全体を状態番号順にソートする。場合によってはステッ
プＳ６４はなくてもよい。

【００５６】次に、本発明の第２実施形態を説明する。

【００５７】本実施形態は、図３に示すステップＳ３の
詳細アルゴリズムとして、上記図４乃至図７のアルゴリ
ズムの別の例を示すものである。

【００５８】オブジェクト指向分析の結果を基にリアル
タイムＯＳ（技術評論社「プロセッサ」１９８７年１１
月号など参照）を用いてマルテタスクのプログラムで実
装する場合に、複数のオブジェクトをまとめて１つのタ
スクとするという作業を行なうが、本発明は、この作業
を自動化するときにも適用できる。

【００５９】具体的には、先の第１実施形態では図８及
び図９の状態遷移図は、同一のオブジェクトのものであ
ると仮定していたが、これを別々のオブジェクトの状態
遷移図と見ることによって、複数のオブジェクトの状態
遷移図を合成した１つのタスクとしての状態遷移図を自
動合成することもできる。

【００６０】または、２つの状態遷移図を合成した状態
遷移図を作るにあたっては、合成する各オブジェクトの
状態遷移図の全ての状態の組み合わせを考慮した状態遷
移図の合成を行なう方式の他の実現手段も考えられる。
それを以下に説明する。

【００６１】図１１及び図１２は、本発明の第２実施形
態に係る図３のステップＳ３の詳細アルゴリズムを示す
フローチャートである。この中では、状態遷移図Ｐ１と
Ｐ２を合成して、状態遷移図Ｚを作る場合として記され
ている。

【００６２】ステップＳ８１では、現在のイベント、ア
クションリスト、残りイベントリスト、全イベントリス
ト、全複合状態リストを空に初期化している。ステップ
Ｓ８２では、Ｐ１とＰ２の中に出てくる全ての状態の組
み合わせのリストを作り、全複合状態リストとする。ス
テップＳ８３では、Ｐ１とＰ２の中に出てくる全てのイ
ベントの論理和からなるリストを作り、全イベントリス
トとする。ステップＳ８４では、全複合状態リストを残
り複合状態リストに代入する（初期化）。

【００６３】ステップＳ８１からステップＳ８４の手順
に関しては、順序は重要ではなく、どの順番でも構わな
い。または、ステップＳ８２及びステップＳ８３は作業
を始める前に一気に作っているが、合成作業を行なう過
程で１つ１つ動的に抽出してもよい。ステップＳ８５で
は、残り複合状態リストが空かどうかを判断している。
空の場合は終了する。空でない場合はステップＳ８６へ
行く。この、残り複合状態リストが空かどうかを判断す
る部分は、アルゴリズム中の何処かにあればよく、例え
ば、アルゴリズムの最後にあってもよい。

【００６４】ステップＳ８６では、現在の複合状態、Ｐ
１の現在の状態、及びＰ２の現在の状態を初期化してい
る。ステップＳ８７では、全イベントリストを残りのイ
ベントリストに代入している。ステップＳ８８では、残
りのイベントリストが空かどうかを判断し、空であれば
ステップＳ８５へ、空でなければステップＳ９０へ移
る。

【００６５】ステップＳ９０では、要はＺ中のある（複
合）状態にいるときに、あるイベントが来た場合に状態
遷移レコードの作成と登録の作業を行なっており、その
作業ができるのであれば、図１２に示すステップＳ９１
からステップＳ９６までの手順の通りでなくても、多
少、制御の手順が入れ替わってもよい。

【００６６】ステップＳ９１では、残りのイベントリス
トから１つ取り出して、現在の入力イベントに入れ、残
りのイベントリストから現在のイベントを削除する。ま
た、アクションリストを空に初期化している。

【００６７】ステップＳ９２及びステップＳ９３では、
テーブルＰ１に対する検索処理を行う。この検索処理
は、まずステップＳ９２で、Ｐ１の次の状態をＰ１の現
在の状態に代入（初期化）する。続くステップＳ９３で
は、Ｐ１の現在の状態と現在の入力イベントをキーにし
て状態遷移テーブルＰ１を検索し、そのレコードｐが存
在すれば、アクションリストにｐのアクションを登録
し、Ｐ１の次の状態にｐの次の状態を代入する。なお、
上記第ステップＳ９２の処理については、ステップＳ９
３の実行前であればどのタイミングで実行されてもよ
い。

【００６８】ステップＳ９４及びステップＳ９５は、テ
ーブルＰ２に対する検索処理である。この検索処理は、
まずステップＳ９４で、Ｐ２の次の状態をＰ２の現在の
状態に代入（初期化）する。続くステップＳ９５では、
Ｐ２の現在の状態と現在の入力イベントをキーにして状
態遷移テーブルＰ２を検索し、そのレコードｐが存在す
れば、アクションリストにＰのアクションを登録し、Ｐ
２の次の状態にｐの次の状態を代入する。なお、ステッ
プＳ９４の処理については、ステップＳ９５の実行前で
あればどのタイミングで実行されてもよい。また、ステ
ップＳ９２及びステップＳ９３と、ステップＳ９４及び
ステップＳ９５の処理は順序が入れ替わっていてもよ
い。

【００６９】ステップＳ９５では、現在の複合状態、現
在の入力イベント、アクションリスト、「Ｐ１の次の状
態とＰ２の次の状態の組み合わせに対応する複合状態」
の組を１つのレコードとして状態遷移テーブルＺに登録
し、ステップＳ８８に戻る。基本的には、まず、全ての
複合状態とイベントリストを求めて、その全ての組み合
わせに対して状態遷移レコードを計算していく過程があ
ればよく、例えば、ステップＳ８６及びステップＳ８７
がステップＳ８５の前にもあり、ステップＳ８８からス
テップＳ８５へ遷移する間にもあったとしてもよい。

【００７０】図１３（ａ），（ｂ）及び図１４（ａ），
（ｂ）は、本第２実施形態に係る合成する前の状態遷移
の例を示す図であり、同図（ａ）は状態遷移テーブルＰ
１であり、同図（ｂ）は状態遷移図である。なお、状態
遷移テーブルは状態遷移図と等価な情報を持っている。
テーブルの中の項目として、「現在の状態」、「イベン
ト］、「アクション」、「次の状態」項目がある。

【００７１】図１５は、本第２実施形態において全複合
状態リスト及び全イベントリストの例を示す図である。

【００７２】図１６は、図１３及び図１４の状態遷移図
を基に合成された後の状態遷移の例であり、同図（ａ）
は状態遷移テーブルＺであり、同図（ｂ）は状態遷移図
である。なお、状態遷移テーブルは状態遷移図と等価な
情報を持っている。テーブルの中の項目として、「現在
の状態」、「イベント」、「アクション」、及び「次の
状態」項目がある。

【００７３】次に、本発明の第３実施形態を説明する。

【００７４】本実施形態では、図３に示すステップＳ３
の詳細アルゴリズムとして、上記図４乃至図７のアルゴ
リズムの別の例を示すものである。

【００７５】上記第２実施形態と同様に、オブジェクト
指向分析の結果を基にリアルタイムＯＳを用いてマルテ
タスクのプログラムで実装する場合に、複数のオブジェ
クトをまとめて１つのタスクとするという作業を行う
が、本発明は、この作業を自動化するときにも適用でき
る。

【００７６】すなわち、本実施形態の装置は、状態遷移
図自体を合成するのではなく、各オブジェクトの現在の
状態をデータとして持ち、各オブジェクトの状態遷移図
データは個別に保持したままで、入力イベントと各オブ
ジェクトの現在の状態データを基に、各オブジェクトの
状態遷移図データを動的に検索し、イベントに対するア
クションと次の状態を計算することにより、見かけ上、
あたかも状態遷移図が合成されたかのように処理する。

【００７７】具体的には、全ての合成後のオブジェクト
に対しては、図１７の状態遷移図とする。各オブジュク
トの状態遷移図はそのままデータとして保存し、この他
にオブジェクト名と現在状態の組からなる図１８に示す
ようなテーブルを持つ。

【００７８】図１７において、ステップＳ１０１では、
合成後のオブジェクトに対して送られてくるイベントを
待つ。ステップＳ１０２では、図１８の中の全てのレコ
ードに対してステップＳ１０３からステップＳ１０６の
処理を行なったかどうかを判断し、まだ処理を行なって
いないレコードがある場合には、ステップＳ１０３に行
く。

【００７９】図１８の中の全てのレコードに対してステ
ップＳ１０３からステップＳ１０６の処理を行なった場
合には、ステップＳ１０１のイベント待ちの状態に戻
る。このステップＳ１０２の実行順序は、特にこの位置
でなければならないわけではなく、例えば、ステップＳ
１０６の後にあってもよい。ステップＳ１０３では、図
１８のようなオブジェクト名と現在状態の組からなるテ
ーブルから、１レコード取り出し、そのオブジェクトの
現在の状態を得る。これをｓｔａｔｅとする。

【００８０】ステップＳ１０４では、オブジェクトの識
別子（ＯｂｊｅｃｔＮａｍｅ）に対応する図８のよう
な状態遷移テーブルから、現在状態（ｓｔａｔｅ）と、
現在送られてきたイベントに対応するアクションと次の
状態を検索して得る。アクションをａｃｔｉｏｎに、次
の状態をｎｅｘｔ−ｓｔａｔｅに入れる。ステップＳ１
０５では、アクション（ａｃｔｉｏｎ）を実行する。

【００８１】ステップＳ１０６では、図１８のオブジェ
クト名と現在状態の組からなるテーブルに次の状態を記
録し、ステップＳ１０２に戻る。ステップＳ１０５とス
テップＳ１０６は手順が逆転していてもよい。

【００８２】

【発明の効果】以上詳述したように、第１の発明である
状態遷移図合成装置によれば、例えば、１つ１つのイベ
ントシーケンスを基にそれぞれ１つずつの状態遷移図が
作成された時に、ある対象物に対して作成された全ての
状態遷移図を自動合成して１つの状態遷移図を作成する
場合に、状態遷移図を自動合成することができるように
なり、そのための労力が大幅に削減できる。また、人手
によりこの作業を行なっていた場合に比べ、誤った合成
を行なうことがなくなるので合成アルゴリズムの信頼性
も向上する。

【００８３】第２の発明である状態遷移図合成装置によ
れば、上記第１の発明において、前記状態遷移図自動合
成部は、前記２つの状態遷移図を構成する項目である、
現在の状態、入力イベント、アクション、及び次の状態
の組からなる各遷移レコードについて、前記現在の状
態、前記入力イベント、及び前記アクションが等しい遷
移レコードは同じ遷移であると判断するようにしたの
で、簡易且つ的確に状態遷移図の自動合成を行うことが
可能になる。

【００８４】第３の発明である状態遷移図合成装置によ
れば、上記第１の発明において、前記状態遷移図自動合
成部は、前記２つの状態遷移図を構成する項目である、
現在の状態、入力イベント、アクション、次の状態の組
からなる各遷移レコードについて、前記現在の状態及び
前記入力イベントが等しいにもかかわらず、前記アクシ
ョンが異なる遷移レコードは、整合性エラーであると判
断するようにしたので、簡易且つ的確に状態遷移図の自
動合成を行うことが可能になる。

【００８５】第４の発明である状態遷移図合成装置によ
れば、上記第１の発明において、前記状態遷移図自動合
成部は、前記２つの状態遷移図の中で共通の状態を外部
より指定したとき、またはその指定がないときは該２つ
の状態遷移図の初期状態は共通であると判断し、その状
態を起点として合成作業を始めるようにしたので、簡易
且つ的確に状態遷移図の自動合成を行うことが可能にな
る。

【００８６】第５の発明である状態遷移図合成装置によ
れば、例えば、複数の対象物を合成して１つのタスク
（プログラムの実行単位）を作り上げる時に、各対象物
毎に記述されたそれぞれの状態遷移図を自動合成して、
タスクとしての１つの状態遷移図を作成する場合など
に、状態遷移図を自動合成することができるようにな
り、そのための労力が大幅に削減できる。また、人手に
よりこの作業を行なっていた場合に比べ、誤った合成を
行なうことがなくなるので合成アルゴリズムの信頼性も
向上する。

【００８７】第６の発明である状態遷移図合成装置によ
れば、上記第５の発明において、前記状態遷移図自動合
成部は、前記第１の状態遷移図中の状態と前記第２の状
態遷移図中の状態との全ての組み合わせを作成し、それ
を合成後の状態遷移図の全ての状態とするようにしたの
で、上記第５の発明において、簡易且つ的確に状態遷移
図の自動合成を行うことが可能になる。

【００８８】第７の発明である状態遷移図合成装置によ
れば、上記第５の発明において、前記第１及び第２の状
態遷移図は、現在の状態、入力イベント、アクション、
及び次の状態の各項目から構成されるので、これら各項
目について状態遷移図の自動合成を的確に行うことが可
能になる。

【００８９】第８の発明では、上記第７の発明におい
て、前記状態遷移図自動合成部は、前記第１の状態遷移
図中のイベントの集合と前記第２の状態遷移図中のイベ
ントの集合との論理和を作り、それを合成後の状態遷移
図中に出てくる全てのイベントであるとしたので、上記
第７の発明において、簡易且つ的確に状態遷移図の自動
合成を行うことが可能になる。

【００９０】第９の発明では、上記第７の発明におい
て、前記状態遷移図自動合成部は、各対象物の現在の状
態をデータとして持ち、各対象物の状態遷移図データを
個別に保持したままで、入力イベントと各対象物の現在
の状態データとを基に、前記各対象物の状態遷移図デー
タを動的に検索し、イベントに対するアクションと次の
状態を計算する唯一のアルゴリズムを持つことにより、
合成する対象である第１と第２の状態遷移図自体を合成
するのではなく、見かけ上で状態遷移図の合成を行うよ
うにしたので、上記第７の発明において、より簡易且つ
的確に状態遷移図の自動合成を行うことが可能になる。

【００９１】第１０の発明である状態遷移図合成方法に
よれば、上記第１の発明と同様の効果を奏する。

【００９２】第１１の発明である状態遷移図合成方法に
よれば、上記第１０の発明において、上記第２の発明と
同様の効果を奏する。

【００９３】第１２の発明である状態遷移図合成方法に
よれば、上記第１０の発明において、上記第３の発明と
同様の効果を奏する。

【００９４】第１３の発明である状態遷移図合成方法に
よれば、上記第１０の発明において、上記第４の発明と
同様の効果を奏する。

【００９５】第１４の発明である状態遷移図合成方法に
よれば、上記第５の発明と同様の効果を奏する。

【００９６】第１５の発明である状態遷移図合成方法に
よれば、上記第１４の発明において、上記第６の発明と
同様の効果を奏する。

【００９７】第１６の発明である状態遷移図合成方法に
よれば、上記第１４の発明において、上記第７の発明と
同様の効果を奏する。

【００９８】第１７の発明である状態遷移図合成方法に
よれば、上記第１６の発明において、上記第８の発明と
同様の効果を奏する。

【００９９】第１８の発明である状態遷移図合成方法に
よれば、上記第１６の発明において、上記第９の発明と
同様の効果を奏する。

【図面の簡単な説明】

【図１】本発明の第１実施形態に係る状態遷移図合成装
置の概略構成を示すブロック図である。

【図２】本発明の状態遷移図合成装置の状態遷移図自動
合成機能を実現するための情報処理システムの機能ブロ
ック図である。

【図３】図２の情報処理システムにおける状態遷移図自
動合成処理を示すフローチャートである。

【図４】図３のステップＳ３の詳細アルゴリズム示すフ
ローチャートである。

【図５】状態遷移テーブルＺの初期状態の決定処理を示
すフローチャートである。

【図６】状態遷移テーブルＺにレコードＸ１のみを登録
する処理を示すフローチャートである。

【図７】レコードＸ１を状態遷移テーブルＺに登録する
処理を示すフローチャートである。

【図８】合成する状態遷移の一例を示す図である。

【図９】合成する状態遷移の他の例を示す図である。

【図１０】図８及び図９の状態遷移図を基に、図４乃至
図７のアルゴリズムを用いて合成された後の状態遷移を
示す図である。

【図１１】本発明の第２実施形態に係る図３のステップ
Ｓ３の詳細アルゴリズムを示すフローチャートである。

【図１２】図１１中のステップＳ９０の詳細処理を示す
フローチャートである。

【図１３】第２実施形態に係る合成する前の状態遷移の
例を示す図である。

【図１４】第２実施形態に係る合成する前の状態遷移の
他の例を示す図である。

【図１５】第２実施形態において全複合状態リスト及び
全イベントリストの例を示す図である。

【図１６】図１３及び図１４の状態遷移図を基に合成さ
れた後の状態遷移の例を示す図である。

【図１７】本発明の第３実施形態における全ての合成後
のオブジェクトに対する状態遷移図である。

【図１８】オブジェクト名と現在状態のテーブルを示す
図である。

【符号の説明】

１ＣＰＵ２バス３ＲＯＭ４ＲＡＭ５入力インターフェース６入力デバイス７出力インターフェース８出力デバイス９外部記憶装置インターフェース１０外部記憶デバイスＥ１コンピュータ端末Ｅ２入出力部Ｅ３イベントシーケンス格納部Ｅ４状態遷移図作成部Ｅ５状態遷移図格納部Ｅ６状態遷移図自動合成部

フロントページの続き (72)発明者大河原将広東京都大田区下丸子３丁目30番２号キヤノン株式会社内

Claims

【特許請求の範囲】

【請求項１】１つの対象物に対して幾つかの側面から
記述された複数の状態遷移図を格納する状態遷移図格納
部と、前記状態遷移図格納部に格納された状態遷移図の中から
任意の２つの状態遷移図を取り出し、その２つの状態遷
移図を自動合成して１つの状態遷移図にする状態遷移図
自動合成部とを備えたことを特徴とする状態遷移図合成
装置。
【請求項２】前記状態遷移図自動合成部は、前記２つ
の状態遷移図を構成する項目である、現在の状態、入力
イベント、アクション、及び次の状態の組からなる各遷
移レコードについて、前記現在の状態、前記入力イベン
ト、及び前記アクションが等しい遷移レコードは同じ遷
移であると判断することを特徴とする請求項１記載の状
態遷移図合成装置。
【請求項３】前記状態遷移図自動合成部は、前記２つ
の状態遷移図を構成する項目である、現在の状態、入力
イベント、アクション、次の状態の組からなる各遷移レ
コードについて、前記現在の状態及び前記入力イベント
が等しいにもかかわらず、前記アクションが異なる遷移
レコードは、整合性エラーであると判断することを特徴
とする請求項１記載の状態遷移図合成装置。
【請求項４】前記状態遷移図自動合成部は、前記２つ
の状態遷移図の中で共通の状態を外部より指定したと
き、またはその指定がないときは該２つの状態遷移図の
初期状態は共通であると判断し、その状態を起点として
合成作業を始めることを特徴とする請求項１記載の状態
遷移図合成装置。
【請求項５】複数の対象物の各々に対してそれぞれ１
枚ずつ記述された状態遷移図を格納する状態遷移図格納
部と、前記状態遷移図格納部に格納された状態遷移図の中から
任意の２つの状態遷移図を第１及び第２の状態遷移図と
して取り出し、その第１と第２の状態遷移図を自動合成
して１つの状態遷移図にする状態遷移図自動合成部とを
備えたことを特徴とする状態遷移図合成装置。
【請求項６】前記状態遷移図自動合成部は、前記第１
の状態遷移図中の状態と前記第２の状態遷移図中の状態
との全ての組み合わせを作成し、それを合成後の状態遷
移図の全ての状態とすることを特徴とする請求項５記載
の状態遷移図合成装置。
【請求項７】前記第１及び第２の状態遷移図は、現在
の状態、入力イベント、アクション、及び次の状態の各
項目から構成されることを特徴とする請求項５記載の状
態遷移図合成装置。
【請求項８】前記状態遷移図自動合成部は、前記第１
の状態遷移図中のイベントの集合と前記第２の状態遷移
図中のイベントの集合との論理和を作り、それを合成後
の状態遷移図中に出てくる全てのイベントであるとした
ことを特徴とする請求項７記載の状態遷移図合成装置。
【請求項９】前記状態遷移図自動合成部は、各対象物
の現在の状態をデータとして持ち、各対象物の状態遷移
図データを個別に保持したままで、入力イベントと各対
象物の現在の状態データとを基に、前記各対象物の状態
遷移図データを動的に検索し、イベントに対するアクシ
ョンと次の状態を計算する唯一のアルゴリズムを持つこ
とにより、合成する対象である第１と第２の状態遷移図
自体を合成するのではなく、見かけ上で状態遷移図の合
成を行うことを特徴とする請求項７記載の状態遷移図合
成装置。
【請求項１０】１つの対象物に対して幾つかの側面か
ら記述された複数の状態遷移図を格納する状態遷移図格
納処理と、前記状態遷移図格納処理によって格納された状態遷移図
の中から任意の２つの状態遷移図を取り出し、その２つ
の状態遷移図を自動合成して１つの状態遷移図にする状
態遷移図自動合成処理とを実行することを特徴とする状
態遷移図合成方法。
【請求項１１】前記状態遷移図自動合成処理は、前記
２つの状態遷移図を構成する項目である、現在の状態、
入力イベント、アクション、及び次の状態の組からなる
各遷移レコードについて、前記現在の状態、前記入力イ
ベント、及び前記アクションが等しい遷移レコードは同
じ遷移であると判断することを特徴とする請求項１０記
載の状態遷移図合成方法。
【請求項１２】前記状態遷移図自動合成処理は、前記
２つの状態遷移図を構成する項目である、現在の状態、
入力イベント、アクション、次の状態の組からなる各遷
移レコードについて、前記現在の状態及び前記入力イベ
ントが等しいにもかかわらず、前記アクションが異なる
遷移レコードは、整合性エラーであると判断することを
特徴とする請求項１０記載の状態遷移図合成方法。
【請求項１３】前記状態遷移図自動合成処理は、前記
２つの状態遷移図の中で共通の状態を外部より指定した
とき、またはその指定がないときは該２つの状態遷移図
の初期状態は共通であると判断し、その状態を起点とし
て合成作業を始めることを特徴とする請求項１０記載の
状態遷移図合成方法。
【請求項１４】複数の対象物の各々に対してそれぞれ
１枚ずつ記述された状態遷移図を格納する状態遷移図格
納処理と、前記状態遷移図格納処理によって格納された状態遷移図
の中から任意の２つの状態遷移図を第１及び第２の状態
遷移図として取り出し、その第１と第２の状態遷移図を
自動合成して１つの状態遷移図にする状態遷移図自動合
成処理とを実行することを特徴とする状態遷移図合成方
法。
【請求項１５】前記状態遷移図自動合成処理は、前記
第１の状態遷移図中の状態と前記第２の状態遷移図中の
状態との全ての組み合わせを作成し、それを合成後の状
態遷移図の全ての状態とすることを特徴とする請求項１
４記載の状態遷移図合成方法。
【請求項１６】前記第１及び第２の状態遷移図は、現
在の状態、入力イベント、アクション、及び次の状態の
各項目から構成されることを特徴とする請求項１４記載
の状態遷移図合成方法。
【請求項１７】前記状態遷移図自動合成処理は、前記
第１の状態遷移図中のイベントの集合と前記第２の状態
遷移図中のイベントの集合との論理和を作り、それを合
成後の状態遷移図中に出てくる全てのイベントであると
したことを特徴とする請求項１６記載の状態遷移図合成
方法。
【請求項１８】前記状態遷移図自動合成処理は、各対
象物の現在の状態をデータとして持ち、各対象物の状態
遷移図データを個別に保持したままで、入力イベントと
各対象物の現在の状態データとを基に、前記各対象物の
状態遷移図データを動的に検索し、イベントに対するア
クションと次の状態を計算する唯一のアルゴリズムを持
つことにより、合成する対象である第１と第２の状態遷
移図自体を合成するのではなく、見かけ上で状態遷移図
の合成を行うことを特徴とする請求項１６記載の状態遷
移図合成方法。