2

我正在尝试为 Java 中的图灵机模拟器程序提出大型测试用例。

该程序从输入文件中读取数据并根据测试用例字符串和图灵机规则列表运行模拟。执行以下规则后，程序将打印字符串是否被接受、拒绝或在给定数量的步骤中不停止。

该程序基本上是在给定一些输入字符串的情况下，在纸上手动通过图灵状态机的模拟。

我发现测试这个程序很困难。该程序适用于所有基本的图灵机和相对较小的测试用例。我想测试这个程序，给定一个非常大的测试字符串（约 30 个字符）、5000 个步骤以及一些大数字或规则和状态。

我想知道是否有人可以帮助我为此提出一个好的测试用例？

示例测试用例

7 15 //number of states and number of rules
0 0 3 B R //[current state, transition character, destination state, value to write, direction to move]
0 B 2 B R
0 x 2 x R
3 x 3 x R
3 B 1 B R
3 0 6 x R
6 x 6 x R
6 0 4 0 R
6 B 5 B L
4 x 4 x R
4 B 2 B R
4 0 6 x R
5 0 5 0 L
5 x 5 x L
5 B 3 B R
3 15 //number of testcases and number of steps to come to a halt
00
000
000000

提前谢谢了

4

1 回答 1

2

如果您正在寻找测试用例来对您的实现进行压力测试，您可能需要查看繁忙的海狸图灵机，它们是具有指定数量的状态和已知运行时间最长的磁带符号的图灵机在终止之前。我们知道这些机器完成运行所需的确切时间，因此您应该能够在已知会占用大量时间和空间的 TM 上测试您的模拟器，并确认您的计步器工作正常。

希望这可以帮助！

于 2013-02-24T18:57:39.177 回答