何时使用＆＃xd8;对于DFA / NFA中的州

发布于 2025-01-23 19:16:17 字数 1353 浏览 3 评论 0原文

我对DFA / NFA中“Ø”的用法感到困惑（让我们在DFA到NFA转换的背景下谈论这一点），

synge 1的符号“ a”没有任何过渡。因此，在过渡表中，我会为“Ø”相同的过渡编写过渡，或者我写“ 1”，因为它将保持状态“ 1”，因为没有任何

箭头

|      state     |     a    |   b   |    E    | 
|----------------|----------|-------|---------|
|          1     |     Ø    |  {2}  |   {3}   |
|          2     |   {2,3}  |  {3}  |    Ø    |
|          3     |    {1}   |   Ø   |    Ø    |

过渡：

|      state     |     a    |   b   |    E    | 
|----------------|----------|-------|---------|
|          1     |    {1}   |  {2}  |   {3}   |
|          2     |   {2,3}  |  {3}  |   {2}   |
|          3     |    {1}   |  {3}  |   {3}   |

使用“Ø”的选择会影响最终输出。现在，我们可以构建状态的功率集，然后可以构建Colcualte Epsilon Clousure，但是让我们简要介绍一下，我们将直接看一下最终DFA中可能存在或可能不存在的有争议的状态，我们将尝试使用实验“Ø”，而不是使用“Ø”

1）不使用null ：（表2）

（

从1和2开始，在接收A时，我们转到1,2,3

epsilon闭合（1,2，1,2， 3）= 1,2,3

（2）使用null ：（表1）

状态= {1,2}

从1和2开始，我们转到{2,3}

epsilon闭合（2,3）= 1 ，2,3

现在，过渡看起来可能一样在最终输出“Ø”中具有额外的状态。在这种情况下，这只是意味着，如果我们没有某个符号的过渡，那么我们就会转到此状态，

但是如果我们没有的话，那么我们的最终输出就不会有额外的状态“Ø”。在这里，如果我们没有过渡，我们不会为某些符号指定过渡箭头，就像在状态1中的符号“ a”中，在图中

，这是正确的，一个是正确的，一个没有状态的”Ø “或一个国家“Ø”

原文

I am confused about the usage of "Ø" in the DFA / NFA ( Let's talk about this in the context of DFA to NFA conversion )

Let's say that I have a NFA as follows:
enter image description here

There isn't any transition defined for symbol "a" for state 1. So in the transition table would i write the transition for the same as "Ø" or do i write "1" cause it will stay in state "1" as there isn't any transition arrow for it

So would it be this:

|      state     |     a    |   b   |    E    | 
|----------------|----------|-------|---------|
|          1     |     Ø    |  {2}  |   {3}   |
|          2     |   {2,3}  |  {3}  |    Ø    |
|          3     |    {1}   |   Ø   |    Ø    |

or:

|      state     |     a    |   b   |    E    | 
|----------------|----------|-------|---------|
|          1     |    {1}   |  {2}  |   {3}   |
|          2     |   {2,3}  |  {3}  |   {2}   |
|          3     |    {1}   |  {3}  |   {3}   |

The choice to use "Ø" affects the final output. Now, we could construct the power set of the states and then calcualte epsilon clousure, but let's cut it short, we will directly Let's look at a controversial state that may or may not be present in the final DFA, and we will try experiment using "Ø" and not using "Ø"

(1) Not using null: ( Table 2 )

State = {1,2}

From 1 and 2, on receiving a we go to 1,2,3

epsilon closure (1,2,3) = 1,2,3

(2) Using null: ( Table 1 )

State = {1,2}

From 1 and 2, on receiving a we go to {2,3}

epsilon closure (2,3) = 1,2,3

Now, the transition might look same but in some cases we would end up again with states where we don't have anywhere to go but to stay in the same state and if we choose to use "Ø" then we would have an additional state in the final output "Ø". In this case, it just means that if we don't have a transition for some symbol then we go to this state

But if we don't then our final output won't have the extra state "Ø". Here we don't specify the transition arrow for some symbol if we don't a transition for it, just like as for symbol "a" in state 1, in the diagram

So, which one is correct, one without the state "Ø" or one with the state "Ø"

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

绳情 2025-01-30 19:16:17

一个与Ø。考虑一个简单的NFA：

  /-> S -a-> (T)
  |   |
  \-a-/

S是开始状态，T是一种接受状态。字母为{a，b}。

当这台计算机读取字符串b时，它会拒绝。如果（s，b）的过渡集为{s}，则转换为dfa将接受ba，这显然是错误的。

正确的过渡状态如下：

S, a, {S, T}
S, b, Ø
{S, T}, a, {S, T}
{S, T}, b, Ø
Ø, a, Ø
Ø, b, Ø

您可以通过两种方式绘制此DFA。不完整的DFA（省略零状态）或完整的DFA（以零状态为不可避免的状态）。 q1 = {s}，开始状态，q2 = {s，t}，接受状态。

Incomplete:
q1 -a-> (q2)<-\
          |   |
          \-a-/

Complete:

    /a,b\
   |    /
    \  v
 /-> q3 <-\
 b        b
 |        |
q1 -a-> (q2)<-\
          |   |
          \-a-/

请注意，在完整版本中，Q3具有与Ø相同的属性。

（通常，不完整的DFA总是可以以这种方式替换为完整的DFA：创建一个新的非接受状态d，其传出过渡为d，σ，D ，其传入的过渡是原始DFA中缺少的任何过渡由于输入通往该状态，因此没有接受的途径，因此可以被拒绝。）

The one with Ø. Consider a simple NFA:

  /-> S -a-> (T)
  |   |
  \-a-/

S is the start state, T is an accepting state. The alphabet is {a, b}.

When this machine reads the string b, it rejects. If the transition set for (S, b) were {S}, then the DFA this converts into would accept ba, which is obviously wrong.

The right transition states are as follows:

S, a, {S, T}
S, b, Ø
{S, T}, a, {S, T}
{S, T}, b, Ø
Ø, a, Ø
Ø, b, Ø

And you could draw this DFA in two ways. A incomplete DFA (where the null state is omitted) or a complete DFA (where the null state is present as an inescapable state). q1 = {S}, the start state, and q2 = {S, T}, the accepting state.

Incomplete:
q1 -a-> (q2)<-\
          |   |
          \-a-/

Complete:

    /a,b\
   |    /
    \  v
 /-> q3 <-\
 b        b
 |        |
q1 -a-> (q2)<-\
          |   |
          \-a-/

Note that in the complete version, q3 has the same properties as Ø.

(In general an incomplete DFA can always be replaced with a complete DFA in this manner: create a new non-accepting state d, whose outgoing transitions are d, Σ, d, and whose incoming transitions are whatever transitions are missing from the original DFA. d is the "dump" state, and can be thought of as a "rejecting" state as opposed to an accepting state. As soon as an input leads into that state, it has no path to acceptance and so can be rejected.)

回复收藏 0 原文

~没有更多了~