这个问题可能听起来有些陈词滥调,但我处于这种情况.
我正在尝试实现一个有限状态自动机来解析C中的某个字符串.当我开始编写代码时,我意识到如果我使用标签来标记不同的状态并使用goto从一个状态跳转到另一个案件来了.
在这种情况下使用标准的break和flag变量非常麻烦,很难跟踪状态.
什么方法更好？最重要的是,我担心这会给我的老板留下不好的印象,因为我正在实习.
这不是一个家庭作业问题.我正在看这个系列讲座而且很好奇.
如何在Python代码中实现dfa或nfa解决这个问题？
有什么好方法在python中做到这一点？他们曾经在现实世界的项目中使用过吗？
众所周知,如何从常规语言的NFA到最小的DFA.但是,DFA可能具有指数级更大的州.
我需要的是一种减少NFA的方法,再次给出一个NFA但具有较少数量的状态.Ti我不需要结果是确定性的,但我希望它保持尽可能小,同时保留公认的语言(可能不是绝对最佳,但越小越好).
这个问题的最佳算法是什么？或者也许不是"最好的",但至少"最容易实现非极端效率"？或者问题是否有一个众所周知的名称,以便我自己能找到好的信息来源？
regex language-agnostic algorithm computer-science finite-automata
Marvin Minsky在口语考试中问我以下问题:
作为蚂蚁行走,它每次执行步骤时都会打印二进制数(例如,101).什么是最小长度,以数字为单位,二进制数可以是什么,可以告诉蚂蚁行进的方向而不查看字符串的开头或结尾？蚂蚁告诉你二进制数.
示例:蚂蚁的二进制数为101,因此,蚂蚁会留下如下所示的路径:101101101101101101101.请注意,无法确定蚂蚁的行进方式.因此,这个特定的数字不起作用(但可能有三位二进制数).
示例:蚂蚁的二进制数是011,因此,蚂蚁留下如下所示的踪迹:011011011011011011.再次,没有办法在不查看字符串末尾的情况下判断蚂蚁的行进方式.
这个问题的答案是什么？请注意,答案不仅仅是二进制数的一个例子.答案需要包括一个证明,即长度小于n-1的二进制数将起作用,其中n是有效的示例二进制数的长度.详尽的枚举证明是可以的,但令人不快.:)
考虑以下FST:
T1
0 1 a : b
0 2 b : b
2 3 b : b
0 0 a : a
1 3 b : a
T2
0 1 b : a
1 2 b : a
1 1 a : d
1 2 a : c
如何在这两个FST上执行合成操作(即T1 o T2)我看到了一些算法,但是不太了解.如果有人能够以一种简单的方式解释它,那将是一个重要的帮助.
请注意,这不是作业.这个例子来自给出解决方案的演讲幻灯片,但我无法弄清楚如何实现它.
有人可以比我更简洁地向SO社区描述NFA到DFA的转换算法吗？(最好是500字以内.)我见过的图表和讲座只会让我以为我曾经认识的东西感到困惑.我最有信心从状态图生成初始NFA转换表,但之后,我丢失了epsilons和子集中的DFA.
1)在转换(delta)表中,哪一列代表新的DFA状态？它是生成状态的第一列吗？
2)在下面我的例子的第{2,3}行中,{2,3}在状态图方面对NFA的意义是什么？(对不起,我必须在图片中思考.)我认为这将是DFA中的"输入0回环"？
3)从表格到DFA或识别所得到的DFA的接受状态的任何简单的"经验法则"？
有限自治
delta | 0 | 1 |
=======+=======+========+
{1} |{1} |{2} |
{2} |{3} |{2,3} |
{3} |{2} |{2,4} |
{2,3} |{2,3} |{2,3,4} |
{2,4} |{3,4} |{2,3,4} |
{2,3,4}|{2,3,4}|{2,3,4} |
{3,4} |{2,4} |{2,4} |
编辑:这是上面的点格式表,欢呼Regexident.
digraph dfa {
rankdir = LR;
size = "8,5"
/* node [shape = doublecircle]; "1";*/
node [shape = circle];
"1" -> "1" [ label = "0" ];
"1" -> "2" [ label = "1" ];
"2" -> "3" [ …首先,这不是要求算法将NFA转换为DFA的问题.
众所周知(并且证明)NFA的等效DFA最多有2 n个状态,即使大多数时候它与NFA的状态数或多或少相同.
我如何预测NFA等效DFA所具有的州数量？哪种特定类型的NFA需要等效DFA才能拥有2 n个状态？
我之所以提出这个问题,是因为能够"发明"一些肯定会产生的NFA,而不考虑最小化,2 n - 1个状态加上"死态".
找不到任何肯定的东西.任何epsilon过渡的NFA都是epsilon-NFA？谢谢.