程序员经验分享-hwhale

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

2023-12-22

给定任意上下文无关语法，我如何检查它是否描述了常规语言？

我不是在寻找考试“技巧”。我正在寻找一种可以编写代码的万无一失的机械测试。

如果有帮助，这里是我可能会收到的 CFG 作为输入的示例。 具体来说，请注意，答案一定比仅仅寻找左递归或右递归复杂得多，因为另一种类型的递归的存在并不自动意味着语法是不规则的。

S: A B C D X
A: A a
A:
B: b B
B:
C: c C c
C: c
D: D d D
D: d
X: x Y
X:
Y: y X
Y:

不存在这样的机械过程，因为确定CFG是否定义正则语言的问题是不可判定的。

这个结果是一个简单的应用格雷巴赫定理 https://en.wikipedia.org/wiki/Greibach%27s_theorem#Applications.

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

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

  • 如何使用 std::string 将所有出现的一个字符替换为两个字符？

    有没有一种简单的方法来替换所有出现的 in a std string with 转义 a 中的所有斜杠std string 完成此操作的最简单方法可能是boost字符串算法库 http www boost org doc libs 1 46

  • AWS ElasticSearch Service - 从 CF 模板设置加密选项

    我正在创建一个云形成模板来在AWS中配置elasticsearch服务域 我想将加密下的此属性设置为 true 域的所有流量都需要 HTTPS 但我无法在 AWS 文档中找到执行此操作的方法 用于设置加密属性的其他选项 例如 启用静态数据加

  • C 中的异或运算符

    在进行按位操作时 我在确定何时使用 XOR 运算符时遇到一些困难 按位与和或非常简单 当您想要屏蔽位时 请使用按位 AND 常见用例是 IP 寻址和子网掩码 当您想要打开位时 请使用包含或 然而 XOR 总是让我明白 我觉得如果在面试中被问

  • 如何在不声明新数据的情况下更改类型（String，Int）元组的 Ord 实例？

    我正在尝试对类型列表进行排序 String Int 默认情况下 它按字符串排序 然后按整数排序 如果字符串相等 我希望它是相反的 首先比较整数 然后如果相等则比较字符串 另外 我不想切换到 Int String 我找到了一种通过定义实例来实

  • 如何在 C++ BOOST 中像图形一样加载 TIFF 图像

    我想要加载一个 tiff 图像 带有带有浮点值的像素的 GEOTIFF 例如 boost C 中的图形 我是 C 的新手 我的目标是使用从源 A 到目标 B 的双向 Dijkstra 来获得更高的性能 Boost GIL load tiif

  • 限制C#中的并行线程数

    我正在编写一个 C 程序来生成并通过 FTP 上传 50 万个文件 我想并行处理4个文件 因为机器有4个核心 文件生成需要更长的时间 是否可以将以下 Powershell 示例转换为 C 或者是否有更好的框架 例如 C 中的 Actor 框

  • 使用 z = f(x, y) 形式的 B 样条方法来拟合 z = f(x)

    作为一个潜在的解决方案这个问题 https stackoverflow com questions 76476327 how to avoid creating many binary switching variables in gekk

  • Ruby 中的 url_encode

    I read 的文档url encode http rdoc info stdlib erb 1 9 3 ERB Util 3Aurl encode 是否有一个表可以准确地告诉我哪个字符被编码为什么 使用url encode ERB s u

  • jolt变换后json对象的排序

    Input The input json object 所需输出 Event1 Value1 Event2 collection of json objects Event3 The input json object 所以基本上输入 js

  • AWS DynamoDB 写后读一致性 - 理论上它是如何工作的？

    大多数nosql解决方案仅使用最终一致性 并且考虑到DynamoDB将数据复制到三个数据中心 如何保持写后读一致性 解决此类问题的通用方法是什么 我认为这很有趣 因为即使在 MySQL 复制中 数据也是异步复制的 我将详细告诉您 Dynam

  • 张量流中的复杂卷积

    我正在尝试运行一个简单的卷积 但包含复数 r np random random 1 10 10 10 i np random random 1 10 10 10 x tf complex r i conv layer tf layers c

  • Kivy - 单击按钮时编辑标签

    我希望 Button1 在单击时编辑标签 etykietka 但我不知道如何操作 你有什么想法吗 class Zastepstwa App def build self lista WebOps getList layout BoxLayo

  • CGImage/UIImage 在 UI 线程上延迟加载会导致卡顿

    我的程序显示一个水平滚动表面 从左到右平铺有 UIImageViews 代码在 UI 线程上运行 以确保新可见的 UIImageView 分配有新加载的 UIImage 加载发生在后台线程上 一切工作几乎都很好 除了每个图像变得可见时出现口

  • 使用 AppleScript 运行另一个应用程序而不将其显示在扩展坞上

    使用 AppleScript 您可以创建运行另一个应用程序的脚本 然后将该脚本本身另存为应用程序并将其放置在 Dock 中 问题 不是真正的问题 是 当您单击它时 它仍然会在扩展坞上显示其他应用程序 是否可以阻止其他应用程序在扩展坞中显示

  • 防止索引超出范围错误

    我想编写对某些条件的检查 而不必使用 try catch 并且我想避免出现 Index Out of Range 错误的可能性 if array Element 0 Object Length gt 0 array Element 1 Ob

  • 如何在 PHP 中从字符串类名实例化？ [关闭]

    Closed 这个问题需要细节或清晰度 help closed questions 目前不接受答案 如何创建返回方法名称的新实例 不幸的是我收到这个错误 错误 类名必须是有效的对象或字符串 这是我的代码 class Foo public f

  • Git 提交失败：“请使用 -m 或 -F 选项提供消息。”

    当我键入 git commit 命令来提交文件时 我收到以下错误消息 Microsoft Visual Studio 微软 找不到命令 错误 核心编辑器 Microsoft Visual Studio 存在问题 请使用 m 或 F 选项提供

  • 恢复上传文件控制

    我确实阅读了以下帖子 C 暂停 恢复上传 https stackoverflow com questions 1048330 pause resume upload in c 使用 HTTP 恢复上传 https stackoverflow

  • 为什么使用 iPhone 或 iOS 设备在“iframe”中查看“position:fixed”时不起作用？

    我研究过 stackoverflow 似乎position fixed在 iOS 移动设备的 iframe 中 https stackoverflow com questions 15874910 position fixed and if

  • 两种情况或 if 哪个更快？ [关闭]

    Closed 这个问题不符合堆栈溢出指南 help closed questions 目前不接受答案 我必须制作一个 非常 轻的脚本 它将接受用户的选项并调用脚本中的函数来执行一些任务 现在我可以使用 IF 和 CASE 选项 但我想知道两

随机推荐

  • 安装QMYSQL驱动

    基本上 当我尝试连接到 mysql 数据库时 我收到此错误 QSqlDatabase QMYSQL driver not loaded QSqlDatabase available drivers QSQLITE QODBC QODBC3

  • 对数组中的对象属性求和

    我有一个对象数组 我想对其中一个属性的值求和 例如 Array 0 gt stdClass Object name gt jon commission gt 5 1 gt stdClass Object name gt smith comm

  • 为什么不可变字符串可以调用 String::add(mut self, other: &str) [重复]

    这个问题在这里已经有答案了 In stdlib字符串 rs impl Add lt str gt for String type Output String inline fn add mut self other str gt Strin

  • 通过 JDBC 访问表时如何检查表的锁定状态

    我正在使用 JDBC 连接到 Oracle 表 表 1 仅执行插入操作 限制为 使用 陈述 only java 代码有一个侦听器 用于侦听数据源 该数据上传到表 1 转换后表 1 中的数据由表 2 读取 要求是使这个过程接近实时 我的问题

  • 适用于 .NET 的 UniData 数据访问产品

    我正在研究如何从 NET 代码访问 UniData 数据库中的数据 根据我的发现 我可以使用 NET 的 UniObjects http www 01 ibm com software data u2 middleware index ht

  • 当在很多矩形上使用背景时，Raphael JS 变得非常慢

    我有一大组小矩形 4K 5K 我想使用精灵技术为它们提供背景 所以我只有一个图像 否则请求数量会杀死服务器 如果我给它们一个彩色背景 那么地图只需要几秒钟就可以构建出来 我尝试创建一个矩形 对其应用翻译以获得分配的背景图像的不同部分并且有效

  • 终止 EC2 实例时删除 EBS 卷，通过 terraform

    我的 tf 文件中有以下内容 provider aws region var aws region resource aws ebs volume agent xvdf count var ec2 count availability zo

  • HBase客户端-服务器版本兼容性

    我想知道如何知道我的 HBase 客户端的 jar 是否适合我的 HBase 服务器的版本 是否有任何地方指定 HBase 客户端 jar 支持哪些 HBase 版本 就我而言 我想将最新的 HBase 客户端 jar 2 4 5 与相当旧

  • 如何以 jQuery 方式搜索和操作复杂的 JavaScript 对象

    在 Web 应用程序的上下文中 我有一个服务器 它根据客户端的输入发送或接收 JSON 字符串 在客户端使用时 这些 JSON 字符串会立即转换为 JavaScript 对象 并以对象的形式存在 这些对象不是数组 而是数组 它们代表复杂的

  • 如何向 BLE 设备发送命令并显示结果

    Override public void onServicesDiscovered final BluetoothGatt gatt int status super onServicesDiscovered gatt status if

  • 从表A中选择B表中不存在的内容

    我正在尝试为 MySQL 编写一条 SELECT 语句 该语句从表 A 中选择表 B 中不存在的内容 例如 Table A BAND 1 2 3 4 5 Table B HATE 1 5 因此 如果表 A 是所有乐队 表 B 是我讨厌的乐队

  • xsl 使用键相乘

    抱歉 我不知道如何提问 我有 3 个 xml 文档 我有一个正在运行的 xsl 只是我无法弄清楚价格总额如何乘以数量 我的时间不多了 请帮忙 这是xsl

  • 在 SSIS 中的文件系统任务之后进行分支而不会使包失败

    如果文件系统任务 例如重命名 失败 例如文件不存在 则 SSIS 会认为这是一个错误 这意味着整个包失败 我可以通过使用脚本任务或将包的最大错误设置为多个来解决这个问题 将包的最大错误设置为多个的问题在于 如果包中的其他位置发生错误 则包不

  • PHPExcel 如何设置单元格名称？

    通常在 Excel 中 您可以为单元格指定特定名称 在 phpexcel 中如何做到这一点 开发人员文档的第 4 6 38 节描述了如何执行此操作 标题为 定义命名范围 的部分 objPHPExcel gt addNamedRange ne

  • 如何详细了解 Laravel 队列作业失败的原因？

    情况 我正在使用 Laravel 队列来处理大量媒体文件 单个作业预计需要几分钟 最多一个小时 我正在使用 Supervisor 来运行我的队列 并且一次运行 20 个进程 我的主管配置文件如下所示 program duplitron wo

  • AF_UNIX 套接字中缓冲区的最大长度

    我想知道 当使用套接字 AF UNIX 用C进行编程时 向套接字发送或从套接字接收数据时是否有任何限制 以字节为单位 您可以使用以下命令更改每个单独套接字连接的读取和写入缓冲区setsockopt http www opengroup or

  • 矩阵 - 如何从用户输入（行）创建矩阵？

    我想根据用户输入创建矩阵 如下所示 这是我的代码 flag True while flag num int input enter matrix dimension if num 0 print Finish flag False else

  • 如何在 LuisActionDialog 传递上下文中从一个意图跳转到另一个意图

    我正在使用 Microsoft Bot Framework LUIS 和LUIS动作绑定 https github com Microsoft BotBuilder Samples tree master CSharp Blog LUISA

  • 如何防止 CALayer（CATiledLayer 的子层）在缩放后更改其比例？

    我有一个用于显示 PDF 页面的 CATiledLayer 此 CATiledLayer 是我的 UIView 的图层类型 它是 UIScrollView 的子视图 我想在此页面上添加覆盖标记 因此 我将一个子层添加到我的 CATiledL

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

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

热门标签