變遷系統

在計算機科學和控制理論中，“變遷系統”用數學的方法描述離散系統的行為。變遷系統主要由“狀態”和狀態之間的“狀態遷移”組成。

基本介紹

• 中文名：變遷系統
• 學科：計算機

簡介

有標號的變遷系統可以從已定義的標籤集合中選擇相應標籤來標記狀態遷移，而且相同的標籤可能被套用在多個狀態遷移上。 變遷系統也可以是無標記的，此時也可以認為標籤集合中只有單一標籤元素，從而省略了狀態遷移上的標籤記號。變遷系統在數學定義上和有向圖一致，但與有限狀態自動機有一定不同。

特點

變遷系統的特點有：

• 系統狀態的集合不一定是有限的或可數的；
• 狀態遷移的集合不一定是有限的或可數的；
• 變遷系統並不需要給出“開始”狀態或“最終”狀態；
• 變遷系統可以表示為有向圖，有限狀態自動機則不能。

操作語義學

操作語義學是計算機科學中的一個概念，它是使得電腦程式在數學上更加嚴謹的一種手段。其它類似的手段包括提供形式語義學，包括公理語義學和指稱語義。

一個計算機語言的操作語義描述一段合理的程式是怎樣被理解為一系列計算機步驟的。這些步驟就是這個程式的意義。在函式程式語言中一段終結性的序列在最後一步的返回程式的值。（由於一個程式可能是非非決定的，一般來說一個程式能夠有許多不同的計算步驟和許多不同的返回值。）

操作語義最早被用來定義Algol 68的語義。下面這句話引用修正的ALGOL 68報告：

一個使用嚴格語言編寫的程式的意義是通過一個假設的計算機來執行該程式的組成部分時完成的行動來解釋的。（Algol68，第二章）

丹納·司科特是第一個在今天的這個定義下使用操作語義這個概念的（Plotkin04b）。以下是司科特關於形式語義學的講稿，其中他提到了語義的“操作”觀點。

有限狀態機

有限狀態機（英語：finite-state machine，縮寫：FSM）又稱有限狀態自動機，簡稱狀態機，是表示有限個狀態以及在這些狀態之間的轉移和動作等行為的數學模型。

狀態存儲關於過去的信息，就是說：它反映從系統開始到現在時刻的輸入變化。轉移指示狀態變更，並且用必須滿足確使轉移發生的條件來描述它。動作是在給定時刻要進行的活動的描述。有多種類型的動作：

• 進入動作（entry action）：在進入狀態時進行
• 退出動作：在退出狀態時進行
• 輸入動作：依賴於當前狀態和輸入條件進行
• 轉移動作：在進行特定轉移時進行