相关疑难解决方法(0)

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

我有这个输入文件:

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

它应该说是否接受或拒绝字符串.到目前为止,我只使用输入编写了工作.

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

我正在使用Konrad Rudolph提出的算法实现本文和另一篇文章中描述的非确定性有限自动机.

我没有使用C++多图,而是使用了一个HashSet<Character> [][] transitions数组(这是家庭作业,Google的番石榴库不能使用).第一维是原始状态,第二维是命运状态,而HashSet定义原点和命运状态之间转换的符号.我的Automaton类的构造函数是:

Automaton (int numberOfStates)
{
    this.numberOfStates = numberOfStates;
    alphabet = new HashSet<>();
    finalStates = new HashSet<>();

    transitions = new HashSet[numberOfStates][numberOfStates];

    for (int i = 0; i < numberOfStates; i++)
    {
        for (int j = 0; j < numberOfStates; j++)
        {
            transitions[i][j] = new HashSet<Character>();
        }
    }
}

这是我使用此过渡数组实现的Konrad Rudolph算法:

public String readStringInAutomaton (char[] inputString,
            int initialState)
{
    HashSet<Integer> currentStates = new HashSet<>();
    HashSet<Integer> nextStates = new HashSet<>();

    currentStates.add(initialState);

    // …