标签: automata-theory

找不到任何肯定的东西.任何epsilon过渡的NFA都是epsilon-NFA？谢谢.

我很难理解LR(1)中的前瞻原则 - 项目.如何计算先行集？

举个例子说我有以下语法:

S -> AB
A -> aAb | b
B -> d

然后第一个状态将如下所示:

S -> .AB , {look ahead}
A -> .aAb, {look ahead}
A -> .b,   {look ahead}

我知道前方是什么,但我不知道如何计算它们.我搜索了答案,但找不到一个简单解释这个问题的网页.

提前致谢

所以我正在研究我已经提出的下推自动机和无上下文语言的测试,我坚持这个结构.

我让这个自动机的每个部分都完全正常工作,除了我将在下面解释的一个部分.

它需要识别的语言是:{x#y#z#w | x,y,z,w在{0,1} +中,其中x≠w且y≠z}.

所以我遇到的问题是将Xi与Wi进行比较,因为Wi的元素在自动机处理W时是不知道的,就像我设计的那样.

如果我存储X的内容,当弹出时间并将每个元素与W的元素进行比较时,它们将以相反的顺序弹出,因此认为000111和111000是相同的字符串,而PDA将拒绝,当它应该明确接受(它们是不同的字符串).这只是一个例子,这也会导致错误地分析其他输入.

如果有一种方法可以按相反的顺序将X的内容压入堆栈,它们将以原始形式弹出,这样我就可以正确地比较字符串的内容.

如果在正常推送后有一种方法可以反转堆栈的内容,这也可以让我得出解决方案.

任何帮助将不胜感激.谢谢.

我正在尝试开发一种在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但是我不确定.

什么类型的语言被PDA接受,其中堆栈大小限制为20项？

在我看来它应该仍然是CFL,因为有一个临时存储器存储.

在所有图灵机扩展中(例如双向无限磁带,RAM,多个读/写磁头和非确定性),它们中的任何一个都允许TM来决定以前不可判断的问题吗？

有人可以帮我设计 PDA 吗？n<=m<=2n}。你能设计一个并附上解释吗？

我们都知道这(a + b)*是一种仅含有符号a和符号的常用语言b.但是(a + b)*是一个无限长度的字符串,它是规则的,因为我们可以建立一个有限的自动机,所以它应该是有限的.

有人可以解释一下吗？

OpenGL通常被描述为"状态机",因为据我所知,它包含可以通过其API设置的全局变量,并且它们可以更改/定义其行为.例如,可以设置当前颜色或变换矩阵.许多状态变量具有连续的值范围.

然而,据我所知,计算机科学中的"状态机"或"有限状态机"被定义为状态(作为节点)和转换(作为有向边)的有向图.

用于描述OpenGL的"状态机"术语是否与通用计算机科学中定义的"状态机"相同.