创建确定性有限自动机 (DFA) - Mercury

我想要在 Mercury 中模拟确定性有限自动机 (DFA)。 但我有几个地方很糟糕。

形式上，DFA 具有以下特征：

• 一组状态 S，
• 一个输入字母 E
• 一个转换函数：S × E --> S，
• 一个startState s € S，

• setOfAcceptableFinalStates F =C S。

  DFA 将始终在启动状态下启动。 然后 DFA 将一一读取输入中的所有字符。 根据当前输入的字符和当前状态，将做出 到一个新的状态。 这些转换在转换函数中定义。 当DFA处于他可接受的最终状态之一时，在读取最后一个字符后，DFA会接受输入，如果不接受，则输入将被拒绝。

  该图显示了接受字符串的 DFA，其中零的数量为多个三个。条件1是初始状态，也是唯一可接受的状态。对于每个输入字符，都有相应的弧线跟随到下一个状态。

链接至图

必须做什么

1. 代表状态的“mystate”类型。每个州都有一个号码，用于 鉴别。

2. 一种“转换”类型，表示状态之间可能的转换。 每个转换都有一个 source_state、一个 input_character 和一个 Final_state。

3. 代表整个 DFA 的“状态机”类型。在该解决方案中，DFA必须具有以下属性：

   • 所有状态的集合，
   • 输入字母表，
   • 一个转换函数，表示为一组可能的转换，
   • 一组接受最终状态，
   • DFA 的现状

4. 谓词“init_machine (state machine :: out)”将他的参数与 DFA，如图所示。 DFA的当前状态被设置为其初始状态，即1。DFA的输入字母表由字符“0”和“1”组成。

5. 用户可以输入文本，该文本将由 DFA 控制。该计划将 继续，直到用户键入 Ctrl-D 并模拟 EOF。如果用户使用 不允许进入 DFA 输入字母表的字符，则会出现错误消息，程序将关闭。 （预计需要）

Example

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.

1

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

2

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

3（错误、finale_state 和 current_state 以及 input_character）

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

4错过了很多

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

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

5不完美

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)
        ).

希望你能帮我

亲切的问候

当您编写诸如 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
            ).