在 c++ 中模拟确定性下推自动机 (PDA)
我正在阅读 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不考虑栈顶的动作，对于过渡字符使用
每个测试用例的第一行输出必须显示以下字符串“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，我不是问我一个可以解决问题的代码，因为我想编写自己的代码（这个想法是学习对吗？ ？），但我需要一些帮助（一些想法或伪代码）才能开始实施。
I was reading an exercise of UVA, which I need to simulate a deterministic pushdown automaton, to see
if certain strings are accepted or not by PDA on a given entry in the following format:
The first line of input will be an integer C, which indicates the number of test cases. The first line of each test case contains five integers E, T, F, S and C, where E represents the number of states in the automaton, T the number of transitions, F represents the number of final states, S the initial state and C the number of test strings respectively. The next line will contain F integers, which represent the final states of the automaton. Then come T lines, each with 2 integers I and J and 3 strings, L, T and A, where I and J (0 ≤ I, J < E) represent the state of origin and destination of a transition state respectively. L represents the character read from the tape into the transition, T represents the symbol found at the top of the stack and A the action to perform with the top of the stack at the end of this transition (the character used to represent the bottom of the pile is always Z. to represent the end of the string, or unstack the action of not taking into account the top of the stack for the transition character is used <alt+156> £). The alphabet of the stack will be capital letters. For chain A, the symbols are stacked from right to left (in the same way that the program JFlap, ie, the new top of the stack will be the character that is to the left). Then come C lines, each with an input string. The input strings may contain lowercase letters and numbers (not necessarily present in any transition).
The output in the first line of each test case must display the following string "Case G:", where G represents the number of test case (starting at 1). Then C lines on which to print the word "OK" if the automaton accepts the string or "Reject" otherwise.
For example:
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
this is the output:
Output:
Case 1:
Accepted
Rejected
Rejected
Rejected
Accepted
Case 2:
Accepted
Accepted
Rejected
Rejected
Accepted
I need some help, or any idea how I can simulate this PDA, I am not asking me a code that solves the problem because I want to make my own code (The idea is to learn right??), But I need some help (Some idea or pseudocode) to begin implementation.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您首先需要一个数据结构来保持转换。您可以使用带有包含转换五元组的转换结构的向量。但是您可以使用状态是整数的事实并创建一个保持在索引 0 处的向量，从状态 0 进行转换；在索引 1 处，像这样从状态 1 转换。这样您可以减少寻找正确转换的搜索时间。
您可以轻松地使用 stl 库中的 stack 进行堆栈。您还需要搜索功能，它可以根据您的实现进行更改，如果您使用第一种方法，您可以使用如下函数：
然后使用返回值来获取 newstate 和 newstack 符号。
或者您可以对向量和 bool 标志使用 for 循环，该标志表示是否找到转换。
在第二种方法中，您可以使用一个函数，该函数引用新状态和新堆栈符号，并在找到适当的转换时设置它们。
对于输入，您可以使用矢量或矢量之类的东西，具体取决于个人喜好。您可以使用 for 循环实现 main 方法，但如果您想要额外的困难，您可以实现递归函数。愿一切都容易。
You first need a data structure to keep transitions. You can use a vector with a transition struct that contains transition quintuples. But you can use fact that states are integer and create a vector which keeps at index 0, transitions from state 0; at index 1 transitions from state 1 like that. This way you can reduce searching time for finding correct transition.
You can easily use the stack in stl library for the stack. You also need search function it could chnage depending on your implementation if you use first method you can use a function which is like:
then use the return value to get newstate and newstack symbol.
Or you can use a for loop over the vector and bool flag which represents transition is found or not.
On second method you can use a function which takes references to new state and new stack symbol and set them if you find a appropriate transition.
For inputs you can use something like vector or vector depends on personal taste. You can implement your main method with for loops but if you want extra difficulties you can implement a recursive function. May it be easy.