0

我正在自学正式语言（Aho's，Hopcroft），但我很难使用正则表达式。

我已经能够处理简单的任务，但这一项已经构成了挑战，至少对我来说是这样。如果你不能算到现在怎么解决这个问题，我不习惯这种类型的计算。
一定有一些属性或东西可以让我概括答案，我可以把它作为一个常规表达式。

到目前为止，我已经设计出至少有 2 到 3 种情况：

  • 如果 sum=3k，则求和 mod3=0
  • 如果 sum=3k+1，则求和 mod3=1
  • 如果 sum=3k+2，则求和 mod3=2。

但是我已经意识到，可能有很多组合会发生求和，所以找不到正则表达式必须遵循的模式。

ex的字符串。（大括号是为了便于阅读）如果总和是字符串中的“10”，则{122211}0末尾有零。情况可能是这样的，所以必须在最后，依此类推。{sum=3k}0{1222111}1{sum=3k+1}

这可能是解决问题的正确途径，也可能不是解决问题的正确方法，但我愿意接受任何建议，非常感谢任何帮助。

4

1 回答 1

0

这里有一个提示：想想你可能处于什么不同的最终状态。你肯定至少有 3 个状态，因为值的数量可以是三个不同的东西 mod 3。此外，您需要有一个不同的开始状态，因为不能接受空字符串。你需要更多的州吗？

提示 2：我认为你可以使用 DFA 轻松地做到这一点，它使用一个起始状态和九个其他状态，其中三个将被接受。

编辑：一旦你有一个 DFA，你可以使用 Kleene 定理来构造一个等效的正则表达式。如果您更愿意直接使用正则表达式，这里有另一个提示：如果您正在查看长度为 3k 的任何字符串，您可以追加：0; 任何长度为 1 的字符串，后跟 1；任何长度为 2 的字符串，后跟 2。因此，如果您可以为长度为 3k、1 和 2 的字符串编写正则表达式，那么您实际上就完成了。

于 2012-02-04T13:15:10.790 回答