问题标签 [automata]

我在这方面考虑了很长时间，但仍然无法在这方面走得太远。第一步很容易考虑任何形式为 o^M 的语言，其中 M 是大于我们对手给出的素数（假设是 n）。我无法弄清楚我们如何从这里证明无论我们的对手如何打破字符串，我们总是可以泵送它以表明它不属于上下文无关语言类（因此不属于常规语言）。

PS：这不是作业问题。我已经完成了这门课程。只是想解决它，因为我在课程期间无法解决它。

我的任务是检查这种语言是否是常规语言：

我既找不到正则表达式，也找不到确定性（或非）有限状态自动机。另一方面，我没有找到任何方法来证明泵引理定理的反面。

有任何想法吗？

PDA接受哪些类型的语言，其中堆栈大小限制为 20 个项目？

在我看来，它仍然应该是CFL，因为有一个临时内存要存储。

我正在做某种自动机的组合。所以我想可视化/绘制组合自动机以更清晰。我已经在java中完成了编码。因此，任何人都可以建议任何可用于此的库或工具。我不知道该怎么做？

前段时间我写了一个像元胞自动机一样的 Wa-Tor（参见 Wikipedia），但是有更多的物种和更聪明的物种。除了进行大量微调以获得稳定的系统外，它非常简单并且运行良好。然而，从那时起，我问自己（现在是你）如何“真实地”更新单元格。

我的“世界”是一个网格，总是从左上角到右下角更新。IMO 这也意味着靠近顶部和左侧的单元格总是更快。因此，例如单元格 [3, 3] 中的一条鱼可以在更新之前被 [3, 2] 中的鲨鱼吃掉。如果单元格的位置相反，鱼总是会从鲨鱼身上逃脱，因为它可以在鲨鱼更新之前离开鲨鱼。

我是否正确认为这是一个“问题”（或至少不现实）？

IMO 在现实环境中应该同时更新所有单元格，但我不知道如何实现类似的东西。我可以想象的另一种方法是以“打乱”的顺序评估单元格。

你会如何解决这个问题/这些问题通常是如何解决的？

对于上述自动机，我的教科书中给出的正则表达式如下：

我无法得出这个...以下是我的尝试：

要么我错了，要么我无法将其简化为书中给出的形式。有人可以在这里指导我，指出错误或逐步向我解释吗？

我真的很感激和感激。

早些时候，我在这里问了一个问题，寻求将有限自动机的转移图转换为正则表达式的帮助：

理解（并形成）这个有限自动机的正则表达式

感谢用户 Patrick87，我能够找到我正在寻找的帮助。我还阅读了他在回答中提到的以下链接：

http://krchowdhary.com/toc/dfa-to-reg-exp.pdf

它解释了三种查找正则表达式的算法方法。直觉上，我被 Brzozowski 代数方法所吸引，并试图解决我在上一篇文章中寻求帮助的 FA，该问题在顶部提到。

以下是我为FA制作的特征方程。如果我错了，请告诉我并纠正我，并指出我正确的方向！

R1 = bR2 + aR3

R2 = aR2 + bR4

R3 = aR3 + bR2 + λ

R4 = aR4 + bR3

这些是正确的吗？如果是，那么我该如何进行替换，因为每个 Ri 都将根据 Rj 来表示，其中 i≠j。

请帮忙 :D

我以为我已经弄清楚了……但我仍然无法理解它。我正在玩 OpenFst 并试图弄清楚如何在“对数”半环中计算“最短距离”。对于下面的小自动机，

http://i.imgur.com/FThh6.png

“shortestdistance”命令的结果是，

并且日志中最短距离的描述为，

使用对数半环，计算到 q 的路径权重的 (log) 和。

我觉得自己很愚蠢，但我无法弄清楚最终 -2.6 到底发生了什么。我已经尝试了我能想到的对数和普通和的所有变体，即使是那些看起来不应该适用的变体，但没有任何结果产生-2.6。现在开始让我发疯了。

在这种情况下，我的直觉是两个不同字符串（bc，bd）中每一个的总路径概率应该相加，然后应该返回最佳概率。(bc) 有两条路径，它们的概率总和为 2/3（非对数）。(bd) 路径的概率为 1/3。但是，这绝对不是正在发生的事情，那么发生了什么？

如何在 Java 中创建可以接受自动机正则表达式和最小字符串长度（int）并生成可能的字符串的程序？

正则表达式的例子是

我是一名助教，被一名学生问到以下问题。尴尬的是，我无法想出答案，所以我求助于你们。

我们知道 L_1 = {a^nb^nc^n} 是非 CFL。我们也知道 L_2 = {a^ib^kc^j : i != k }是上下文无关的。

那些人的联合呢？（这显然是非常规的）它是上下文无关的吗？