程序员经验分享-hwhale

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

2024-02-20

众所周知，给定一个正则语法，我们有算法来获取它的正则表达式。

但是如果给定的语法是上下文无关语法（但它只生成常规语言），就像

  • S->aAb
  • A->bB
  • B->cB|d

    • 有没有现有的算法可以得到通用的正则表达式？

    Thanks！


    从最一般的意义上来说，没有解决方案。确定 CFG 是否正则的问题是不可判定的（Greibach 定理，最后 3 页）http://www.cis.upenn.edu/~jean/gbooks/PCPh04.pdf http://www.cis.upenn.edu/~jean/gbooks/PCPh04.pdf）如果我们可以将 CFG 转换为正则表达式，我们就可以在任何语法上使用该算法，并使用其成功/失败来确定该语言是否是正则语言。

    因此，当已知 CFG 可以生成正则语言时，要么其语言已知（因此可以直接转换为 RegEx），要么存在可以利用的语法的某些属性。每个属性都有自己的转换为正则表达式的算法。

    例如，如果语法是右线性 http://en.wikipedia.org/wiki/Linear_grammar，每个产生式都是 A->bC 或 A->a 的形式。这可以转换为 NFA，其中：

    1）每个非终结符都有一个状态，加上一个接受状态。

    2）起始符号S为起始状态。

    3) A->bC 是输入 b 上从 A 到 B 的转换

    4) A->a 是从 A 到输入 a 的接受状态的转换。

    然后可以通过状态消除将该 NFA 转换为正则表达式（第 5-8 页）http://www.math.uaa.alaska.edu/~afkjm/cs351/handouts/regular-expressions.pdf http://www.math.uaa.alaska.edu/~afkjm/cs351/handouts/regular-expressions.pdf）。 左线性语法的类似过程将交换开始和接受状态。

    除此之外，我们还可以利用常规语言的闭包属性。例如，问题中的语言不是线性的，但可以写成S->S'b，S'->aA。现在 S' 是右线性的，S 是两个不相交线性文法的串联。连接两个表达式作为最终表达式。 Union 的逻辑类似。

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

    regex

    contextfreegrammar

    regularlanguage

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

    随机推荐

    • 覆盖rails update_all方法

      我需要覆盖轨道 活动记录 update all方法 以便它始终更新updated at场也是如此 我应该如何实现这一目标 将以下代码放入文件中 config initializers update all with touch rb cla

    • 将用户定义的库添加到 SVN

      我正在开发一个项目 我使用了许多外部库 jar 格式 我已将下载的所有外部 jar 添加到版本控制 subversion 的构建路径中 然而 最近我注意到许多库并不在 SVN 树中 我对此进行了一些研究 这些是我作为用户定义的库创建的库 并

    • 在函数中使用全局变量

      如何在函数内创建或使用全局变量 如何在一个函数中在其他函数中使用定义的全局变量 Failing to use the global keyword where appropriate often causes UnboundLocalErr

    • PostgreSQL 自定义异常？

      在 Firebird 中我们可以像这样声明自定义异常 CREATE EXCEPTION EXP CUSTOM 0 异常 自定义异常 这些存储在数据库级别 在存储过程中 我们可以像这样引发异常 异常 EXP CUSTOM 0 PostgreS

    • Cakephp - HABTM 记录不会在唯一设置为 true 时删除

      CakePHP 的默认值 unique 设置为 true 我对其进行编码也是为了确保这一点 所以我有以下数据库结构 项目 HABTM 操作 将 unique 设置为 true 情况如下 当我删除 1 条或多条记录时 如果至少 1 条记录保持

    • 有没有办法从 Java Play 2 框架中的数据库生成代码？

      有谁知道如何在 Play Framework 2 0 中轻松地从数据库生成代码 我知道他们有一个模块 但似乎这是 1 X 版本的 Anyone CRUD 模块仅适用于 Play 1 2 x 在 Play 2 0 中不可用 它可能会在 Pla

    • C++ 中的 exit 和 std::exit 有什么区别？

      有什么区别exit and std exit在 C 中 我已经研究过但我找不到任何东西 这两个代码有什么区别 1 if SDL Init SDL INIT EVERYTHING 0 std cout lt lt Error Can t in

    • 实例变量何时初始化并赋值？

      实例变量什么时候初始化 是在构造函数块完成之后还是之前 考虑这个例子 public abstract class Parent public Parent System out println Parent Constructor init

    • 如何在cmd中显示每个进程的CPU使用率

      我想要一个 cmd windows 命令来显示所有进程以及每个进程的 cpu 百分比 有一个命令可以给我这个结果吗 你能帮我吗 谢谢 Try pslist http technet microsoft com en us sysintern

    • 访问回收站

      我想检查回收站中的文件 就像它是一个普通目录一样 特别是获取那里的文件列表以及每个文件到达回收站的日期 这段代码可以帮助你 Access the recycle bin folder Dim SH As New Shell32 Shell

    • Python 3.6 中的 f 字符串调试简写

      下列适用于 Python 3 8 https stackoverflow com questions 59661904 what does equal do in f strings inside the expression curly

    • 尝试删除最后一个元素时，带有子项的 SwiftUI (2.0) 列表崩溃

      我有以下带有子项的 SwiftUI 列表的代码 改编自另一个 StackOverflow 答案 SwiftUI 2 0 带有子项的列表 如何使披露按钮的可点击区域覆盖整个列表项 https stackoverflow com questio

    • 校准图像以获得位于同一平面上的点的顶视图

      校准 我已经使用 Matlab 中的视觉工具箱校准了相机 我使用棋盘图像来做到这一点 校准后我得到了cameraParams 其中包含 Camera Extrinsics RotationMatrices 3x3x18 double Tra

    • Angular 5 材质小吃栏仅针对自定义错误处理无法正确显示，否则工作正常

      Angular 5 材质 材质小吃栏仅针对自定义错误处理无法正确显示 否则工作正常 我试图使用材料小吃栏显示我的后端错误 问题是第一次被触发时 它出现在错误的位置 不是应有的底部中间 而是在左侧 并且它永远留在那里而不会消失 根据我的配置

    • 单击时弹出窗口中出现错误微调器

      我的应用程序如果有一个按钮 一个弹出窗口 有两个旋转器 那么我就可以在那里弹出窗口 但是当我单击旋转器时出现错误 这里有我的下面的代码和调试 因为 logcat 我一切都正确 public void a adirRegistro View

    • 根据另外 2 个表的联接结果插入到一个表中

      我在 MySQL 中有 3 个表 def table spot table tag mapping spot table def table tag id tag ja 2010490043 鉄道 2010680003 american f

    • 从动态名称获取 PHP 枚举

      我正在尝试从动态名称创建 php 8 1 枚举 看来不可能 所以给定一个枚举 enum Foo case bar 当然还有以下作品 Foo bar虽然这不会 name bar Foo name 这会导致 访问未声明的静态属性 App Con

    • 使用批处理检查互联网连接

      因此 最近我的互联网连接确实不太令人满意 因此我正在尝试收集尽可能多的数据 以了解中断的时间和持续时间 我尝试了一些 连接监控 程序 但它们没有按照我想要的方式工作 所以我决定制作一个 我是一个十足的菜鸟 但通过过去一个小时的谷歌搜索 我想

    • Mathematica 中的空值和非空值测试

      在 Mathematica 中测试某个值是否为 Null 的最佳 最干净 建议的方法是什么 并且不为空 例如 a Null b 0 f n If n Null 1 2 f a f b 结果是 1 If 0 Null 1 2 我本来期望 f

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

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

    热门标签