标签: automata

我正在学习有限的自动机和语法测试,我坚持这个问题:

Construct a grammar that generates L:
L = {a^n b^m c^m+n|n>=0, m>=0}

我相信我的作品应该遵循以下方针:

    S->aA | aB
    B->bB | bC
    C->cC | c Here's where I have doubts

我的C作品如何记住m和n的数量？我猜这必须是一个无上下文的语法,如果是这样,应该怎么做？

有人能告诉我传感器与NFA的不同之处吗？

美好的一天堆栈溢出.

我是使用正则表达式的菜鸟,这是我的问题 - 如果密码包含4个连续字符,我需要检查密码.到目前为止,我刚刚介绍的是数字.这是我的正则表达式:

升序数字 - ^.？(？:0123 | 1234 | 2345 | 3456 | 4567 | 5678 | 6789).$

降序数字 - ^.？(？:9876 | 8765 | 7654 | 6543 | 5432 | 4321 | 3210).$

这仅适用于数字.我知道这已经是正则表达式的一种矫枉过正,所以我不想用字母来做.如果我这样做,那将是太过分了.

abcdblah //因为abcd而是真的

helobcde //因为bcde是真的

dcbablah //真的是因为dcba

heloedcb //因为edcb而是真的

任何帮助将受到高度赞赏.谢谢stackoverflow.

我在ANTLR语法中有2个简单的词法分析器规则：

fragment Attrs : '.' ARCH; 
fragment ARCH : 'IA32' | 'X64' | 'IPF' | 'EBC' | 'common';

使用ANTLR4.7生成的ATN如下所示：

我searhed约ATN一定的参考，比如这一个。

很漂亮，但我不明白：

• 节点中的数字和标签是什么意思？
• 箭头线上的epsion符号是什么意思？
• 灰色和红色节点是什么意思？

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

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

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

如果您已经拥有算法的伪代码,它们是否有助于描述图灵机的功能？

我正在学习复杂性理论课程,我花了一些时间来描述一个决定或接受某种语言(状态,转换等)的图灵机器,即使我知道如何用C或甚至汇编这样的东西来编码它.我想我只是没有足够的图灵机练习(工作),但我很感激任何建议.

编辑

我不想制作图灵机模拟器,我想在纸上描述图灵机(字母,状态,过渡)来决定某种语言.

这是一个简单的例子,我的意思是,我需要编写一个超过0和1的字符串的图灵机,并将其中的所有0更改为1.例如,如果从磁带(输入)上的11010开始,它将在磁带(输出)上以11111停止.现在用高级语言,你知道它是这样的:

Go over every character on tape
    If character is 0 change it to 1

图灵机描述非正式地类似于:

你有两个状态,q和停止.当您处于状态q并且您看到1时,请在不更改的情况下向右转.如果看到0,则将其更改为1并向右移动.如果看到空白符号(磁带末尾),则转到暂停状态.

在形式上你会有类似{q,halt}的状态.{((q,1) - >(q,1,R)),((q,0) - >(q,1,R)),((q,#) - >(halt,0,L) )}用于过渡.

现在这个问题是微不足道的,但还有其他更多涉及(添加一元数或识别具有相同数量的a,b和c的语言).我可以轻松地为他们编写伪代码,但编写图灵机更具挑战性(需要我很长时间),我想知道是否有一些技巧,资源或指导方针可以帮助我更好地解决这类问题.

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

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

制作PDA以识别以下语言:包含比b更多的字符串的语言

我几天来一直在努力解决这个问题,我似乎已经完成了一个完整的心理障碍.是否有人能够为我如何解决这个问题提供一些指导或指导？

如何识别没有算术的Prolog中的A ^ n B ^ n语言以及任何A,B,其中A!= B？

有了已知的A = a和B = b,我们就可以写了

% For each 'a' save 'b' in a list, then check 
% whether constructed list is equal to the rest of input list

anbn(L) :- anbn(L, []). 

anbn(L, L). 

anbn([a|L],A) :- anbn(L, [b|A]).

对于任何A和BI都在考虑一个解决方案

anbn(L) :- anbn(L, []).

anbn([H|L],[]) :- anbn(L,[H]). % save an element

anbn([H|L], [H|A]) :- anbn(L, [H,H|A]). % make sure front elements are the same

所以第一个元素都是相同的,但是我没有看到一个优雅的方法来检查列表其余部分中的所有元素是否与前面的元素相同和不同.

我可以检查剩下的是否与存储的列表一样长,然后它是否只包含第二个类型的元素,但我相信我的问题过于复杂,并且存在一个简短的解决方案.

按照标题：

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

字母= {a，b}

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

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

然而，

w = b

也被接受。

在下一个解决方案中：

我们的问题

w = b

在这里解决了，但是

w = aaab

不被接受。

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