我正在攻读我的计算语言测试,并且有一个想法我遇到了问题.
我知道常规语法更简单,不能包含歧义,但不能完成编程语言所需的大量任务.我也理解无上下文语法允许模糊,但允许编程语言(如回文)所需的一些东西.
我遇到的问题是通过了解常规语法非终结符可以映射到终端或非终结符后跟终端,或者无上下文非终结符映射到终端和非终结符的任意组合,从而理解我如何得到以上所有内容.
有人可以帮我把所有这些放在一起吗？
计算机是否可以通过用户提供的示例"学习"正则表达式？
澄清:
可能吗？我可以使用Google的算法,关键字等吗？
编辑:谢谢你的答案,但我对提供此功能的工具不感兴趣.我正在寻找理论信息,如论文,教程,源代码,算法名称,所以我可以为自己创造一些东西.
我需要学习如何设计DFA,以便给定任何数字'n',它接受二进制字符串{0,1},其十进制等效数可以被'n'整除.
不同的'n'会有不同的DFA,但有人可以给出一个基本的方法,我应该遵循任何数字0 <n <10.
我正在分析一个大型公共数据集,其中包含大量冗长的人类可读字符串,这些字符串是由一些常规(在形式语言理论意义上)语法明确生成的.
一个接一个地查看这些字符串集来查看模式并不太难; 不幸的是,大约有24,000个这些独特的字符串分为33个类别和1714个子类别,因此手动执行此操作有点痛苦.
基本上,我正在寻找一个现有的算法(最好使用现有的参考实现)来获取任意的字符串列表,并尝试推断一些可用于生成的正则表达式的最小化(对于一些合理的最小化定义)它们(即从该语法生成的语言中推导出一组有限字符串中的常规语法).
我已经考虑过重复贪婪最长的常见子串消除,但这只是到目前为止,因为除了完全匹配之外它不会崩溃,所以不会检测到,例如,在特定位置的变化数字串的常见模式语法.
暴力强迫任何不会脱离常见子串消除的东西是可能的,但可能在计算上不可行.(另外,我想过这个问题,有可能是一个"阶段排序"和/或子淘汰"当地最低"的问题,因为你可能会做出最终迫使最终语法贪婪的字符串匹配要少压缩/即使它看起来是最好的减少最小).
我喜欢我在Automata Theory和Formal Languages学习的课程,所以很自然地,我开始环顾互联网,了解自从课程所依据的书籍编写以来所发生的事情.
我发现的是我不熟悉的东西清单似乎很短.例如,从维基百科条目中的自动机列表中,该课程涵盖了一半,而另一半主要与课程未涵盖的一种语言相关.
此外,在研究理论的应用时,我得到了大致相同的结果:编程语言语法,编译器,文本搜索,以及......就此而言.
它真的死了吗？还是继续发展？这个理论有新的应用吗？
我使用这些规则制作了终极笑发生器.你能用聪明的方式用自己喜欢的语言实现它吗？
在每次迭代时,都会发生以下转换.
H -> AH
A -> HA
AA -> HA
HH -> AH
AAH -> HA
HAA -> AH
n = 0 | H
n = 1 | AH
n = 2 | HAAH
n = 3 | AHAH
n = 4 | HAAHHAAH
n = 5 | AHAHHA
n = 6 | HAAHHAAHHA
n = 7 | AHAHHAAHHA
n = 8 | HAAHHAAHHAAHHA
n = 9 | AHAHHAAHAHHA
n = ...
我手边有一个问题,我没有得到使用哪种设计模式.问题是这样的:
我必须构建一个具有'N'状态的系统,并且我的系统必须根据某些条件从任何状态转换到任何其他状态.例如:在条件1下,从状态1移动到3,在条件2上从状态1移动到4.
甚至从一个状态到另一个状态的转换也可以在两个或更多个不同的条件下完成.
例如,从状态1到状态3的转换可以在以下
情况下完成:条件1:"它是星期日"
条件2:"它的下雨"
条件3:"它的下雨和星期日"
在每种情况下,状态3的处理可以是不同.
我希望我能够清楚地理解这个问题.请帮助.
非常感谢
(有向)图表代表有限自动机.到目前为止,我的测试程序已经写出了用于测试的点文件.这对于回归测试(将验证的输出文件保存在subversion中,询问是否存在更改)和可视化都非常好.但是,有一些问题......
基本上,我想要一些可以从C++中调用的东西,它可以为我的状态和过渡计划一个布局,但是将绘图留给我 - 这将允许我绘制我想要的东西并在GUI(wxWidgets)窗口上绘制.
我还想要一个允许商业用途的许可证 - 我目前不需要它,我可能很好地作为开源发布,但我不想限制我的选择ATM.
GraphViz的问题是(1)关于在Windows上从源构建的警告,(2)用于呈现和解析的所有不必要的依赖性,以及(3)(假定的)缺少具体且纯粹用于布局的文档API.
基本上,我希望能够指定我的状态(具有边界矩形大小)和过渡,并读出每个过渡的状态和航点的位置,然后基于这些坐标自己绘制.我还没有弄清楚应该如何处理转换上的注释,但应该有一些规定来为那些指定边界框大小,将它们与转换相关联,以及读出位置.
有谁知道可以处理这些要求的库？
我不一定反对为自己实施某些东西,但在这种情况下,如果可能的话,我宁愿避免它.
我被要求显示DFA图和RegEx作为RegEx的补充(00 + 1)*.在之前的问题中,我必须证明DFA的补充是封闭的并且也是正则表达式,所以我知道要将DFA,M转换为补码,M`,我只需要交换初始接受状态和最终接受国家.
但是,似乎RegEx的初始接受状态是{00, 1, ^},最终接受状态也是{00, 1, ^}如此.因此,交换它们只会产生完全相同的RegEx和DFA,这似乎是相互矛盾的.
我做错了什么,或者这个RegEx应该没有真正的补充？
谢谢
如何在Python代码中实现dfa或nfa解决这个问题？
有什么好方法在python中做到这一点？他们曾经在现实世界的项目中使用过吗？