问题标签 [automata]

有谁知道 C# 中有任何好的 NFA 和 DFA 实现，可能还实现了两者之间的转换？我希望能够构建一个 NFA，然后将其自动转换为 DFA，而不必编写我自己的代码，这将花费很长时间。有这个Python 代码，也许我可以使用 IronPython 并与 C# 集成，但是 Python 很慢。

我有一个任务，我需要拍摄一些现有的照片[显示一些自动机（DFA、NFA、图灵机）]，并以某种方式将它们转换为一种格式，这使我能够使用数据将其表示为自动机以及将其编译成一些图形表示。你们中有人做过类似的事情吗？是否有任何 Python 库/框架可以让我以图形方式呈现一些自动机数据？

我想问是否有算法（也已经实现）来检查交替自动机的空性，特别是弱交替自动机。

我正在尝试从有限自动机构造一个正则表达式，但发现我自己完全被这个所困扰。要使用的正则表达式是这样的：

? = 0 或 1
* = 0 或更多
+= 1 或更多
| = 或
_ = 空字符串
@ = 空集
() = 括号

据我了解，字符串必须是以“a*”结尾的“b*”或以“a+bb+”结尾
我现在拥有的是((b*(a+(bb))*)*) ，但这并没有考虑到以“a”结尾的字符串。

如前所述，我 100% 坚持这一点，只是无法理解我应该如何处理这个问题。

图片：http: //img593.imageshack.us/img593/2563/28438387.jpg

代码：
自动机
FA 的类型

州
q1
q2
q3
q4

字母
a
b

初始状态
q3

最终状态
q3
q4

过渡
q1 a q2
q1 b q3
q2 a q2
q2 b q2
q3 a q4
q3 b q3
q4 a q4
q4 b q1

任何解决方案或提示表示赞赏！

图灵机如何实现队列？

有人能告诉我换能器与 NFA 有何不同吗？

我正在阅读 Peter Linz 的一本名为“形式语言和自动机简介”的书。在它的一个问题中，它要求我，"Design an acceptor for integers in a programming language C"有人可以告诉我如何获得这个答案。任何帮助将不胜感激

我正在阅读一本关于自动机理论的书，书中给出了一个示例，即具有相同数量的 0 和 1 的语言与 1*0* 相交会导致 1n0n，其中 n > 0

所以我的问题是，我怎样才能找到一些与 1*0* 相交时也会产生 1n0n 的常规语言。有没有办法考虑这个？

更新：感谢您的回答！我想我想要找到的是一些常规语言，所以像 1n0n 这样的语言是行不通的；）有可能吗？有任何想法吗？

我正在研究一些测试准备材料并坚持这个问题。

显示 L = {we {a,b}*: w = wR 且每个 a 都紧跟 ab} 的上下文无关文法。

wR 是相反的 w。所以，在英语中，每个“a”后面跟着一个“b”的回文，使用任意数量的a和b。

到目前为止，我得到了这个反向部分，但我不知道如何合并每个 a 后跟 ab 部分，同时确保回文属性仍然有效。

任何帮助是极大的赞赏！

不太确定这是否是正确的论坛，但在理论计算机科学上建议我将它移到这里......

有限状态机的典型字母大小是多少？

我目前正忙于实现一个高性能的 FA 库，在继续之前需要做一些设计考虑。我的状态空间将按 2 147 483 647 ( Integer.MAX_VALUE) 的顺序排列，我觉得这已经绰绰有余，即使对于非一般用途也是如此。现在，剩下的就是字母空间。

假设字母表通常只由所有可显示的字符组成（在这种情况下，它可以存储为 abyte会带来非常好的性能），这有什么好处吗？还是应该将字母符号翻译成Strings，以便您拥有字母标签？在这种情况下，我需要保留一个将 aString转换为 a或的 Map int，具体取决于我想要制作的大小。shortbyte