英文:
Can a DFA have multiple of the same state?
问题
我需要创建一个DFA，用于表示状态的顺序，例如 A -> B -> C -> B -> A，以此类推，其中 'A' 是起始和结束状态，1 表示过渡到下一个状态，0 表示回到当前状态。1 和 0 是唯一的输入。
1.1 你被要求设计一个交通灯的计算模型，它有三种颜色，红色（r）、黄色（a）和绿色（g）。交通灯的顺序是 r → a → g → a → r，依此类推。考虑每个灯的等待时间是用二进制 0 标记的，而从一个灯切换到另一个灯则用二进制 1 标记。每个灯的等待时间是可选的，可以持续任意长时间。如果没有输入，交通灯保持为红色（r）。如果将红色（r）视为起点和终点，并且交通灯必须完成一个循环，那么，
1.1.1 绘制一个DFA，可以接受这个语言，考虑到给定的连续工作流程。
我找到的唯一一种方法是通过拥有2个B状态来按照这种顺序完成，这样可以吗，还是有其他方法可以做到这一点？
英文:
I need to create a DFA for a sequential order of states e.g. A -> B -> C -> B -> A
and so on, where 'A' is the start and finish state, 1 is a transition to the next state and 0 just loops back to the current state. 1 and 0 are the only inputs
Question below
1.1 You have been given the task to design the computational model for the traffic light
which operates with three colours, red (r), amber (a), and green (g). The sequential
flow of the traffic light is r → a → g → a → r and so on. Consider that the wait time
on each light is marked with the help of a binary, 0, and switching from one light to
another is marked by a binary 1. The wait on each light is optional and can continue
for any duration. If there is no input, the light remains red (r). If red (r) is considered
as your start and end point, and traffic lights must complete once cycle, then,
1.1.1 Draw a DFA which can accept this language considering the given workflow
in a continuous manner.
The only way I've found I can do it in this order is by having 2 B states, Is this ok or is there another way to do this?
答案1
得分: 1
一个DFA能够具有多个相同的状态吗？
一个DFA状态包括需要满足的条件列表，以触发转移到不同状态（例如，对于状态2，您可能有“如果接收到二进制1，转移到状态3”和“如果按下复位按钮，转移到状态1”）。如果DFA状态相同，那么这些触发条件也必须相同，这意味着重复的状态是多余的，并且可以被轻松丢弃。
然而，状态的“外部可观察”后果可能对不同的状态相同。例如，您可以有两个不同的状态，它们都具有“黄灯亮”的后果，但具有不同的触发条件和目标状态（例如，“如果接收到二进制1，转移到状态3”与“如果接收到二进制1，转移到状态1”）。
为了好玩，您可以添加一个行人的“行走/不行走”信号灯，如果信号灯为红色或“红色后的黄灯”，则设置为“行走”，如果信号灯为绿色或“绿色后的黄灯”，则设置为“不行走”。现在您仍然具有相同的4个状态，但在所有4个状态之间存在外部可观察的差异。
类似地，当进入每个状态时，您可以在计时器上设置不同的时间（例如，“红灯35秒，黄灯5秒，绿灯30秒，绿灯后的黄灯10秒”）。
英文:
> Can a DFA have multiple of the same state?
A DFA state includes a list of condition that need to be satisfied to trigger a move to a different state (e.g. for state 2 you might have "If binary 1 is received, move to state 3" and "If reset button is pressed, move to state 1"). If the DFA state is the same then these trigger conditions must also be the same, which means that a duplicate state is redundant and trivially discarded.
However; the "outwardly observable" consequences of a state may be the same for different states. E.g. you can have 2 different states that both have the "amber light is on" consequences, but have different triggers and target states (e.g. "If binary 1 is received, move to state 3" vs. ""If binary 1 is received, move to state 1").
For fun; you could add a "walk/don't walk" light for pedestrians that's set to "walk" if the lights are red or "amber after red", and set to "don't walk" if the lights are green or "amber after green". Now you still have the same 4 states but there's an outwardly observable difference between all 4 states.
In a similar way, when entering each state you might set a different amount of time on the timer (e.g. "red for 35 seconds, amber for 5 seconds, green for 30 seconds, amber for 10 seconds").
答案2
得分: 0
是的，就像Raymond Chen上面所说的，2个B状态是可以的，没有其他办法。
英文:
Yes, as Raymond Chen said above, 2 B states is this ok, there is no other way.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论