[發明專利]一種狀態機的合并方法和裝置

有效

• 申請號: 201410838366.6
• 申請日: 2014-12-29
• 公開（公告）號: CN104503733B
• 公開（公告）日: 2017-10-20
• 發明（設計）人: 王磊;楊磊;謝少林
• 申請（專利權）人: 中國科學院自動化研究所
• 主分類號: G06F9/38
• 分類號: G06F9/38
• 代理公司: 中科專利商標代理有限責任公司11021
• 代理人: 宋焰琴

1.一種狀態機的合并方法，包括以下步驟：

步驟1，對輸入的所有子狀態機的狀態進行分析，并將所述所有子狀態機的狀態轉換圖轉變為順序連接的一個或多個狀態塊；

步驟2，將輸入的所有子狀態機的首個狀態塊取出，判斷這些狀態塊的可拼接性和輸出子狀態機的拼接類型；

若該步驟判定可拼接性是采用拼接規則，且拼接類型是全順序塊類型、全循環塊類型或全嵌套循環塊類型之一，則判斷循環次數是否相同，若相同則將所有輸入子狀態機放入步驟5的輸入中，直到本次輸入中沒有子狀態機時跳到步驟5，若循環次數不相同則采用等價變換規則判定，跳轉至步驟3進行子狀態機提取規則判定；

若該步驟判定可拼接性是采用等價變換規則，且拼接類型是有嵌套循環塊的全循環塊類型，則將當前狀態塊為循環塊的子狀態機放入下一次步驟2的輸入中，將當前狀態塊為嵌套循環塊的子狀態機放入步驟3的輸入中，直到本次輸入中沒有子狀態機時跳到步驟3；

若該步驟判定可拼接性是采用等價變換規則，且拼接類型是非全順序塊類型，則將當前狀態塊為順序塊的子狀態機放入下一次步驟2的輸入中，將當前狀態塊為非順序塊的子狀態機放入步驟3的輸入中，直到本次輸入中沒有子狀態機時跳到步驟3；

若該步驟判定可拼接性和輸出的拼接類型不符合上述情況時，該方法輸出子狀態機不可拼接，該方法結束；

步驟3，接收符合等價變換規則的狀態塊，根據狀態塊組合的情況判定需要提取的狀態數量并輸出給步驟4；

步驟4，將輸入的子狀態機按照拼接類型進行等價變換，等價變換后的子狀態機與輸入子狀態機功能完全一致，但狀態塊結構不同，并且等價變換后的子狀態機狀態塊表示輸出到步驟2的輸入中替換原子狀態機的狀態塊表示，重新做可拼接性判定；若輸入的拼接類型是非全順序塊類型，則將輸入的所有子狀態機做抽取順序塊等價變換，若輸入的拼接類型是有嵌套循環塊的全循環塊類型，則將輸入的所有子狀態機做抽取循環塊等價變換，當輸入中沒有需要等價變換的子狀態機時，跳轉到步驟2；

步驟5，對輸入的所有子狀態機狀態塊進行拼接，輸出合并狀態機；若存在不能拼接的狀態塊，則跳轉到步驟2。

2.根據權利要求1所述的狀態機的合并方法，其中所述步驟1包括：

子步驟1.0，讀取一個輸入子狀態機的當前狀態，判斷該狀態是哪種狀態塊的起始狀態，并跳轉到相應狀態塊分析的子步驟；

子步驟1.1，收集符合順序塊特征的狀態，并輸出到一個順序塊中；

子步驟1.2，收集符合循環塊特征的狀態，并輸出到一個循環塊中，并記錄循環塊的循環條件；

子步驟1.3，識別并輸出只有一個狀態的循環塊，并記錄循環塊的循環條件；

子步驟1.4，刪除輸入子狀態機狀態轉換圖中該嵌套循環塊的狀態轉換，并將涉及狀態轉換的信息輸出到子步驟1.5；以及

子步驟1.5，根據輸入的狀態，嵌套循環塊的嵌套信息將子狀態機的狀態塊表示輸出到步驟2的輸入中。

3.根據權利要求2所述的狀態機的合并方法，其中所述的子步驟1.5包括以下步驟：

判斷輸入中是否有嵌套循環的循環條件，若有，則創建一個新的嵌套循環塊，記錄該嵌套循環塊的結束狀態，并將輸入中的狀態塊放入該嵌套循環塊中，并將該新嵌套循環塊作為輸入的狀態塊；

若當前有嵌套循環塊未結束，則將輸入的狀態塊放入當前嵌套循環塊；

若輸入的狀態塊是嵌套循環塊則將當前嵌套循環塊切換到輸入的狀態塊；

若當前輸入的狀態塊的最后一個狀態是當前嵌套循環塊標記的結束狀態，則退出當前嵌套循環塊，將當前嵌套循環塊切換為上一層嵌套循環塊，若不存在上一層嵌套循環塊，則將該嵌套循環塊輸出到該子狀態機的狀態塊表示中；

若當前沒有嵌套循環塊且輸入不是嵌套循環塊，則將輸入的狀態塊輸出到該子狀態機的狀態塊表示中；

判斷若當前狀態是狀態機的結束狀態，則將該子狀態機從子步驟1.0的輸入中刪除，若子步驟1.0的輸入中沒有子狀態機則跳轉到步驟2。

4.根據權利要求1所述的狀態機的合并方法，其中步驟2中所述的輸出子狀態機的拼接類型包括：含有嵌套循環塊的全循環塊類型、非全順序塊類型、全順序塊類型、全循環塊類型和全嵌套循環塊類型。