标签: finite-automata

当我在感恩节后回到学校时,我将学习CS理论课程,内容包括确定性和非确定性有限状态机,图灵机,下推自动机和其他一些东西.但是,我还没有找到一个好的应用程序,可以生成它们的可视化表示,以及测试它们的工作方式(通过/失败等).到目前为止我发现的最好的是jFlap,我觉得它很尴尬.

你可以在我询问有关机器应用程序的最佳架构的情况下阅读这个问题,虽然对于帮助我解决这个问题并不是完全必要的.

我对有限状态机的理解(特别是对于实现)有点年轻,可能缺乏一点,但我正在实现这个应用程序,我有一个地方需要有一个嵌套的FSM.基本上这台机器有一些高级状态(冷[又刚启动],归位,设置,准备运行,运行,报告,重新设置)但是当机器运行时,它需要有自己的小FSM实现(加载Lense,定位边缘,测量楔形,测量圆度和完整[可能在那里更多]).

我的问题是:我是否应该建立具有"嵌套状态"的能力,其中状态可以有一个子状态列表,系统可以进入这些子状态,那些子状态可以返回到父状态？或者我应该将FSM实现放在Running状态中,并将它们保存为两个不同的FSM？或者你认为我在做什么或者在想某些愚蠢的东西并且应该重新思考它？

欢迎提出想法,建议,批评和建议.

我想测试两种语言是否有共同的字符串.这两种语言都来自下面描述的常规语言的子集,我只需要知道两种语言中是否存在字符串,而不是产生示例字符串.

该语言由类似glob的字符串指定

/foo/**/bar/*.baz

其中**匹配0个或更多字符,并*匹配零个或多个不是的字符,/所有其他字符都是字面值.

有任何想法吗？

谢谢,迈克

编辑:

我实现了似乎表现良好的东西,但尚未尝试正确性证明.您可以看到源和单元测试

鉴于:

我不知道接受的语言是什么.

从它看,你可以得到几个最终结果:

1.) bb
2.) ab(a,b)
3.) bbab(a, b)
4.) bbaaa

给定两个非确定性有限自动机M1和M2,是否有一种有效的算法来确定M1接受的语言是否是M2接受的语言的超集？

我想绘制一个带有边缘和圆形状态的自动机,像这样http://pop-art.inrialpes.fr/~girault/Cours/Automates/td5.html,你有一个例子吗？

在正式语言的乔姆斯基分类中，我需要一些Non-Linear, Unambiguous and also Non-Deterministic上下文无关语言（N-CFL）的例子吗？

1. 线性语言：对于哪些线性文法是可能的（？CFG）例如
   L ₁ = {a ⁿ b ⁿ | ? 0 }

2. 确定性上下文无关语言（D-CFG）：对于哪些确定性下推自动机（D-PDA）是可能的，例如
   L ₂ = {a ⁿ b ⁿ c ^m | ? 0，米？0 }
   L ₂是明确的。

非线性的CF 文法是非线性的。
L _nl = {w: n _a (w) = n _b (w)} 也是一个非线性 CFG。

-- 3. Non-Deterministic Context Free Language(N-CFG) : 对于哪个only Non-Deterministic Push-Down-Automata(N-PDA)是可能的，例如
L ₃ = {ww ^R | ? {a, …

鉴于以下语言:

L1 = { (ab)n | n ≥ 0 }

那是, L1 = { ε ab, abab, ababab, abababab, ... }

问题是要找到什么语言.L12

我的猜测是它等于.那是对的吗？如果是这样,我该如何证明呢？如果没有,为什么不呢？{ (ab)2n | n ≥ 0 }

谢谢!

我读到每个非确定性有限自动机（NFA）都可以转换为确定性有限自动机（DFA）。这可以为 kleene star regex 完成吗，比如 a* ？

以上是 a* 的 NFA。

我试图了解如何从正则表达式创建 NFA-s，但我对 epsilon 转换感到非常困惑。我的教科书中有这个例子，但我不明白为什么使用 epsilon 转换以及如何知道何时使用它们。