问题标签 [automata]

我用python制作了一个IME（输入法编辑器）模拟器。它就像有限状态机，当输入来并输出在 python 程序上显示结果时。不知道结果如何一一显示，所以想请教一下如何像命令行样式一样显示。

问题是两件事，

1. 如何一一表达每个结果？
2. 如何实现“空格”或“退格”？

3. 输入“del（退格）键”时可以使用此代码吗？

   /li>

我很好奇是否有人知道如何编写程序以在给定有限自动化的情况下生成正则表达式，或者是否已经存在任何程序（最好在 c 中）。

为了让事情变得不那么复杂，我想将状态数限制在 4 个左右，假设 FA 是最小形式，并且 FA 只有一个 FinalState 和一个 StartState。

我已经考虑了一段时间，我认为要做的第一件事就是为 FA 创建一个转换表。

所以FA可能看起来像这样：

这将生成正则表达式： b + (ab*a(a + b))

我已经绞尽脑汁好几个小时了，但我不知道如何去做。非常感谢任何想法。

我需要帮助设计一个接受单词“hello”、“hello world”和“stay together”的 nfa，字母表包括英文字母表、数字和符号。我需要帮助开始。有人有什么建议吗？

如何为以下语言构建上下文无关语法：

我开始尝试：

然后A=别的东西......但我无法让它工作。

.

我想知道我们如何才能记住为 no 增加了多少 c 的 shud。b的增加？
例如：

我很难理解我们如何使用线性时间逻辑对这些自动机建模。有人可以请在此链接图片中的案例上向我解释这一点，或者将我指向一个在示例中解释这一点的来源。

我提前感谢您的帮助。

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

1. 线性语言：线性语法是可能的（⊆ CFG），例如
   L ₁ = {a ⁿ b ⁿ | n≥0}

2. 确定性上下文无关语言（D-CFG）：确定性下推自动机（D-PDA）是可能的，例如
   L ₂ = {a ⁿ b ⁿ c ^m | n ≥ 0, m ≥ 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 | w ∈ {a, b} ^* }
L ₃也是线性CFG。

--4。模棱两可的 CFL : only ambiguous CFG is possible
L ₄ = {a ⁿ b ⁿ c ^m |的 CFL n ≥ 0, m ≥ 0 } U {a ⁿ b ^m c ^m | n ≥ 0, m ≥ 0 }
L ₄既是非线性又是模糊 CFG 和每个模糊 CFL \subseteq N-CFL。

我的问题是：
是否所有非线性、非确定性 CFL 都是模棱两可的？如果不是，那么我需要一个非线性、非确定性 CFL 且明确的示例？

给定下面的维恩图：

也在这里问

NFA 和 epsilon NFA 的实时示例是什么，即除了它用于设计编译器之外的实际示例

我需要一些帮助来解决抽水引理问题。

这是我到目前为止得到的：

我让 y = abbc^n，n 是来自抽水引理的长度。y 在 L 中是因为 a:s 的数量小于 b:s 的数量，并且 b:s 的数量小于 c:s 的数量。

我让 u = a，v = bb 和 w = c^n。|紫外线| < y，如抽水引理中所述。如果我“抽” (bb)^2 那么我得到

这是正确的吗 ？我在“正确的道路”上吗？

谢谢

你能检查一下吗：https ://dl.dropbox.com/u/25439537/finite%20automata.png

这是一个检查作业，所以不要担心。我只是想澄清一下我的答案是否正确，因为它被我的老师标记为不正确。

我的答案是 ((a+b)(a+b))*a 第一个 (a+b) 表示上箭头。第二个 (a+b) 表示下箭头。最后一个'a'告诉我们它应该总是以'a'结尾。

我只是想记录很多专家的证据，以便我可以把它交给我的老师。

我使用 Hopcroft 算法将 DFA 转换为最小 DFA。我通过这个链接从维基百科找到了一个伪代码，http ://en.wikipedia.org/wiki/DFA_minimization#Hopcroft.27s_algorithm ，我制作了 python 代码来转换 dfa。

我的 DFA 包含五个指标，

我不知道为什么这个算法对我的代码不起作用，我的代码有什么问题吗？