如何确定我的NFA是否正确?
显而易见的选择是耗尽所有可能的输入。我想我做到了。但我不太确定它是否有效,并且我没有违反任何非确定性有限自动机的规则。
我的 NFA 如下所示:(ab u aab u aba)*
下面是我的图表。
我错过了什么吗?
The obvious choice is to exhaust all possible inputs. I think I did. But I am not very sure whether it's valid and I didn't break any rules of non-deterministic finite automata.
My NFA is given by: (ab u aab u aba)*
and below is my diagram.
Have I missed something?
您不会遗漏任何东西,但 NFA 可以通过折叠路径和消除 λ 规则来大大简化。为了确定你的 NFA 是否决定了正则表达式表示的语言,你可以通过追踪转换图中的状态来非正式地争论。为了讨论 NFA,我将使用最终状态为 {q0,q3,q4} 和初始状态 q0
目标是表明NFA 完全接受语言 (ab U aab U aba)*。为此,我们可以考虑以 q0 处的 λ 开头接受的字符串,并通过图中穷尽所有可能的转换,记录通过连接转换的符号构建的字符串,并注意是否存在这样的字符串是否接受。图中的路径表示串联;最终状态表明接受或分离;循环表示克林星。
有更正式的方法可以表明给定的 NFA 决定一种语言。但最简单的方法是通过 NFA 穷尽所有可能的路径,在循环上引入 Kleene 闭包。形式化方法的一个示例是将 NFA 转换为正则表达式,然后以公理方式导出所获得的表达式与目标表达式的等式。这很大程度上是不必要的。
然而,您可能已经完全按照我刚刚写的内容进行操作,从而使整篇文章变得不必要。如果没有,我希望它展示了一种非正式的推理,你可以用它来说服自己 NFA 决定一种语言。
You aren't missing anything, but the NFA could be simplified considerably by collapsing paths and eliminating λ-rules. In order to determine whether your NFA decides the language denoted by the regular expression, you can argue informally by chasing states in the transition graph. In order to talk about the NFA, I'll use the following definition of the δ function with final states {q0,q3,q4} and initial state q0
The goal is to show that the NFA accepts precisely the language (ab U aab U aba)*. To this end, we can consider the strings accepted by beginning with λ at q0 and exhausting all possible transitions through the graph, recording the strings built by concatenating the symbols transitioned on, and noting whether such a string is accepted or not. Paths in the graph indicate concatenation; final states indicate acceptance or disjunction; loops indicate Kleene star.
There are more formal methods of showing that a given NFA decides a language. But the easiest way is to exhaust all possible paths through the NFA, introducing Kleene closures on cycles. An example of a formal method would be to convert the NFA to a regular expression, then derive the equality of the obtained expression and the target expression axiomatically. This is largely unnecessary.
You probably have done precisely what I just wrote, however, making this entire post unnecessary. If not, I hope it shows the kind of informal reasoning you can use to convince yourself that an NFA decides a language.