标签: finite-automata

我正在寻找一个免费的工具来创建有限自动机和语法树的视觉吸引力的图表.
注意:我真的只想绘制图表.我没有必要创建一个模型或做一些花哨的东西.

谢谢你的时间.

编辑:
我可能会补充说,我在Latex中创建文档,因此我也对基于tex的图表解决方案持开放态度.

以图的形式构造确定性有限自动机的规则是什么？我的教授通过例子解释,但我不确定所有图表必须遵循哪些规则.任何帮助表示赞赏,谢谢!

以下正则表达式是否等效为真？为什么或者为什么不？

(ab)* u (aba)* = (ab u aba)*

*= Kleene明星

你=联盟(集合理论)

我正在从Aho的编译器构造中读取有限自动机和语法,并且我长期坚持使用这种语法.我对如何描述它没有明确的认识:

考虑以下语法:

S - >(L)| a L - > L,S | 小号

请注意,括号和逗号实际上是该语言的终端,并出现在此语法接受的句子中.尝试描述该语法生成​​的语言.这个语法是不明确的？

我关注的是:这种语法生成的语言能否被描述为正则表达式？我对如何做到这一点很困惑.有帮助吗？

我有一个函数,它接受一个输入字符串,然后通过几个正则表达式运行字符串,直到找到匹配.找到匹配后,我返回一个输出,该输出是原始字符串和匹配的函数.所以在红宝石中:

str = "my very long original string ... millions of characters"
case str
  when regex1
    do_something1(str,$1)
  when regex2
    do_something2(str,$1)
  when regex3
    do_something3(str,$1)
  ...
  when regex100000
    do_something100000(str,$1)
  else
    do_something_else(str)
end

现在,Ruby实际上是在优化这个开关循环,以便str只被遍历一次吗？假设它不是,那么使用嵌入了回调的一个很长的正则表达式可以更有效地执行此功能.像这样的东西:

/(?<callback:do_something1>regex1)|
(?<callback:do_something2>regex2)|
(?<callback:do_something3>regex3)|
   ...
(?<callback:do_something100000>regex100000)/

是否有任何技术可以做到这一点？

我目前正在尝试学习如何手动创建自己的词法分析器.我一直在使用Flex(和Bison一起)练习并学习它如何在内部工作,但我目前至少看到了3种不同的解决方案来开发我自己的.

1. 使用RE列表,遍历每个RE,当一个匹配时,只需返回相关的令牌(参见关于RE的python文档)
2. 从RE创建DFA(例如Flex;基于RE,创建一个大型状态机)
3. 用很多switch case或if语句创建我自己的'状态机'(我认为Lua就是这样做的)

我相信我可以尝试每种解决方案,但是:

• 是否存在一种解决方案无法解决的问题？
• 在什么情况下你会使用一个解决方案而不是另一个？
• 正如标题所说:哪一个产生最有效的代码？

提前致谢!