終結狀態

終結狀態

終結狀態,也可以稱之為終止狀態,在計算機科學中,在分析問題時,經常要用到狀態圖,終結狀態是是狀態圖重要組成部分之一。終結狀態簡單來說代表一個活動或事件的結束。終結狀態在很多領域都有提到,例如在自動機理論中,是進程終止的標誌。

簡介

狀態是對象執行某項活動或等待某個事件時的條件。轉移是兩個狀態之間的關係,它由某個事件觸發,然後執行特定的操作或評估並導致特定的結束狀態。

狀態圖用於顯示狀態機(它指定對象所在的狀態序列)、使對象達到這些狀態的事件和條件、以及達到這些狀態時所發生的操作。狀態機由狀態組成,各狀態由轉移連結在一起。狀態圖中可以有多種不同的狀態,但有兩種狀態是不可或缺的,分別是起始狀態和終結狀態。起始狀態是指一個活動或事件的開始。而終結狀態代表一個活動或事件的結束。

進程的終結狀態

進程(Process)是計算機中的程式關於某數據集合上的一次運行活動,是系統進行資源分配和調度的基本單位,是作業系統結構的基礎。在早期面向進程設計的計算機結構中,進程是程式的基本執行實體;在當代面向執行緒設計的計算機結構中,進程是執行緒的容器。程式是指令、數據及其組織形式的描述,進程是程式的實體。進程執行時的間斷性,決定了進程可能具有多種狀態。事實上,運行中的進程可能具有以下三種基本狀態:就緒狀態、運行狀態(Running)、阻塞狀態(Blocked)。在目前實際的系統中,為了管理的需要,還存在著兩種比較常見的進程狀態,即創建狀態和終止狀態。

終結狀態:進程的終止也要通過兩個步驟: 首先等待作業系統進行善後處理,然後將其 PCB 清零,並將 PCB 空間返還系統。當一個進程到達了自然結束點,或是出現了無法克服的錯誤,或是被作業系統所終結,或是被其他有終止權的進程所終結,它將進入終止狀態。進入終止態的進程以後不能再執行,但在作業系統中依然保留一個記錄,其中保存狀態碼和一些計時統計數據,供其它進程收集。一旦其它進程完成了對終止狀態進程的信息提取之後,作業系統將刪除該進程。

自動機的終結狀態

有關概念

計算機控制系統的控制程式具有有限狀態自動機(FA)的特徵,可以用有限狀態機理論來描述。有限自動機(Finite Automata Machine)是計算機科學的重要基石,它在軟體開發領域內通常被稱作有限狀態機(Finite State Machine),是一種套用非常廣泛的軟體設計模式。自動機是有限狀態機(FSM)的數學模型。

自動機就是一個有內部狀態的機器。它有一個初始狀態,而每當它接收到一個字元,它就根據字元和當前的內部狀態,更新自己的內部狀態(新狀態與舊狀態和輸入字元之間的函式關係稱為狀態轉移函式),而當所有字元都處理完之後,我們根據自動機的最終狀態,將接受的字元串分為兩類:自動機接受的字元串和自動機不接受的字元串。

數學模型

終結狀態 終結狀態

自動機可以表示為5-元組 ,這裡的:

Q 是狀態的非空有窮集合。

∑ 是符號的有限集合,我們稱為這個自動機接受的語言的字母表。 輸入字元串都是∑上的字元串

終結狀態 終結狀態

δ 是狀態轉移函式,就是 。(對於非確定自動機,空串是允許的輸入)。

q0 是開始狀態,就是說自動機在還未處理輸入的時候的狀態(明顯的 q0∈ Q)。

F 是終止狀態集合,也叫做接受狀態的 Q 中的狀態的集合(就是 F⊆Q)。

接受器和識別器

接受器和識別器(也叫做序列檢測器)產生一個二元輸出,說要么“是”要么“否”來回答輸入是否被機器接受。所有FSM的狀態被稱為要么接受要么不接受。在所有輸入都被處理了的時候,如果當前狀態是接受狀態,輸入被接受,否則被拒絕。作為規則,輸入是符號(字元);動作不使用。

機器還可以被描述為定義了一個語言,它包含了這個機器所接受而非拒絕的所有字詞;我們稱這個語言被這個機器接受。通過定義,FSM接受的語言是正則語言 - 就是說,如果一個語言被某個FSM接受,那么它是正則的(cf. Kleene的定理)。

開始狀態

開始狀態通常用“沒有起點的箭頭”指向它來表示。

接受(終結)狀態

接受狀態(或稱終結狀態)是一個機器回報到目前為止,輸入字元串屬於它所接受的內容之狀態。狀態圖中通常將其標示為雙圓圈。

終結狀態 終結狀態

開始狀態也可以是接受狀態或終結狀態,此情況下自動機會接受空字元串。如果開始狀態不是接受狀態,且沒有可以連到任何接受狀態的箭頭,那么此自動機就不會“接受”任何輸入。

一個接受狀態的例子如圖:一台判斷輸入二進位字元串是否含有偶數個0的 確定有限自動機(DFA)。

S1代表著已經輸入了偶數個0,因此S1 即為接受狀態(同時亦為開始狀態)。若輸入含有偶數個0(包含沒有0的字元串),則此機器會以接受狀態來結束。

被這台DFA接受的字元串,舉例來說是ε(空字元串), 1, 11, 11…, 00, 010, 1010, 10110…等等。

相關詞條

相關搜尋

熱門詞條

聯絡我們