gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:58:10 30 4
gpt4 key购买 nike

我正在阅读 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,我不是在问我解决问题的代码,因为我想制作自己的代码(我的想法是学习对吧??),但我需要一些帮助(一些想法或伪代码)才能开始实现。

最佳答案

您首先需要一个数据结构来保持转换。您可以使用带有包含转换五元组的转换结构的 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 方法,但如果您想要额外的困难,您可以实现一个递归函数。愿一切轻松。

关于c++ - 在 C++ 中模拟确定性下推自动机 (PDA),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6683489/

30 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com