程序员经验分享-hwhale

常规语言的最小泵送长度

2024-03-21

如何计算正则语言的最小泵送长度。例如，如果我有 0001*，则最小泵送长度应为 4，即 000 无法泵送。为什么会这样呢？


它将小于或等于该语言的最小 DFA 中的状态数减一。因此，将正则表达式转换为 DFA，最小化它，并对状态进行计数。对于你的例子：

0001*

SOURCE    SYMBOL    DESTINATION
q1        0         q2
q1        1         q5
q2        0         q3
q2        1         q5
q3        0         q4
q3        1         q5
q4        0         q5
q4        1         q4
q5        0         q5
q5        1         q5

为什么等于这个呢？因为这是您可以在 DFA 中进行的最大转换次数，而无需访问某个状态两次。一旦你访问一个州两次，你就已经循环了。

当然，语言的最小 DFA 可能缺少那么长的路径。在这种情况下，您可以通过使用自动机图的深度优先搜索之类的方法并查看可以跟踪的路径有多长，找到不会两次访问某个状态的最长路径（从起始状态开始）。这才是你真正的答案。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

regularlanguage

pumpinglemma

常规语言的最小泵送长度 的相关文章

  • 生成正则表达式

    通常在我们的工作中我们会使用正则表达式capture or match运营 但是 可以使用正则表达式 至少手动 来生成与正则表达式匹配的合法句子 当然 有些正则表达式可以匹配无限长的句子 例如表达式 我有一个问题可以通过使用正则表达式句子生

  • 使用奥格登引理与常规泵引理进行上下文无关语法

    我正在学习问题中引理之间的区别 我能找到的每个参考文献都使用以下示例 a i b j c k d l i 0 or j k l 以显示两者之间的差异 我可以找到一个使用常规引理来 反驳 它的例子 选择 w uvxyz s t 维 gt 0

  • 在JAVA中按特定单词分割字符串

    字符串 S 乘 3 加加 3 3 1 我想得到两个字符串数组 第一个是 乘 加 加 另一个输出是 3 3 3 1 我怎么才能得到它 我尝试使用 String operators s split 0 9 String operands s s

  • 使用正则表达式表示标识符

    C 编程语言中识别标识符的常规定义为 letter gt a b z A B Z digit gt 0 1 9 identifier gt letter letter digit 该定义将生成以下形式的标识符 标识符 a zA Z a zA

  • 如何确定上下文无关语法是否描述了常规语言？

    给定任意上下文无关语法 我如何检查它是否描述了常规语言 我不是在寻找考试 技巧 我正在寻找一种可以编写代码的万无一失的机械测试 如果有帮助 这里是我可能会收到的 CFG 作为输入的示例 具体来说 请注意 答案一定比仅仅寻找左递归或右递归复杂

  • 证明某种语言正则

    在我的计算理论课上 我们的作业是证明一种语言是正规的 该语言定义为 B 1ky y is in 0 1 and y contains at least k 1s for k gt 1 在我看来 这种语言需要一个下推自动机来为此创建一台机器

  • 有没有办法否定正则表达式？

    给定一个正则表达式R它描述了一种常规语言 没有花哨的反向引用 有没有一种算法方法来构造正则表达式R 描述除以下描述的单词之外的所有单词的语言R 应该可以作为维基百科 http en wikipedia org wiki Regular la

  • 有没有一种正则语言来表示正则表达式？

    具体来说 我注意到正则表达式的语言本身并不是正则的 因此 我无法使用正则表达式来解析给定的正则表达式 我需要使用解析器 因为正则表达式本身的语言是上下文无关的 有没有什么方法可以用可以使用正则表达式解析结果字符串的方式来表示正则表达式 注意

  • 为什么正则语言的补语仍然是正则语言？

    根据我的教科书 只要L1是正则语言 L1 A L1的补集就是正则语言 A 不是还包括上下文无关语言 上下文相关语言和递归可枚举语言吗 A L1 也将包括所有这些 不是吗 那怎么可能有规律呢 在有限状态机的表示下 我理解为什么补码仍然是常规语

  • 泵送引理（常规语言）

    我需要一些帮助来解决泵引理问题 L a b c a L lt b L lt c L 这是我到目前为止得到的 y uvw is the string from the pumping lemma 我让 y abbc n n 是泵引理的长度 y

  • 为给定的正则表达式绘制最小 DFA

    绘制最小的直接且简单的方法是什么DFA 接受与给定相同的语言Regular Expression RE 我知道可以通过以下方式完成 Regex to NFA to DFA to minimized DFA 但有没有什么捷径呢 像 a b a

  • 是否有可能有匹配所有有效正则表达式的正则表达式？

    是否可以仅使用正则表达式来检测给定字符串是否是有效的正则表达式 假设我有一些字符串 它们可能是也可能不是有效的正则表达式 我想要一个正则表达式与对应于有效正则表达式的那些字符串相匹配 那可能吗 或者我是否使用一些更高级别的语法 即上下文无关

  • a* 与 (a*)* 相同吗？

    快速提问 如果a是一个正则表达式 那么这是真的吗a a Is a 有效的表达 如果是 那么任何人都可以解释为什么它与a 我很抱歉在这里提问 但我无法通过谷歌找到任何东西 Yes a a 是一样的 两者都生成相同的语言 即字符串包含的任何数字

  • 如果我们知道一个CFG只生成正则语言，那么我们能得到对应的正则表达式吗？

    众所周知 给定一个正则语法 我们有算法来获取它的正则表达式 但是如果给定的语法是上下文无关语法 但它只生成常规语言 就像 S gt aAb A gt bB B gt cB d 有没有现有的算法可以得到通用的正则表达式 Thanks 从最一般

  • 常规语言的抽引理

    我在使用泵引理检查给定语言是否规则时有点困惑 假设我们必须检查是否 L 接受偶数的语言0是否正常 我们知道它是正则的 因为我们可以为 L 构造一个 DFA 但我想用泵引理来证明这一点 现在假设我拿一个字符串w 0000 现在将字符串划分为x

  • 常规语言的最小泵送长度

    如何计算正则语言的最小泵送长度 例如 如果我有 0001 则最小泵送长度应为 4 即 000 无法泵送 为什么会这样呢 它将小于或等于该语言的最小 DFA 中的状态数减一 因此 将正则表达式转换为 DFA 最小化它 并对状态进行计数 对于你

  • a*b* 是正则吗？

    I know anbn for n gt 0 is not regular by the pumping lemma but I would imagine a b to be regular since both a b don t ha

  • 正则表达式中的顺序不重要吗？

    我正在查看此 stackoverflow 链接中提出的问题 奇数个 a 的正则表达式 https stackoverflow com questions 28902496 regular expression for odd number

  • 瑞典 SSN 正则表达式拒绝特定年龄以下的用户

    我的正则表达式有问题 我已经可以验证正确的瑞典社会安全号码以符合这些标准 YYMMDDNNNN 年月日 NNNN 年年月日DDNNNN YYYYMMDD NNNN 但如果用户未满 18 岁 我也想拒绝该用户注册 我的常规表达现在是这样的 有

  • [a-zA-Z] 的正则表达式

    我有一个仅匹配英文字母的正则表达式 a a zA Z 字符类 有没有内置的正则表达式 我的意思是像 s or w 您正在要求一个速记班 http www regular expressions info shorthand html对于英文

随机推荐

  • 搜索 Jenkins 作业的控制台输出

    我的 Jenkins 工作有 100 多个构建 我需要搜索该作业的所有构建 以查找控制台输出中具有特定字符串的构建 有没有什么插件可以做到这一点 我怎么做 我经常使用詹金斯脚本控制台 https wiki jenkins ci org di

  • 如何在Servlet中使用“应用程序”对象？

    如果我们正在编写 JSP 文件 则只需使用嵌入的 应用程序 对象 但如何在 Servlet 中使用它呢 The applicationJSP 中的对象称为ServletContext https docs oracle com javaee

  • 如何通过printf将正数打印为负数

    在阅读有关 printf 的内容时 我发现它可以通过以下代码 对于 根据用户的需要打印正数或负数 但是该代码不起作用并且输出是正值 请指出错误所在 谢谢 include

  • 获取给定 ISO 8601 日历年的周数

    我需要创建一个函数 根据 ISO 周系统 ISO8601 在 Swift 中计算给定年份的周数 我需要这个数字作为 Int 首先我想我需要做一个NSDate然后我意识到有时 12 月 31 日是下一年的第一周 例如 2014 年 12 月

  • “read”命令在一行中最多可以包含多少个字符

    我有以下 shell 脚本来从终端读取行 bin bash while read line do if z line then break fi echo line done 我无法输入超过 256 个字符 终端不允许我这样做 终端不会打印

  • 如何通过pyodbc备份数据库

    当使用 pyodbc 游标执行时 备份语句不能在事务中使用 pyodbc 似乎在默认事务内执行查询 我也尝试过使用自动提交模式或在备份语句之前添加提交语句 这两个都不起作用 can t execute the backup statemen

  • 位置 2 出现意外文字

    我在 html 页面上显示时遇到此错误 并且我以数组形式返回日期 如果我只想显示未来的月份和年份 那么应该做什么 现在我想返回整个日期 因此 html 上有错误ngmodel 中 p calendar 标签中的页面 其中我显示 date2

  • ckeditor“key”的使用 CKEDITOR.instances.editor.on('key', function (e){

    我意识到存在有关如何为 CKEDITOR 4 实现事件处理程序的问题 我可以使用此代码来获取按键按下数据 但我似乎无法在按键后获取数据 CKEDITOR instances editor on key function e document

  • Kotlin Android 扩展是否缓存合成属性或每次调用 findViewById() 时？

    如果我有一个简单的自定义视图 myitem xml

  • 检查 sys.argv[x] 是否已定义

    检查变量是否已传递给脚本的最佳方法是什么 try sys argv 1 except NameError startingpoint blah else startingpoint sys argv 1 检查长度sys argv if le

  • 如何使用 sf 更改国家之间共享边界的颜色？

    我想将共享颜色更改为不同的颜色 比如说红色 到目前为止 我正在绘制德国联邦州巴伐利亚并触及奥地利各州 我从以下位置获取数据https gadm org download country html https gadm org downloa

  • 尝试调用不存在的方法。超导系统

    当我运行 STS Spring Boot 应用程序时 出现以下错误 The attempt was made from the following location org apache catalina authenticator Aut

  • PITest 找不到测试

    我们的项目都是由整个公司的母公司设置的 对于我正在处理的项目 我们有一个根 pom 它引用该父级 并在其下面有许多模块 尝试单独将 PITest 与这些模块中的任何一个一起使用 或者在根模块上使用 都会导致不运行任何测试 lp server

  • 在 Notepad++ 中获取我自己的 PHP 函数的参数提示

    在 首选项 gt 备份 自动完成 中启用 输入时的函数参数提示 后 我获得了有关本机 PHP 函数的有用提示 如下所示 string false substr string str int start int length 是否有插件或其他

  • 音频会话服务： kAudioSessionProperty_OverrideAudioRoute 具有不同的输入和输出路由

    我正在摆弄音频会话服务 我正在尝试控制音频路由设置AudioSessionSetProperty kAudioSessionProperty OverrideAudioRoute as kAudioSessionOverrideAudioR

  • 在模型类中使用 java.awt.Point - 糟糕的编码风格？

    我有一个场景 对象在坐标系上移动 我考虑在我的模型类中使用 java awt Point 因为它提供了我需要的所有功能 位置表示 翻译 距离计算 但在我的模型中使用 java awt 类感觉有些错误 但重写相同的功能也不是答案 所以我的问题

  • MATLAB 中不使用 for 循环的多个数组的交集

    我总是被告知 在 MATLAB 中几乎所有的 for 循环都可以省略 而且它们通常会减慢进程 那么这里有办法做到这一点吗 我有一个元胞数组 tsCell tsCell存储不同长度的时间数组 我想为所有时间数组找到一个相交的时间数组 Inte

  • Twig 数组访问

    我正在尝试打印传递给树枝模板的变量的值 我正在使用这段代码 naziv 0 索引为 0 因为传递的数组只有一个元素 提到的代码会产生以下错误 具有键 title 的数组的键 0 不存在于 但是当我像这样使用 for 循环时 for key

  • Proguard (R8) 混淆自定义视图名称

    我在我的应用程序中使用 R8 并且有几个自定义视图 在 xml 布局中引用 但它们的名称根本没有混淆 有什么办法可以实现这一点吗 我正在使用标准 Gradle 规则 release minifyEnabled true shrinkReso

  • 常规语言的最小泵送长度

    如何计算正则语言的最小泵送长度 例如 如果我有 0001 则最小泵送长度应为 4 即 000 无法泵送 为什么会这样呢 它将小于或等于该语言的最小 DFA 中的状态数减一 因此 将正则表达式转换为 DFA 最小化它 并对状态进行计数 对于你

热门标签