我正在做一个自动机理论的任务,我必须通过确定性有限自动机的过渡函数来确定一个单词是否被接受
我有这个输入文件：
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
};
