c++ - 在 C++ 中模拟确定性下推自动机 (PDA)

Question

我正在阅读 UVA 的练习，我需要用它来模拟确定性下推自动机，看看 如果某些字符串在以下格式的给定条目上被 PDA 接受或不接受:

输入的第一行会是一个整数C，表示测试用例的个数。每个测试用例的第一行包含五个整数 E、T、F、S 和 C，其中 E 表示自动机中的状态数，T 表示转换数，F 表示最终状态数，S 表示初始状态和C 分别是测试字符串的个数。下一行将包含 F 个整数，代表自动机的最终状态。然后是 T 行，每行有 2 个整数 I 和 J 以及 3 个字符串 L、T 和 A，其中 I 和 J(0 ≤ I，J < E)分别代表一个过渡状态的起始状态和目的地状态。 L 表示从磁带读取到转换中的字符，T 表示在堆栈顶部找到的符号，A 表示在此转换结束时对堆栈顶部执行的操作(用于表示堆栈底部的字符堆总是Z.来表示字符串的结尾，或者不考虑栈顶的unstack Action ，对于过渡字符使用£)。堆栈的字母表将是大写字母。对于链 A，符号从右到左堆叠(与程序 JFlap 的方式相同，即新的栈顶将是左边的字符)。然后是 C 行，每行都有一个输入字符串。输入字符串可能包含小写字母和数字(不一定出现在任何转换中)。

每个测试用例的第一行输出必须显示以下字符串“Case G:”，其中G代表测试用例的数量(从1开始)。如果自动机接受该字符串，则在 C 行上打印单词“OK”，否则打印“Reject”。

例如:

Input:
2
3 5 1 0 5
2
0 0 1 Z XZ
0 0 1 X XX
0 1 0 X X
1 1 1 X £
1 2 £ Z Z
111101111
110111
011111
1010101
11011
4 6 1 0 5
3
1 2 b A £
0 0 a Z AZ
0 1 a A AAA
1 0 a A AA
2 3 £ Z Z
2 2 b A £
aabbb
aaaabbbbbb
c1bbb
abbb
aaaaaabbbbbbbbb

这是输出:

Output:
Case 1:
Accepted
Rejected
Rejected
Rejected
Accepted

Case 2:
Accepted
Accepted
Rejected
Rejected
Accepted   

我需要一些帮助，或者知道如何模拟这个 PDA，我不是在问我解决问题的代码，因为我想制作自己的代码(我的想法是学习对吧？？)，但我需要一些帮助(一些想法或伪代码)才能开始实现。

Answer 1

您首先需要一个数据结构来保持转换。您可以使用带有包含转换五元组的转换结构的 vector 。但是你可以使用状态是整数的事实并创建一个 vector ，它保持在索引 0，从状态 0 转换；在索引 1 处，状态 1 就是这样转换的。这样您就可以减少寻找正确转换的搜索时间。

对于stack，你可以很方便的使用STL库中的stack。您还需要搜索功能，如果您使用第一种方法，它可能会根据您的实现进行更改，您可以使用如下函数:

int findIndex(vector<quintuple> v)//which finds the index of correct transition otherwise returns -1

然后使用返回值得到newstate和newstack symbol。

或者您可以在 vector 和表示是否找到转换的 bool 标志上使用 for 循环。

在第二种方法中，您可以使用一个函数来引用新状态和新堆栈符号，并在您找到合适的转换时设置它们。

对于输入，您可以根据个人喜好使用 vector 或 vector 之类的东西。您可以使用 for 循环实现您的 main 方法，但如果您想要额外的困难，您可以实现一个递归函数。愿一切轻松。