实现一个代码来模拟c中的非确定性的有限自动机

发布时间：2020-12-16 05:37:20 所属栏目：百科来源：网络整理

导读：我正在做一个自动机理论的任务,我必须通过确定性有限自动机的过渡函数来确定一个单词是否被接受我有这个输入文件： 6 8 0 2250 0 a0 1 a1 1 b1 2 c1 3 c3 4 d4 4 d4 5 d3aaabccccaabbbbcdcacdddddd 输入以4个整数开始,第一个是自动机的状态数,接下来是自动

我正在做一个自动机理论的任务,我必须通过确定性有限自动机的过渡函数来确定一个单词是否被接受

我有这个输入文件：

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

然后进入N行(N是转换次数),每个都有2个整数,一个字符I,J和C表示转换,即转换从状态i到状态J与字符C的状态.在这行后面附带一个整数S,它将包含要测试的字符串数,然后S行与相应的字符串.

该程序的输出应为：

Case #2:
aaabcccc Rejected
aabbbbcdc Rejected
acdddddd Accepted

应该说String是否被接受或拒绝.到目前为止,我只用输入的方式对工作进行编码.

我不知道如何代表自动机最方便.我应该使用数组吗？对阵列应用什么逻辑？没有事先知道自动机字母表有什么办法吗？我需要一个数据结构来表示自动机吗？我有一点困扰这个任务,并希望一些想法,一些伪代码或想法来做到这一点.代码是否是另一种语言？我不想要解决方案,因为我想做我的任务,但如果我可以使用一些帮助

解决方法

我想你可以有一个转换的映射,其中tr [(i,c)] = j如果通过c从i状态转换到j状态,最后状态的数组fs [m]其中m是最终状态数以及初始状态s0的整数.

Bellow是一个具有这样性质的类的框架：

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
};

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!