regex - 带有 epsilon 转换的 NFA 让我们做什么？

Question

我有以下自动机。我应该通过它了解空转换的使用。

我认为这个自动机的正则表达式如下： 0* 1* 2*

我只想知道这个自动机让我们做什么？换句话说，在这种情况下，空转换有什么用？

Answer 1

没错，您的自动机描述了 0*1*2*。q ₀是处理一系列（可能是空的）0 的地方。q ₁是处理一系列（可能是空的）1 的地方。通过从q ₀到q ₁的空转换，在 0 和 1 之间不需要任何字符。

空转换不允许您描述任何没有它就无法描述的语言。但是，只需尝试修改您的自动机以不使用空转换。这是可能的，但它需要更多的转换，它需要使每个状态都成为最终状态，当你完成时，你希望看到它使分辨正在描述的语言变得更加困难。

所以使用空转场是为了让你的自动机更容易理解。

Answer 2

我想你想知道这之间的区别..

和这个

区别是第一个自动机接受字符串 0,1 和 2 的任何东西......而第二个自动机接受字符串 0,1 和 2 of ...0，然后是 1,1，然后是 2.... 例如。它接受 012,001122,0012,0112 等。它不接受 102,201,0121,0120,0011221。

所以空的过渡使它变得又好又容易......