为什么 L={wxw^R|w, x 属于 {a,b}^+ } 是正则语言
使用泵引理，我们可以很容易地证明语言L1 = {WcW^R|W ∈ {a,b}*}不是常规语言.(字母是{a,b,c}；W^R代表反向串W) 然而，如果我们将字符 c 替换为 "x"(x ∈ {a,b}+)，例如 L2 = {WxW^R|x,W∈{a,b}^+}，那么L2是正则语言. 你能给我一些想法吗? 解决方案 如果我们用 x 替换字符 c，其中 (x ∈ {a,b}+
..
dfa相关内容
将 nfa 转换为 dfa
我想编写一个将 nfa 转换为 dfa 的程序，用户绘制图形然后程序将其转换为 dfa .我该怎么做? 解决方案 您可能想查看之前有关 incites 的问题. C# 中的 NFA/DFA 实现 如答案所示，您可以通过在 C# 中重新实现以下 python 示例来解决问题 https://gist.github.com/491973 如果您不关心实现语言，而只是想玩
..
你如何构建两个 DFA 的联合?
有没有人对构造两个给定 DFA 的并集的算法有一个简单的描述?例如，假设我们有两个超过 {0,1} 的 DFA，其中 {w|w 有奇数个字符}w 有状态 A 和 B三角洲 |0 |1----------------一个 |乙 |乙----------------乙 |一个 |一种{x|x 有偶数个 1}x 有状态 a 和 b三角洲 |0 |1----------------||乙--------
..
两种不同字母的语言的交集是什么?
我对此进行了一些谷歌搜索，但没有真正确定的弹出. 假设我有两种语言 A 和 B. A = { w 是 {a,b,c}* 的子集，使得 w 的倒数第二个字符是 b } B = { w 是 {b,d}* 的子集，使得最后一个字符是 b } 人们如何定义这一点?我认为字母表将是两者的结合，使其成为 {a,b,c,d} 但除此之外，我不知道如何对此进行 DFA. 如果有人能对
..
正则表达式 0(0+1)*0+1(0+1)*1 的 DFA 是多少?
这是我画的 DFA- 正确吗? 我很困惑，因为 q4 状态对于相同的输入符号有 2 不同的转换，这违反了 DFA 的规则，但我想不出任何其他解决方案. 解决方案 您的 DFA 不正确. 您的 DFA 完全错误，所以我不发表评论 RE 的 DFA: 0(1 + 0)*0 + 1(1 + 0)*1 语言说明:如果字符串以0开头，则应该以0结尾，或者如果字符串以1开头它应该以
..
设计接受可被数字“n"整除的二进制字符串的 DFA
我需要学习如何设计一个 DFA，以便给定任何数字“n"，它接受二进制字符串 {0, 1}，其十进制等效数可被“n"整除. 对于不同的“n"会有不同的 DFA，但是有人可以给出一个我应该遵循的基本方法来处理任何数字 0
..
如何扩展此语法的项目集？
我有这个语法 E-> E + i E-> i 增强语法 E '-> E E-> E + i E-> i 现在我尝试扩展项目集0 I0） E'-> .E + E-> .E + i + E-> .i 然后，因为我的 .E c $ c> I0 我将其扩展，但是随后我将得到另一个 E 规则，依此类推，这是我的第一个疑问
..
实施词法分析器时是DFA还是Regexes？
（我正在学习如何编写编译器，因此，如果我提出任何不正确的声明，请更正我的想法） 为什么有人仍会在代码中实现DFA（ goto语句，表驱动的实现）何时可以仅使用正则表达式？据我了解，词法分析器会输入一串字符并列出一系列标记，这些标记在语言的语法定义中是终端，因此可以用正则表达式对其进行描述。 解决方案 您绝对正确的是，编写正则表达式比DFA更容易。但是，要考虑的一个好问题是 这些
..
实现代码以模拟C ++中的不确定自动机
我正在为自动机理论做作业，我必须确定确定性有限自动机的转移函数是否接受一个词 I拥有此输入文件： 6 8 0 2 2 5 0 0 a 0 1 a 1 1 b 1 2 c 1 3 c 3 4 d 4 4 d 4 5 d 3 aaabcccc aabbbbcdc acdddddd 输入以4个整数开头，第一个是自动机
..
升压字符串匹配DFA
给出一个字符串，我必须测试它是否以一组已知的后缀结尾.现在，由于后缀的数目不是很小，因此必须对照该已知后缀列表检查文档中的每个单词.单词和后缀中的每个字符均为char32_t.作为幼稚的迭代匹配将是昂贵的.尽管大多数后缀都不是子后缀或不是另一个后缀的前缀，但是大多数后缀都是由一小部分字符构成的.大多数支票将是未命中而不是成功. 因此，我想构建后缀的DFA以最大程度地减少错过的费用.我可以手动
..
文本信息与数千个正则表达式的高效匹配
我正在解决一个问题，我有一条短信可以与数千种形式的正则表达式匹配 {0 or 300 chars} {0 or 300 chars} 例如 "on"[ \t\r]*(.){0,300}"."[ \t\r]*(.){0,300}"from" 或者一个真实的例子可以是 "Dear"[ \t\r]*"Customer,"[
..
在E = {a，b}上找到该语言的正则表达式
L = w:(na(w)-nb(w))mod 3/= 0 如何找到该语言的正则表达式? 我了解这意味着As的数量减去B的数量不能为3的倍数.所以a-b不能为3、6、9、12等. 但是我仍然很难将其放入正则表达式中.我先尝试将其设置为DFA或NFA，但我也无法做到这一点. 感谢您的帮助！ 解决方案 我会通过将{a，b}上的单词列表分为三种情况来解决此问题: L1
..
如何使用字符范围实现正则表达式NFA?
当您阅读 Regex:NFA和汤普森的算法一切看起来都很简单，直到您在现实生活中意识到不仅需要直接字符"7"或"b"，而且还需要: [A-Z] [^_] . 即字符类(或范围).因此，我的问题是-如何使用字符范围构建NFA?使用“非A"，“其他"之类的元字符，然后计算重叠范围?使用最终自动机时，这将导致使用树状结构，而不仅仅是表格. 更新:请假定大小字母(>> 256)不平凡.
..
如何在代码中实现有限自动机?
如何在Python代码中为此实现dfa或nfa? 在python中有哪些好的方法? 他们曾经在现实世界的项目中使用过吗? 解决方案 表示DFA的直接方法是将其作为词典的字典.对于每个州，创建一个由字母字母作为键的字典，然后创建一个由州作为键的全局字典.例如，以下有关DFA的维基百科文章 中的以下DFA 可以用这样的字典表示: dfa = {0:{'0':0, '1':1},
..
过渡中的歧义:如何在NFA中处理字符串?
我已经根据给定的正则表达式制作了DFA，以匹配测试字符串.在某些情况下会出现.*. (例如.*ab).假设现在计算机处于状态1.在DFA中，.*表示所有字符到其自身的过渡，而从状态1到a的另一过渡是"a".如果测试字符串包含"a"，则可能是过渡，因为从状态1开始，计算机可以进入两种状态，这在DFA中是不可能的. 解决方案 我从基础示例开始，以便对您有帮助 任何自动机类可以具有两种形式:
..
DFA与NFA引擎:它们的功能和局限性有什么区别?
我正在寻找基于DFA和NFA引擎之间功能和局限性的非技术性解释. 解决方案 确定性有限自动机(DFAs)和非确定性有限自动机(NFA)具有完全相同的功能和局限性.唯一的区别是符号方便. 有限自动机是具有状态并读取输入的处理器，每个输入字符都有可能将其设置为另一状态.例如，一个状态可能是“连续读取两个C"或“一个单词开始读".这些通常用于快速扫描文本以找到模式，例如对源代码进行词法扫描
..
给定正则表达式绘制最小DFA
绘制最小的DFA的直接和简便方法是什么，该方法接受与给定的Regular Expression(RE)相同的语言. 我知道可以通过以下方式完成: Regex ---to----► NFA ---to-----► DFA ---to-----► minimized DFA 但是有什么捷径吗?就像(a+b)*ab 解决方案 正则表达式转换为DFA 尽管没有从正则表达式(RE)
..
寻找DFA的补充?
要求我显示DFA图和RegEx，作为RegEx (00 + 1)*的补充.在前面的问题中，我不得不证明DFA的补码是封闭的并且也是正则表达式，因此我知道要将DFA M转换为补码M`，我只需要交换初始接受状态，然后最终接受状态. 但是，似乎RegEx的初始接受状态为{00, 1, ^}，最终接受状态也为{00, 1, ^}.因此，交换它们只会导致RegEx和DFA完全相同，这似乎是矛盾的.
..
“δ:Q×Σ→Q"如何变化?是否读过DFA(确定性有限自动机)的定义?
您怎么说英语δ: Q × Σ → Q?描述×和→的含义也将有所帮助. 解决方案 δ就像z = f(x, y) 数学函数定义了一组元素到另一组元素的映射.在函数集中，输入参数称为函数的域，而输出则为有效. [ANSWER] 在表达式"δ:Q×Σ → Q"中， ×表示笛卡尔积(即一组)，而→是映射. "δ:Q×Σ → Q"说δ是定义了从Q×Σ到Q的映射的转换函数. 其
..
可自定义的静态Java调用图生成器？
我必须重构和维护一堆看起来相似的可怕Java类。许多人具有以下实现模式 类机器{ public int advance（int state）{ switch （状态）{ 情况7：返回step_7（）; 情况13：返回step_13（）; 情况4：返回step_4（）; } } private int step_7（）{ if（something）return 13;否则返回
..