Создание детерминированных конечных автоматов (ДФА) - Меркурий

Question

Я хотел бы иметь детерминированные конечные автоматы (DFA), смоделированные в Меркурии. Но я в нескольких местах.

Формально DFA описывается со следующими характеристиками:

• a setOfStates S,
• inputAlphabet E <- символ суммирования,
• Функция перехода: S × E -> S,
• a startState s € S,

• a setOfAcceptableFinalStates F = C S.

  DFA всегда запускается в начальном состоянии. Затем DFA будет читать все символы на входе, один за другим. На основании текущего входного символа и текущего состояния, он будет переведен в новое состояние. Эти переходы определены в функции переходов. когда DFA находится в одном из его приемлемых конечных состояний после прочтения последнего символа, тогда DFA примет ввод, если нет, то ввод будет отклонен.

  На рисунке показан DFA принимающих строк, где количество нулей равно множеству трех. Условие 1 является исходным состоянием, а также единственным приемлемым состоянием. для каждого входного символа - соответствующая дуга, за которой следует следующее состояние.

Ссылка на рисунок

Что должно быть сделано

1. Тип "mystate", который представляет состояние. Каждый штат имеет номер, который используется для идентификации.

2. Тип "переход", который представляет возможный переход между состояниями. Каждый переход имеет source_state, input_character и final_state.

3. Тип "statemachine", представляющий весь DFA. В решении DFA должен иметь следующие свойства:

   • Множество всех состояний,
   • входной алфавит,
   • функция перехода, представленная в виде набора возможных переходов,
   • набор принятия конечных состояний,
   • текущее состояние ДФА

4. Предикат "init_machine (конечный автомат:: выход)", который объединяет его аргументы с DFA, как показано на рисунке. Текущее состояние для DFA установлено в его начальное состояние, а именно 1. Входной алфавит DFA состоит из символов "0" и "1".

5. Пользователь может ввести текст, который будет контролироваться DFA. программа будет продолжаться до тех пор, пока пользователь не введет Ctrl-D и не смоделирует EOF. Если пользователь использует символы, которые не допускаются во входном алфавите DFA, то появится сообщение об ошибке, и программа закроется. (предварительно требуется)

пример

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

Надеюсь, вы можете помочь мне

С уважением

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