有限狀態機程序

我的任務是創建一個小程序，該程序可以從輸入中讀取FSM的定義，從輸入中讀取一些字符串，並根據定義確定FSM是否接受這些字符串。我需要用C，C++或Java編寫它。我在網上搜索了關於如何開始的想法，但我能找到的最好的是關於Automata-based programming的維基百科文章。所提供的C示例似乎使用枚舉列表來定義狀態，如果狀態是事先硬編碼的，那就沒問題了。再次，我需要能夠實際讀取狀態的數量和每個狀態應該做什麼的定義。任何建議表示讚賞。有限狀態機程序

UPDATE：我可以使字母小（例如{A B}），並採用這樣的其他公約作爲開始狀態總是我允許對狀態，例如數量強加合理的限制狀態0。不超過10個

問題總結：

如何實現的FSA？

來源

2009-11-21 kingrichard2005

什麼是輸入格式？在繼續之前，它需要有明確的定義。 – outis

你能描述一下你輸入文件的格式嗎？ – poundifdef

......更重要的是，你將如何表達「每個州應該做什麼的定義」？你應該提供更多關於你需要做什麼的信息。 –

首先，獲取所有狀態（其中N個）的列表以及所有符號（其中M個）的列表。然後有兩種方式可以解釋或代碼生成：

解釋。創建一個NxM矩陣，其中矩陣的每個元素都填入相應的目標狀態編號，如果沒有，則爲-1。然後只需要一個初始狀態變量並開始處理輸入。如果你達到-1，你就會失敗。如果用完輸入符號而未達到成功狀態，則失敗。否則你成功了。
代碼生成。用C或你最喜歡的編譯器語言打印一個程序。它應該有一個整數狀態變量初始化爲開始狀態。它應該有一個for在輸入字符上循環，在狀態變量上包含一個開關。每個狀態應該有一個case，並且在每種情況下，在當前字符上都有一個switch語句來改變狀態變量。

如果你想要的東西比2再快，那就是一定要得到你不及格（！），擺脫了狀態變量，而使用轉到 :-)如果你不及格，你可以安慰你自己知道這就是編譯器所做的。

P.S.如果您在狀態圖中識別環路等，則可以將您的F更改爲A，並打印出相應的，而和如果陳述，而不是使用轉到。

來源

2009-11-23 18:16:03

感謝邁克和所有提供寶貴信息的人。我繼續使用你的解釋方法，並能夠在一天內完成一個完整的工作程序。非常感謝，這是一個很好的幫助和非常豐富的信息 – kingrichard2005

@king：不客氣。 –

如果您使用的是像Java或C++這樣的面向對象的語言，我建議您從對象開始。在擔心文件格式之類的問題之前，先爲有限狀態自動機及其行爲表現一個好的對象模型。你將如何代表國家，轉型，事件等？你的FSA會成爲複合材料嗎？一旦你有這樣的工作，你可以得到正確的文件格式。任何事情都可以做到：XML，文本等

來源

2009-11-21 22:56:01 duffymo

你好duffymo，這是一個學術項目，所以我正在和我的教授談談他想如何代表國家，轉型等。不太清楚複合材料的含義，我知道我們必須使用的字母只限於字符'a'和'b'。爲了清晰起見，我會更新問題描述。 – kingrichard2005

作者：Composite，我的意思是GoF設計模式，其中FSA可以是狀態機中的一個狀態。 – duffymo

表示自動機的一種非硬編碼方式是作爲轉換矩陣，它允許爲每個當前狀態和每個輸入字符表示下一個狀態。

來源

2009-11-21 22:57:15

您還沒有真正問過問題。如果您有針對特定任務的特定question（但仍然提供總體目標），您將獲得更多更好的幫助。這個問題的範圍應該很窄（例如不是「我如何實施FSA？」）。

至於如何表示一個FSA（這似乎是你有什麼困難），請繼續閱讀。

開始考慮一個有限狀態機的定義：它是一個字母Σ，一組狀態第，開始狀態小號，一組狀態一個和過渡功能的接受δ從一個國家和一個符號到一個國家。您必須能夠從輸入中確定這些屬性。轉換函數無法訪問的任何狀態都可以被刪除以產生等效的FSM。狀態和字母表的最小集合因此隱含在轉換函數中;您可以通過在輸入中不要求使用Σ或S，使您的FSM更易於使用（並且難以實施，但難度更大）。

您不需要對輸入使用的狀態使用相同的表示。只要你有一個從整數到字符串和字符串到整數的映射，你可以使用無符號整數作爲你的內部表示，這樣你就可以在內部表示和外部表示之間進行轉換。這樣，您的轉換函數可以作爲一個數組存儲，所以轉換步驟可以在不變的時間內執行。

更簡單的方法是使用外部表示法作爲內部表示法。使用這個選項，轉換函數將被存儲爲從字符串和符號到字符串的映射。考慮到大多數地圖數據結構的性能，轉換步驟可能是O（log（| S | + |Σ|））。如果符號表示爲整數（例如char s），則可以將轉換函數表示爲從字符串到字符串數組的映射，給出O（log（| S |））性能。

在FSM的圖形視圖之後建模的另一個選項是爲狀態創建一個類。一個國家有一個名稱（外部表示）。各國負責過渡;發送一個符號到一個狀態並取回另一個狀態。

將該組狀態存儲爲從名稱到狀態的映射。

你走了，三個不同的地方開始，每個地方都有不同的方式來表示國家。

來源

2009-11-21 22:58:54 outis

不要一下子想到一切。做一兩件事的時間

- come with language of state machine 
- come with language for stimulus 
- create sample file of one state machine in language 
- create sample file of stimulus 
- come with class for state 
- come with class for transition 
- come with class for state machine as set of states and transitions 
- add method to handle violation to state class 
- code a little parser for language 
- code another parser for language 
- initial state 
- some output thing like WriteLn here and there 
- main method 
- compile 
- run 
- debug 
- done

來源

2009-11-21 23:06:09

的OpenFst工具做它的方式是：A FSM有狀態的載體，其中的每一個具有圓弧的載體。每個弧具有輸入（和輸出）標籤，目標狀態ID和權重。你可以看看代碼。也許它會激勵你。

來源

2009-11-21 23:11:46 Frank

有限狀態機程序

回答

相關問題