回分類題庫
g062: D.有限狀態自動機
關鍵字: NPSC 2009 國中組決賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 100 Times / 96 Users | Submit : 160 Times / 98 Users | Accepted rate : 98%
題目加入時間 : 2011-12-26 15:11

Content: 简体中文

有限狀態自動機(Finite State Machine)是由有限個狀態以及在這些狀態之間的轉移和動作等行為所組成的數學模型。

有限狀態自動機可以使用狀態轉移圖(State Transition Diagram)來表示,例如下面的狀態轉移圖,表示的是一個可以用來判斷二進位數是否具有偶數個0 的有限狀態自動機。「沒有起點的箭頭」指向狀態S1,表示狀態S1是開始狀態(StartState);狀態S1為雙重圓圈,表示狀態S1是接受狀態(Accept State)。

 

輸入二進位數,例如10101,一開始的狀態是狀態S1;讀到第一個1 的時候,依然停留在狀態S1;讀到第一個0 的時候,移動到狀態S2;讀到第二個1 的時候,依然停留在狀態S2;讀到第二個0 的時候,移動到狀態S1;讀到第三個1 的時候,依然停留在狀態S1;因為狀態S1是接受狀態,表示輸入的二進位數10101 具有偶數個0。

如果輸入的二進位數是10010,最後會停留在狀態S2。因為狀態S2不是接受狀態,所以我們可以知道二進位數10010 不具有偶數個0。

有限狀態自動機也可以使用狀態轉移表(State Transition Table)來表示,例如上面(上一頁)的狀態轉移圖可以表示為:

當前狀態→
條件↓
狀態S1狀態S2
讀到0狀態S2狀態S1
讀到1狀態S1狀態S2

你現在的任務是模擬下圖表示的有限狀態自動機(如果你有興趣的話,你也可以想一想這個有限狀態自動機的目標是找出怎樣的二進位數):

 

Input:

第一行有一個整數N(1≦N≦100),代表總共有N 筆測試資料。每一筆測試資料各佔一行,各為一個二進位數 B,位數最少為 1、最多為100。請不要忽視開頭的0(不論有幾個),舉例而言:二進位數1 和二進位數001 在此題目中是不相同的。

Output:

針對每一筆測試資料,輸出最後會停留在哪一個狀態,如果停留在接受狀態就輸出Accept,否則輸出Reject,格式請參照範例輸出。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3
101011
0110
1011011

Sample Output :

q3: Reject
q0: Accept
q3: Reject

Hint :

Author :

NPSC 2009 國中組決賽 (管理員:sagit)

  Solve it!   Status Forum