标签: finite-automata

我想在C中构建一个词法分析器,我正在关注龙书,我可以理解状态转换但是如何实现它们？

有更好的书吗？

事实上,我必须通过多个状态解析字符串,以便我可以判断字符串是否可接受!

我正在复习关于计算理论的课程的一些注释,我有点坚持展示以下声明,我希望有人可以帮我解释一下:)

让A成为常规语言.语言B = {ab | A中存在a和b中不存在a*}为什么B是常规语言？

有些观点对我来说很明显.如果b只是一个常量字符串,这是微不足道的.由于我们知道a中的a和b是字符串,因此常规语言在union下关闭,因此联合接受这两个字符串的语言显然是常规的.但是,我不确定b是不变的.也许是,如果是的话,那么这不是一个真正的问题.我很难理解它.谢谢!

用于解析字符串的引擎(在Perl中称为"正则表达式")与书中术语"正则表达式"所知的非常不同.

所以,我的问题是:是否有一些文档描述了Perl的regexp实现,以及它与经典实现有何不同之处(通过经典我的意思是可以真正转换为普通DFA/NFA的正则表达式)以及如何有用？

谢谢.

假设我有两个确定性有限状态自动机，由以下转换图表示：

关键字 IF 的 FSA： IF

  ___        ___         _
 /   \  I   /   \  F   // \\
>| 0 |----->| 1 |----->||2||
 \___/      \___/      \\_//

ID 的 FSA： [AZ][A-Z0-9]*

            ------------
  ___       | _    LET |
 /   \ LET  // \\<------
>| 0 |----->||1||
 \___/      \\_//<------
            |      NUM |
            ------------

我可以使用什么算法将它们组合成具有三个最终状态的单个确定性有限状态自动机，由以下转换图表示：

            -----------------------
            | LETTER BUT F OR NUM |   --------
  ___       | _          _   LET  v _ |  LET |
 /   \  I   // \\  F   // \\----->// \\<------
>| 0 …

在DFA中,我们可以通过执行两个自动机状态的交叉乘积并接受在初始自动机中接受的那些状态来完成两个自动机的交集.联盟的表现同样如此.虽然我可以轻松地使用epsilon过渡在NFA中进行联合,但我如何做他们的交集呢？

我正在尝试开发一种在Java中执行非确定性有限自动机的模拟.第一个命令行参数是定义机器的文本文件.第二个参数是输入字符串.如果它接受字符串,则打印到标准输出"accept",然后是可以结束的接受状态列表.如果它拒绝,则输出"reject",然后输出所有可能的结束状态列表.

例如,文字:

state   1   start
state   2
state   7   accept
transition  1   0   1
transition  1   1   1
transition  1   0   2
transition  2   0   2
transition  2   0   1
transition  2   1   1
transition  2   0   7
transition  7   0   7
transition  7   1   7

看起来像:

输入字符串为10将输出

reject 1 2

并输出一个输入字符串000

accept 7

我需要建议使用什么数据结构.我想过使用hashmaps和sets但是我不确定.

我是一名学习 DFA 的学生，正在寻找一个可以查找十进制数是否能被 7 整除的 DFA。

今天我已经解决了数字 2,3,4,5,6,8,9 的整除问题，但我无法解决数字 7 的这个问题。我在网上搜索过，但找不到任何帮助我的答案或者对我来说是可以理解的。

所以现在我来这里寻求帮助。提前致谢。

我搜索了谷歌,并在许多页面中给出了最小化DFA死状态或陷阱状态被删除.我的问题是,如果某些转换未定义,它仍然是一个DFA.那么你说的人呢？

给定任意上下文无关语法，我如何检查它是否描述了常规语言？

我不是在寻找考试“技巧”。我正在寻找一种可以编写代码的万无一失的机械测试。

如果有帮助的话，这里是我可能会收到作为输入的 CFG 示例。具体来说，请注意，答案一定比仅仅寻找左递归或右递归复杂得多，因为另一种类型的递归的存在并不自动意味着语法是不规则的。

S: A B C D X
A: A a
A:
B: b B
B:
C: c C c
C: c
D: D d D
D: d
X: x Y
X:
Y: y X
Y:

按照标题：

L = {（（n _a（w）-n _b（w））mod 3> 0}

字母= {a，b}

我找到了这个问题的两个答案：

在此解决方案中，我们的语言被接受。

然而，

w = b

也被接受。

在下一个解决方案中：

我们的问题

w = b

在这里解决了，但是

w = aaab

不被接受。

我该如何解决这个问题？我在互联网上找不到合适的答案。