为什么 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}+
..
nfa相关内容
将 nfa 转换为 dfa
我想编写一个将 nfa 转换为 dfa 的程序，用户绘制图形然后程序将其转换为 dfa .我该怎么做? 解决方案 您可能想查看之前有关 incites 的问题. C# 中的 NFA/DFA 实现 如答案所示，您可以通过在 C# 中重新实现以下 python 示例来解决问题 https://gist.github.com/491973 如果您不关心实现语言，而只是想玩
..
如何将NFA转换为相应的正则表达式?
我正在为明天的考试而学习，并且我检查了许多教程，讲述了如何将NFA转换为Regex，但是我似乎无法确认我的答案.按照这些教程，我解决了NFA 我的解决方法是: a ba 我正确吗? 解决方案 如何将NFA转换为正则表达式? 您的答案a*ba*是正确的.我可以从给定图像中的NFA得出您的答案，如下所示: 在起始状态q 0 上有一个带有标签a的自循环.因此，在初始
..
我正在尝试在Python中实现NFA以识别单词，但是我的代码无法正常工作，
我正在尝试实现一种识别单词的方法.我编写了以下代码，并尝试在纸上遵循我的代码，并使用示例输入逐步执行它，但是我找不到我的代码没有按我希望他做的那样的原因.有人看到这个缺陷吗?我看不到它，我对为什么它不起作用感到困惑. from collections import defaultdict class NFA: def __init__(self, initial, trns, fi
..
文本信息与数千个正则表达式的高效匹配
我正在解决一个问题，我有一条短信可以与数千种形式的正则表达式匹配 {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
..
将Epsilon-NFA转换为NFA
我无法理解将epsilon-NFA转换为NFA的过程，所以我想知道是否有人可以帮助我: 答案是: 新NFA中的0的A分别为1,2和2.我认为这是因为Epsilon NFA中的0导致1和2带有A(与Epsilon结合使用).那么为什么1,2为何没有A步到2，因为在Epsilon NFA中1却有A步到1和2? 解决方案 每当从NFA中删除ε时，在转换时都应注意ε过渡的方向.
..
将NFA转换为正则表达式
我在此网站上发现了相同的问题，答案是 PDF，其中描述了如何将NFA转换为正则表达式.但这不起作用，因为此方法有一些条件: 存在从初始状态到所有其他状态的转换，并且没有 过渡到初始状态. 只有一个接受状态，只有过渡进入其中(没有传出状态) 过渡). 接受状态不同于初始状态. 除了初始状态和接受状态外，所有其他状态都与所有其他状态连接 通过过渡状态.尤其是，每个州都有向自己的过渡.
..
将NFA转换为DFA
我在理解如何转换时遇到了麻烦. 如果2获得输入"a"，由于字符串为空，它将变成(1,4)或(1,2,4)? 谢谢！ 解决方案 如果状态Q2获得输入"a"，则下一个状态可以是Q1，Q2，0r Q4. 在您的NFA中，您将获得最终状态Q4 等效的DFA如下: a- ||
..
从正则表达式创建NFA的步骤
从正则表达式创建NFA时遇到“描述每个步骤"的问题.问题如下: 将以下正则表达式转换为不确定的有限状态自动机(NFA)，清楚地描述了所使用算法的步骤: (b | a)* b(a | b) 我已经制作了一个简单的三态机，但是这很直觉. 这是我的讲师在过去的一次考试中提出的问题，他的讲师也对汤普森的算法作了以下解释:任何人都可以弄清楚如何“清楚地描述每个步骤"吗?似乎只是一组基本规则，而不
..
如何使用字符范围实现正则表达式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完全相同，这似乎是矛盾的.
..
证明对{a，b}的以下设置是常规的
鉴于字母 {a，b} 我们定义了 N a （w）作为单词 w 中 a 的出现次数，对于 N b （w）。证明在 {a，b} 上的以下设置是常规的。 A = {xy | N a （x）= N b （y）} 我很难弄清楚从哪里开始解决这个问题。任何信息将不胜感激。 解决方案 是的，它是常规语言！ 如果 a 和 b 属于语言 A = {xy | N a （x）= N b （y）
..
将字符集转换为nfa / dfa的高效算法
我目前正在使用扫描仪生成器。 生成器已经可以正常工作了。但是，当使用字符类时，算法变得非常慢。 扫描器生成器会为UTF8编码的文件生成一个扫描器。应该支持所有字符（0x000000到0x10ffff）。 如果我使用大字符集，例如any运算符'。'或unicode属性{L} ，nfa（以及dfa）包含很多状态（> 10000）。因此，将nfa转换为dfa并创建最小dfa会花费很长时间（
..
模型检查:使用NFA的错误前缀
我们使用NFA为安全属性建模BadPrefixes.我想了解给定安全属性的NFA建模方法. 以下图像仅供参考. 例如，对于安全属性P2，有人可以解释如何知道需要多少个状态(解决方案有4个)以及在边上使用哪种逻辑，在图3和图4中，边如何选择满足不良前缀P1和P2.谢谢. 解决方案 在这里，我们有几个定义和符号，让我们首先看一下这些: 我们获得了一组原子命题AP.这里没有明确说，但
..
时间复杂度权衡nfa vs dfa
（我发现答案，它的下面在任何人的评论） 我正在寻找一个更好的使用和在编译器的什么情况下的讨论nfa或dfa。什么是模拟nfa vs dfa的时间复杂度折中，哪一个更适合在编译器的什么情况下？ 谢谢你，考试和帮助将非常麻烦：） Leanne。有人回答我:(：） 解决方案 来自NFA的DFA的构建时间是O （2 ^ m）其中m是节点数。 DFA的运行时间是O（n），其中
..