regex - DFA 最小化-6ren

regex - DFA 最小化

转载作者：行者123 更新时间：2023-12-04 22:49:26

我有一个关于 DFA 最小化的问题。所以我使用了众所周知的技术将正则表达式转换为 NFA，然后使用 goto/closure 算法从中构造 DFA。现在的问题是如何将其最小化？我在这里看过有关它的课文:http://www.youtube.com/watch?v=T9Z66NF5YRk我仍然无法理解这一点。什么是 DFA 最小化？这只是合并 IDENTICAL 状态(在相同字符上进入相同状态的状态)还是不同的东西？

所以，我从以下语法开始:

%digit = '0'..'9'
%letter = 'a'..'z' | 'A'..'Z'
%exponent = ("e" | "E") ("+" | "-")? digit+

T_INT = digit+
T_FLOAT = T_INT exponent
T_IDENTIFIER = (letter | "$" | "_") (letter | "$" | "_" | digit)*

并最终得到以下 DFA(表示为 JSON):

{
    "START": [{
        "type": "range",
        "from": 36,
        "to": 36,
        "shift": "1"
    }, {
        "type": "range",
        "from": 48,
        "to": 57,
        "shift": "2"
    }, {
        "type": "range",
        "from": 65,
        "to": 90,
        "shift": "1"
    }, {
        "type": "range",
        "from": 95,
        "to": 95,
        "shift": "1"
    }, {
        "type": "range",
        "from": 97,
        "to": 122,
        "shift": "1"
    }],
    "1": [{
        "type": "range",
        "from": 36,
        "to": 36,
        "shift": "1"
    }, {
        "type": "range",
        "from": 48,
        "to": 57,
        "shift": "1"
    }, {
        "type": "range",
        "from": 65,
        "to": 90,
        "shift": "1"
    }, {
        "type": "range",
        "from": 95,
        "to": 95,
        "shift": "1"
    }, {
        "type": "range",
        "from": 97,
        "to": 122,
        "shift": "1"
    }, {
        "shift": ["t_identifier"]
    }],
    "2": [{
        "type": "range",
        "from": 48,
        "to": 57,
        "shift": "2"
    }, {
        "type": "range",
        "from": 69,
        "to": 69,
        "shift": "3"
    }, {
        "type": "range",
        "from": 101,
        "to": 101,
        "shift": "3"
    }, {
        "shift": ["t_int"]
    }],
    "3": [{
        "type": "range",
        "from": 43,
        "to": 43,
        "shift": "5"
    }, {
        "type": "range",
        "from": 45,
        "to": 45,
        "shift": "5"
    }, {
        "type": "range",
        "from": 48,
        "to": 57,
        "shift": "4"
    }],
    "4": [{
        "type": "range",
        "from": 48,
        "to": 57,
        "shift": "4"
    }, {
        "shift": ["t_float"]
    }],
    "5": [{
        "type": "range",
        "from": 48,
        "to": 57,
        "shift": "4"
    }]
}

那么我该如何最小化呢？

更新:

好的，这是我的算法。鉴于以下 DFA:

{
    0: [{
        from: 97,
        to: 97,
        shift: 1
    }],
    1: [{
        from: 97,
        to: 97,
        shift: 3
    }, {
        from: 98,
        to: 98,
        shift: 2
    }],
    2: [{
        from: 98,
        to: 98,
        shift: 4
    }],
    3: [{
        from: 97,
        to: 97,
        shift: 3
    }, {
        from: 98,
        to: 98,
        shift: 4
    }],
    4: [{
        from: 98,
        to: 98,
        shift: 4
    }]
}

这就是我为最小化它所做的:

对于每个状态(在我的示例中编号为 0、1、2、3、4)获得标识这种状态的唯一哈希(例如对于 state0，这将是:from=97,to=97,shift=1，对于 state1，这个将是:from=97,to=97,shift=3&from=98,to=98,shift=2 等等...)

比较获得的散列，如果我们找到两个相同的散列，则将其合并。在我的例子中，state2 hash 将是:from=98&shift=4&to=98，state4 hash 将是:from=98&shift=4&to=98，它们是一样的，所以我们可以将它们合并到新的 state5 中，之后 DFA 将看起来像这样:

{
0: [{
    from: 97,
    to: 97,
    shift: 1
}],
1: [{
    from: 97,
    to: 97,
    shift: 3
}, {
    from: 98,
    to: 98,
    shift: 5
}],
3: [{
    from: 97,
    to: 97,
    shift: 3
}, {
    from: 98,
    to: 98,
    shift: 5
}],
5: [{
    from: 98,
    to: 98,
    shift: 5
}]

}

继续这个直到我们没有变化，所以下一步(合并状态 1 和 3)将把 DFA 转换成以下形式:

{
0: [{
    from: 97,
    to: 97,
    shift: 6
}],
6: [{
    from: 97,
    to: 97,
    shift: 6
}, {
    from: 98,
    to: 98,
    shift: 5
}],
5: [{
    from: 98,
    to: 98,
    shift: 5
}]

}

没有更多相同的状态，这意味着我们已经完成了。

第二次更新:

好的，给定以下正则表达式: 'a' ('ce')* ('d' | 'xa' | 'AFe')+ | 'b' ('ce')* ('d' | 'xa' | 'AFe')+ 'ce'+ 我有以下 DFA (START -> start state, ["accept"] -> so to说转换到接受状态):

{
    "START": [{
        "type": "range",
        "from": 98,
        "to": 98,
        "shift": "1.2"
    }, {
        "type": "range",
        "from": 97,
        "to": 97,
        "shift": "17.18"
    }],
    "1.2": [{
        "type": "range",
        "from": 120,
        "to": 120,
        "shift": "10"
    }, {
        "type": "range",
        "from": 100,
        "to": 100,
        "shift": "6.7"
    }, {
        "type": "range",
        "from": 65,
        "to": 65,
        "shift": "8"
    }, {
        "type": "range",
        "from": 99,
        "to": 99,
        "shift": "4"
    }],
    "10": [{
        "type": "range",
        "from": 97,
        "to": 97,
        "shift": "6.7"
    }],
    "6.7": [{
        "type": "range",
        "from": 99,
        "to": 99,
        "shift": "15"
    }, {
        "type": "range",
        "from": 120,
        "to": 120,
        "shift": "13"
    }, {
        "type": "range",
        "from": 100,
        "to": 100,
        "shift": "6.7"
    }, {
        "type": "range",
        "from": 65,
        "to": 65,
        "shift": "11"
    }],
    "15": [{
        "type": "range",
        "from": 101,
        "to": 101,
        "shift": "14.accept"
    }],
    "14.accept": [{
        "type": "range",
        "from": 99,
        "to": 99,
        "shift": "16"
    }, {
        "shift": ["accept"]
    }],
    "16": [{
        "type": "range",
        "from": 101,
        "to": 101,
        "shift": "14.accept"
    }],
    "13": [{
        "type": "range",
        "from": 97,
        "to": 97,
        "shift": "6.7"
    }],
    "11": [{
        "type": "range",
        "from": 70,
        "to": 70,
        "shift": "12"
    }],
    "12": [{
        "type": "range",
        "from": 101,
        "to": 101,
        "shift": "6.7"
    }],
    "8": [{
        "type": "range",
        "from": 70,
        "to": 70,
        "shift": "9"
    }],
    "9": [{
        "type": "range",
        "from": 101,
        "to": 101,
        "shift": "6.7"
    }],
    "4": [{
        "type": "range",
        "from": 101,
        "to": 101,
        "shift": "2.3"
    }],
    "2.3": [{
        "type": "range",
        "from": 120,
        "to": 120,
        "shift": "10"
    }, {
        "type": "range",
        "from": 100,
        "to": 100,
        "shift": "6.7"
    }, {
        "type": "range",
        "from": 65,
        "to": 65,
        "shift": "8"
    }, {
        "type": "range",
        "from": 99,
        "to": 99,
        "shift": "5"
    }],
    "5": [{
        "type": "range",
        "from": 101,
        "to": 101,
        "shift": "2.3"
    }],
    "17.18": [{
        "type": "range",
        "from": 120,
        "to": 120,
        "shift": "25"
    }, {
        "type": "range",
        "from": 100,
        "to": 100,
        "shift": "22.accept"
    }, {
        "type": "range",
        "from": 65,
        "to": 65,
        "shift": "23"
    }, {
        "type": "range",
        "from": 99,
        "to": 99,
        "shift": "20"
    }],
    "25": [{
        "type": "range",
        "from": 97,
        "to": 97,
        "shift": "22.accept"
    }],
    "22.accept": [{
        "type": "range",
        "from": 120,
        "to": 120,
        "shift": "28"
    }, {
        "type": "range",
        "from": 100,
        "to": 100,
        "shift": "22.accept"
    }, {
        "type": "range",
        "from": 65,
        "to": 65,
        "shift": "26"
    }, {
        "shift": ["accept"]
    }],
    "28": [{
        "type": "range",
        "from": 97,
        "to": 97,
        "shift": "22.accept"
    }],
    "26": [{
        "type": "range",
        "from": 70,
        "to": 70,
        "shift": "27"
    }],
    "27": [{
        "type": "range",
        "from": 101,
        "to": 101,
        "shift": "22.accept"
    }],
    "23": [{
        "type": "range",
        "from": 70,
        "to": 70,
        "shift": "24"
    }],
    "24": [{
        "type": "range",
        "from": 101,
        "to": 101,
        "shift": "22.accept"
    }],
    "20": [{
        "type": "range",
        "from": 101,
        "to": 101,
        "shift": "18.19"
    }],
    "18.19": [{
        "type": "range",
        "from": 120,
        "to": 120,
        "shift": "25"
    }, {
        "type": "range",
        "from": 100,
        "to": 100,
        "shift": "22.accept"
    }, {
        "type": "range",
        "from": 65,
        "to": 65,
        "shift": "23"
    }, {
        "type": "range",
        "from": 99,
        "to": 99,
        "shift": "21"
    }],
    "21": [{
        "type": "range",
        "from": 101,
        "to": 101,
        "shift": "18.19"
    }]
}

故事是一样的，我如何最小化它？如果我遵循经典的 Hopcroft 算法来构建所有这些表，确定不可区分的状态，将它们合并在一起等等，那么我将得到包含 15 个状态的 DFA(使用这个工具: http://regexvisualizer.apphb.com/ 和这个正则表达式 a(ce )(d|xa|AFe)+|b(ce)(d|xa|AFe)+ce+ 来检查)。以下是使用 Hopcroft 算法缩小后 DFA 的样子:

Hopcroft's minimized DFA

我想出的算法，在“重新思考”Hopcroft 的算法之后，构建的 DFA 比你在上面看到的要小(抱歉图像质量，我不得不一步一步地重新绘制它以了解为什么它更小):

my algorithm

这是它的工作原理，关于“状态等价”的决定基于给定状态(例如“START”)的哈希函数的结果，如果我们从该状态开始，则可以从 DFA 构建短字符串.给定上面的 DFA 和 START 状态，我们可以构造以下字符串: 98->120, 98->100, 98->65, 98->99, 97->120, 97->100, 97->65 , 97->99 所以让它成为 START 状态散列函数的结果。如果我们为 DFA 中的每个状态运行此函数，我们将看到对于某些状态，此函数为我们提供相同的结果(“1.2”、“6.7”、“2.3”和“10”、“13”和“15” , "16"AND "11", "8", "26", "23"AND "12", "9", "4", "5", "20", "21"AND "17.18", "18.19"AND "25", "28"AND "27", "24") 所以我们需要做的就是将这些状态合并在一起。

我发现我在某处错了，但不明白我的算法生成的最小化 DFA 有什么问题？

最佳答案

您提出的算法没有完全最小化，因为它没有检测到行为相同的复杂结构。要了解此 DFA(由 JFLAP 绘制):

enter image description here

最小化将结合 q1 和 q2，但概述的算法无法做到。

与此相反，Hopcroft 的算法最初会像这样进行分区:

   {q0, q1, q2}, {q3}

然后拆分第一组，因为 q0 没有过渡到 q3:

   {q0}, {q1, q2}, {q3}

并且不会进一步 split ，因为 q1 和 q2 的行为相同。

关于regex - DFA 最小化，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11132319/

文章推荐： zend-framework - 未捕获的异常 'Zend_View_Exception'

文章推荐： google-apps-script - 如何在 toast() 中显示换行符/CR？

文章推荐： sql - 如何在同一个语句的where子句中使用like和 between？

文章推荐： perl - 在 Cygwin 1.7.11 中构建 Perl 5.6.2 的步骤

regex - DFA 最小化
我有一个关于 DFA 最小化的问题。所以我使用了众所周知的技术将正则表达式转换为 NFA，然后使用 goto/closure 算法从中构造 DFA。现在的问题是如何将其最小化？我在这里看过有关它的课文
delphi - 最小化/优化重复代码
这是我的代码，当鼠标光标悬停在 TPanel 上时，它会“动画化”它。我还有一个代码块来取消它的动画。 procedure Tmain.pStarting1MouseEnter(Sender: TOb
Jquery setInterval 最小化
我有图像 slider ，其中图像在超时时相互替换。我使用 jQuery 函数 setInterval() 但有一个小问题，在最小化浏览器窗口后，该函数继续“工作”，并且我恢复浏览器窗口图像的位置以令
c# - 禁用窗体双击时的最大化/最小化
这个问题在这里已经有了答案: 关闭 10 年前。 Possible Duplicate: How can I stop a double click of the window title bar
c# - 最小化/恢复窗口时是否可以禁用动画？
当我在我的 Windows 窗体应用程序中单击最小化按钮时，我不希望它执行经典的 Windows 最小化动画(窗口下降到任务栏)。据我所知，没有最小化事件，我只能使用调整大小，但我不知道如何检测我是
android - 检测应用程序关闭/最小化
首先 - 对不起我的英语。我刚刚创建了 Android 应用程序。它包含几个 Activity ，并在此应用程序的背景下播放音乐。当用户以某种方式(通过单击“后退”按钮、主页按钮或其他方式)离开应用
Java 2D 最小化
我需要帮助编写一个程序，该程序以 (X,Y) 的形式给出指定数量的坐标点。将给出的点数是程序中的第一行；它可以通过扫描仪读取。我需要计算覆盖线 x = a 和 y = b 的所有点的最小面积。因此，
Android:最小化 Activity
我需要一个 Activity 返回到上一个 Activity ，但如果再次单击该按钮，它将恢复上次的 Activity 。这是所需的过程:我点击一个按钮， Activity 开始。如果我点击“后退”按
javascript - 函数参数列表太长 |最小化
随着这个动画变得越来越复杂，我不断添加参数，以便它们在每次回调时可用。目前共有 6 个。例如，现在我想在显示消息时禁用输入框，因此我必须添加另一个元素 - in_element; 电话: M
c++ - 最小化、最大化按钮无缘无故消失
这是一个基于对话框的 MFC 应用程序。我并没有故意添加任何关于最小化、最大化和恢复按钮的代码。它可以首先显示那些按钮。但它在长时间运行后就会消失。或者计算机的 sleep 可能导致此问题？我不知道
c++ - 禁用窗口最大化/最小化
如何使用 Windows API 禁用窗口的最大化和/或最小化功能？最大化/最小化框需要变灰并禁用，双击标题栏、拖动到屏幕顶部等也需要不起作用。最佳答案您可以调用 SetWindowLong/Se
最小化 session 日程冲突的算法
是否有任何已知的算法帽子可以解决以下问题:我们有一个 session ，有多个同时会谈。用户应标记感兴趣的会谈，然后我们要创建一个会谈时间表，以便我的大多数人都可以参加他们的会谈并最大限度地减少日程冲
c++ - 什么事件用于最大化/最小化？
目前我负责为一个小项目开发一个(C++)窗口类；目标是将依赖性保持在最低限度。Win32/WinAPI 的实现按预期工作，但是，当涉及到 Linux/XCB 时，我正在努力。我知道，我可以检查“_N
c++ - windows编程中如何触发最大化/最小化
windows C++编程，如何让事件窗口最大化或最小化？对于鼠标按下事件，我们使用类似 mi.dwFlags = MOUSEEVENTF_LEFTDOWN 的东西，并使用 SendInput()
java - 最小化 if 条件
我编写了以下获取 2 个参数的构造函数，如果值(x 或 y)为负，它将被初始化为零。 public Point1 ( int x , int y ) { //if one or
javascript - 最小化 puppeteer 时我的代码不运行
我有以下代码，如果我将导航窗口最大化，它运行良好，但是当我最小化它时它停止工作。更多细节: 当窗口最小化时，“scrollDown & scrollTop”函数停止执行。 'use strict'
vba - 始终保持 Excel 最小化
我有一个包含一些宏和用户表单的 Excel 文件。我不希望用户在没有密码的情况下访问文件本身。他们应该只能看到用户表单并通过用户表单输入数据。这是我目前拥有的代码。 Private Sub Wor
tensorflow - 最小化 tensorflow 中复值网络的损失
目前，我正在尝试训练一个同时具有复值张量作为输入和输出的网络。作为损失函数，我采用输出与真实值之间逐点差异的范数。当我尝试最小化损失函数时，tensorflow 的“最小化”函数提示意外的复数。我觉
memory - 最小化 Julia 函数中的内存使用
这个函数是我想要优化的主力。任何关于如何限制其内存使用的想法都会很棒。 function F(len, rNo, n, ratio = 0.5) s = zeros(len); m = co
qt - 最小化 Qt 应用程序
在 Qt 下的 Windows Mobile 和 Symbian 平台上，如何通过单击应用程序中的某个按钮来最小化我的应用程序？最佳答案大概QWidget::setWindowState将适合您，

行者123

个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章

滴滴打车优惠券免费领取

全站热门文章

首页

博学

6Ren·AI

商城

regex - DFA 最小化