实现代码以模拟C ++中的不确定自动机 [英] Implementing a code to simulate a finite automaton nondeterministic in c++

问题描述

我正在为自动机理论做作业，我必须确定确定性有限自动机的转移函数是否接受一个词

I'm doing an assignment for automata theory, which I have to determine whether a word is accepted or not by a transition function for a deterministic finite automaton

I拥有此输入文件：

6 8 0 2
2
5
0 0 a
0 1 a
1 1 b
1 2 c
1 3 c
3 4 d
4 4 d
4 5 d
3
aaabcccc
aabbbbcdc
acdddddd

输入以4个整数开头，第一个是自动机的状态数，第二个是自动机的转移数，第三个数是初始状态，然后是最终状态数。然后出现最终状态（在示例中，最终状态是2和5）。

The input starts with 4 integers, the first is the number of state for the automaton, next is the number of transitions of the automaton, the third number is the initial state, and then the number of final states. then come the final states (in the example the final states are 2 and 5).

然后出现N行（N是转换数），每行都有2个整数以及一个字符I，J和C，代表转换的状态，即转换从状态i到状态J的字符为C。此行之后是单个整数S，它将包含字符串数进行测试，然后在S行中输入相应的字符串。

Then come N lines (N is the number of transitions), each with 2 integers and a character, I, J and C, representing the states where the transition, ie, the transition goes from state i to state J with the character C. Following this line come with a single integer S, which will contain the number of strings to test, then S lines with the respective strings.

该程序的输出应为：

Case #2:
aaabcccc Rejected
aabbbbcdc Rejected
acdddddd Accepted

它应该说字符串是被接受还是被拒绝。到目前为止，我只使用输入对工作进行编码。

It should say if the String is accepted or rejected. So far, I've only coded the work with the input.

我不知道如何最方便地表示自动机 。我应该只使用数组吗？我将对阵列应用什么逻辑？有什么方法可以不事先知道自动机字母吗？我需要一个数据结构来表示自动机吗？我对这项任务有些困惑，希望有一些想法，一些伪代码或想法可以做到。代码是另一种语言吗？我不想要解决方案，因为我想做作业，但是如果我可以使用一些帮助，请帮忙

I don't know how would be most convenient to represent the automaton. Should I simply use arrays? What logic would I apply to the arrays?. Is there any way to do it without knowing in advance the automaton alphabet? Do I need a data structure to represent automata?. I am a little stuck with this assignment, and would like some ideas, some pseudocode or ideas to do it. Is the code in another language? I do not want the solution, because I want to do my assignment but if I could use some help

推荐答案

我认为您可以拥有一个映射 tr 进行转换，如果 tr [（i，c）] = j ， c $ c> i 状态通过 c 转换为 j 状态，这是最终状态的数组 fs [m] 其中， m 是最终状态的数量和初始状态的整数 s0 。

I think you can have a maptr for transitions where tr[(i, c)] = j if there is transition from i state to j state via c, an array for final states fs[m] where m is the number of final states and an integer for the initial state s0.

下面是具有此类属性的一类框架：

Bellow is a frame of a class with such properties:

class Automata
{
public:
    Automata(int start) : s0(start)
    {}

    void add_transition(int i, int j, char c) {
        //...
    }

    void add_final_state(int i) {
        //...
    }

    bool validate_string(const std::string& str) {
        //...
    }
private:
    std::map<std::pair<int, char>, int> tr; // transitions
    std::vector<int> fs; // final states
    int s0; // initial state
};

这篇关于实现代码以模拟C ++中的不确定自动机的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！