3

我已经定义了这个伪代码，用于使用松弛特里树识别字符串，其中函数 Next[u,x] 给出了具有来自 u 的 u 边的节点集（基本上是节点集，例如 (u,x,v)是 T 中的一条边）。

这里是：

U := {1};

while s ≠ λ and U ≠ Ø do


 U:= U in u Union Next [u, head(s)];
 s:= tail(s)
 od;

 if U ≠ Ø then
  if Final[u] for some u in U then
    Accept 
  else reject
  fi
 else
   reject
 fi

基本上我已经为循环定义了一个后置条件，并给出了一个循环不变量（我想我已经涵盖了这些元素，但如果你认为它有助于解释它，那就去吧）。

所以我需要给出一个简短的论据来说明为什么不变量是不变的（即当循环条件成立时，它是如何被循环体保存的）。

然后我需要扩展这个伪代码，以便它可以移动到一个新节点而不推进输入：

（我想我会通过添加另一个数组（比如 Null）来做到这一点，其中 Null[u] 是它可以从 u 移动到的状态集，而无需推进输入）

它还应该改变，使得在查看输入之前的每次迭代都可以从 U 中的状态到达所有状态，而无需推进输入。

感谢您的所有帮助，我发现这两个步骤非常困难，但认为我第一部分的伪代码很好

4

0 回答 0