状態遷移から知る有限オートマトン
- 前回の勉強内容
- 今回の勉強内容 : 状態遷移図を使って有限オートマトンを知る
- 無効と有効の状態遷移をテストする状態遷移テストというものがあります。
- オートマトンは、入力から内部の状態と規則に従い結果を出力する仮想的な自動機械です。
- 次回の勉強内容
前回の勉強内容
今回の勉強内容 : 状態遷移図を使って有限オートマトンを知る
勉強のきっかけになった問題
次の表は，入力記号の集合が{0，1}，状態集合が{a，b，c，d}である有限オートマトンの状態遷移表である。長さ3以上の任意のビット列を左(上位ビット)から順に読み込んで最後が110で終わっているものを受理するには，どの状態を受理状態とすればよいか。
1. a 2. b 3. c 4. d
平成18年秋期問7 有限オートマトンの状態遷移表｜応用情報技術者試験.com
無効と有効の状態遷移をテストする状態遷移テストというものがあります。
- 英語 : state transition testing
ブラックボックステストの設計技法の一つ。無効と有効の状態遷移を実行するテストケースを設計する。
JSTQBソフトウェアテスト標準用語集
状態遷移をテストするには状態の遷移を整理するために図と表を使用します。
状態遷移図は、発生する可能性のあるイベントとその結果の状態を図にしたものです。
- 英語 : state diagram
- 特徴
- 「できること」を表現する
- 状態遷移の流れを容易に把握できる
- 図示することによって新たな発見がある
- どこへの遷移もしない状態 / 複数の異なる状態に遷移するイベント
- 状態遷移に関する仕様の不備にだって気がつく
コンポーネント又はシステムが取りうる状態を示し、ある状態から他への状態の変化の原因となる、（又は）その結果として生ずる、イベントや状況を表すダイアグラム。
JSTQBソフトウェアテスト標準用語集
A diagram that depicts the states that a system or component can assume, and shows the events or circumstances that cause or result from a change from one state to another.
IEEE 610Standard Glossary of Software Engineering Terminology
図はマルチタスクで動作するコンピュータにおけるタスクの状態遷移を表したものである。実行状態のタスクが実行可能状態に遷移するのはどの場合か。
- 自分より優先度の高いタスクが実行可能状態になった。
- タスクが生成された。
- 入出力要求による処理が完了した。
- 入出力要求を行った。
平成23年秋期問20 タスクの状態遷移｜基本情報技術者試験.com
状態遷移表は、発生する可能性のあるイベントと状態の組み合わせから生じる結果を示す遷移をテーブルで表したものです。
- 英語 : state table
- 無効な遷移と、有効な遷移の両方を示します。
- 特徴
- 「できないこと」を洗い出せる
- 仕様があいまいな個所に潜む欠陥を発見できる
- 全ての状態と全てのイベントを組み合わせるので、仕様のあいまいな個所を特定できる
- 状態遷移図の不備を見つけることができる
次の表は，文字列を検査するための状態遷移表である。検査では，初期状態をaとし，文字列の検査中に状態がeになれば不合格とする。
解答群で示される文字列のうち，不合格となるものはどれか。ここで，文字列は左端から検査し，解答群中の△は空白を表す。
ア. ＋0010 イ. －1 ウ. 12.2 エ. 9.△
平成18年春期問9 状態遷移表｜基本情報技術者試験.com
図は，偶数個の1を含むビット列を受理するオートマトンの状態遷移図であり，二重丸が受理状態を表す。a，bの正しい組合せはどれか。
回答群
平成25年春期問3 オートマトンの状態遷移図｜応用情報技術者試験.com
状態遷移図と状態遷移表は、各メリットを合わせてお互いを見合わせながら整理することでテストケースを洗い出す事ができます。
状態遷移図では動作を想定しながら作るので「できること」に着目しがちですが、状態遷移表は状態とイベントを網羅的に組み合わせるので「できないこと」にも気が付けるのです。
性格が違うのだからどちらかあればいいってわけではないのですね。
オートマトンは、入力から内部の状態と規則に従い結果を出力する仮想的な自動機械です。
- 英語 : automaton
入力と状態の数がある程度決まっているのが有限オートマトンです。
- 別名 : 有限状態機械
有限個の状態と遷移と動作の組み合わせからなる数学的に抽象化された「ふるまいのモデル」である。
デジタル回路やプログラムの設計で使われることがあり、ある一連の状態をとったときどのように論理が流れるかを調べることができる。有限個の「状態」のうち1つの状態をとる。ある時点では1つの状態しかとらず、それをその時点の「現在状態」と呼ぶ。
何らかのイベントや条件によってある状態から別の状態へと移行し、それを「遷移」と呼ぶ。それぞれの現在状態から遷移しうる状態と、遷移のきっかけとなる条件を列挙することで定義される。
有限オートマトン - Wikipedia
図で表される有限オートマトンで受理される文字列はどれか。ここで
は初期状態を，
受理状態を表す。
ア 01011 イ 01111 ウ 10111 エ 11110
平成18年秋期問11 有限オートマトン｜基本情報技術者試験.com
勉強のきっかけになった問題も状態遷移図を書いてみるとわかりやすいです。
