finite-automata - 有限状態マシンとデッドロック

Question

これは私の問題です

デッドロックのない 2 つのステート マシンの痕跡を知っています。

コンポジションがデッドロックフリーであるかどうか、トレースで知りたいです（estructureを知りません）。

これを知ることができる定理はありますか？

Answer 1

実際にコンポジションを処理している場合（初期パラメーターを使用してマシンAを実行し、次に初期パラメーターとしてAの最終パラメーターを使用してマシンBを実行）、コンポジションのデッドロックは必然的にAまたはBのいずれかで発生します。

Aでは発生しません（Bが存在しない場合にも発生します）。また、Bでは発生しません（Aが存在せず、Bに同じ初期パラメーターを使用した場合にも発生します）。したがって、AとBはデッドロックがないという最初の仮定に基づいて、それらの構成もデッドロックがありません。