我们如何为 n,m > 0 的 a^n b^(nm) 构建图灵机

Question

我们如何为语言 L = {a^n b^nm where n>0) 构建图灵机。我无法理解n.m部分的设计部分。

Answer 1

堆栈溢出不会帮你做作业。

但至少给你一个开始。尝试编写一个 TM 来执行以下操作：

0. 确保字符串的形式为

   a+b*

   。
1. 如果不再有

   b

   ，则成功。
2. 对于字符串开头的每个

   a

   ，删除字符串末尾的

   b

   。
3. 如果在删除过程中用完

   b

   ，则失败
4. 否则，返回步骤 1。