オートマトンを解析するアルゴリズム

質問

オートマトンを解析するアルゴリズムは存在しますか？

回答No.5

noname#208507 · ベストアンサー

> ブラックボックスで中はわからない状態で、です

有限の時間内に、中を特定できるアルゴリズムは存在しないと思いますが。

何度入力を与えても、入力と無関係にランダムな値を返す関数が、たまたま何かの関数と等価の値を返した可能性を否定できないので。

お礼

わかりやすい例をありがとうございます

回答No.4

επιστημη（@episteme）

> 入力と出力を測定し、内部状態と関数を求める、ということをしたいです。

それは解析というより、(1stepずつ)実行するってことじゃないすか?

補足

ブラックボックスで中はわからない状態で、です

回答No.3

noname#208507

どんなオートマトンの、何を解析するかによりますが。

解析したいシステムの振る舞いを有限状態オートマトンで表現し、検査したい性質が書かれた式（線形時相論理）もオートマトンに変換して、両者の受理する言語の集合のANDをとることでその性質を自動的に検査するソフトウェアがあります。オートマトンに基づくモデル検査器と呼ばれており、SPINというソフトが有名です。論文をあたれば、どのようなアルゴリズムで実現されているか分かるでしょう。

http://ja.wikipedia.org/wiki/SPIN%E3%83%A2%E3%83%87%E3%83%AB%E3%83%81%E3%82%A7%E3%83%83%E3%82%AB

回答No.2

noname#198951

"解析するアルゴリズム"と言うのがそもそも意味不明ですが。

オートマトンは、オートマシンの読み間違えという説があるので、自動機械だと考え、状態遷移表や図から流れを想像するだけでは？
その為のアルゴリズムなんて、人の想像やひらめきをプログラム化するのと同じでかなり無謀だと思うけど。

オートマトンの状態遷移表からアルゴリズムを推測してプログラムを作ると言うのなら簡単ではあるけど。

回答No.1

επιστημη（@episteme）

解析って、なにすりゃいいですか?
# 「停止するか?」の判定すら原理的に不可能ですけど。

補足

入力と出力を測定し、内部状態と関数を求める、ということをしたいです。