創建確定性有限自動機（DFA） - Mercury

Question

我想要在Mercury中模擬確定性有限自動機（DFA）。 但是我在幾個地方都有。

形式上，DFA是具有以下特徵的描述：

• 一個setOfStates S，
• 一個inputAlphabetë< - 求和符號，
• 一個transitionFunction：S×E - >取值，
• 一個將startState小號€S，

• 一個setOfAcceptableFinalStates F = C^S.

  DFA將始終在啓動狀態下啓動。 然後DFA將逐個讀取輸入中的所有字符。 根據當前輸入字符和當前狀態，會有 到一個新的狀態。 這些轉換在轉換函數中定義。 當DFA處於其可接受的最終狀態之一時，在讀完最後一個字符後，DFA將接受輸入，如果不是，則輸入將被拒絕。

  該圖顯示了一個DFA接受的字符串，其中零的數量是多個三。條件1是初始狀態，也是唯一可接受的狀態。對於每個輸入字符來說，相應的弧線是下一個狀態。

Link to Figure

必須做什麼

1. A型「mystate」表示的狀態。每個州都有一個用於識別 的號碼。

2. 表示狀態之間可能轉換的類型「轉換」。 每個轉換都有一個source_state，一個input_character和一個final_state。

3. 表示整個DFA的「statemachine」類型。在該解決方案中，DFA必須具有以下性質：

   • 的集合中的所有狀態中的，
   • 輸入字母，
   • 一個過渡函數，表示爲一組可能的轉變的，
   • 一個組接受最終狀態的，
   • 的DFA

4. 謂詞「init_machine的當前狀態（狀態機::出） 「它將自己的論點與DFA的 統一起來，如圖所示。 DFA的當前狀態設置爲其初始狀態，即1. DFA的輸入字母表由字符'0'和'1'組成。

5. 用戶可以輸入一個文本，該文本將由DFA控制。該程序將繼續執行，直到用戶鍵入Ctrl-D並模擬EOF。如果用戶在DFA的輸入字母表中使用了 字符，則會出現一條錯誤消息，結束該程序將關閉。 （PRED要求）

例

Enter a sentence: 0110 
String is not ok! 
Enter a sentence: 011101 
String is not ok! 
Enter a sentence: 110100 
String is ok! 
Enter a sentence: 000110010 
String is ok! 
Enter a sentence: 011102 
Uncaught exception Mercury: 
Software Error: Character does not belong to the input alphabet! 

---

的東西笏我有。

:- module dfa. 
:- interface. 
:- import_module io. 
:- pred main(io.state::di, io.state::uo) is det. 

:- implementation. 
:- import_module int,string,list,bool. 

:- type mystate ---> state(int). 

:- type transition 
      ---> trans(
        source_state::mystate, 
        input_character::bool, 
        final_state::mystate 
        ). 

（錯誤，finale_state和current_state和input_character）

:- type statemachine 
        ---> dfa(
         list(mystate), 
         list(input_character), 
         list(transition), 
         list(final_state), 
         current_state(mystate) 
         ). 

遺漏了很多

:- pred init_machine(statemachine :: out) is det. 

%init_machine(statemachine(L_Mystate,0,L_transition,L_final_state,1)) :- <-probably fault 

不完美

main(!IO) :- 
     io.write_string("\nEnter a sentence: ", !IO), 
     io.read_line_as_string(Input, !IO), 
     (
       Invoer = ok(StringVar), 
       S1 = string.strip(StringVar), 
       (if S1 = "mustbeabool" then 

         io.write_string("Sentenceis Ok! ", !IO) 
       else 
         io.write_string("Sentence is not Ok!.", !IO)), 
       main(!IO) 
     ; 
       Invoer = eof 
     ; 
       Invoer = error(ErrorCode), 
       io.format("%s\n", [s(io.error_message(ErrorCode))], !IO) 
     ). 

希望你能幫助我

親切的問候

Answer 1

當你寫一個類型如mystate：

:- type transition ---> trans(source_state::mystate, input_character::bool, final_state::mystate). 

不要把它全寫在一行上，很難閱讀。

:- type transition 
    ---> trans(
       source_state  :: mystate, 
       input_character :: bool, 
       final_state  :: mystate 
      ). 

現在它更容易閱讀。我們也可以看到類型和字段名稱是錯誤的。請嘗試：

:- type transition 
    ---> trans(
       mystate :: source_state, 
       bool  :: input_character, 
       mystate :: final_state 
      ).