我正在做自动机理论的作业,我必须确定确定性有限自动机的转换函数是否接受一个单词
我有这个输入文件:
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
它应该说明字符串是被接受还是被拒绝。到目前为止,我仅使用输入对工作进行了编码。
我不知道如何最方便地表示自动机。我应该简单地使用数组吗?我将对数组应用什么逻辑?有没有办法在不事先知道自动机字母表的情况下做到这一点?我需要一个数据结构来表示自动机吗?我对这个作业有点困惑,想要一些想法、一些伪代码或想法来完成它。代码是另一种语言吗?我不想要解决方案,因为我想完成我的作业,但如果我需要一些帮助
我想你可以有一张地图tr
对于过渡,其中tr[(i, c)] = j
如果有从i
陈述到j
状态通过c
,最终状态的数组fs[m]
where m
是最终状态的数量和初始状态的整数s0
.
波纹管是具有以下属性的类的框架:
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
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)