问题标签 [formal-languages]

请不要在这里回答，而是在 cstheory.stackexchange，我将这个问题复制到！

JSON 和 XML 都经常被称为上下文无关语言——它们都主要由 EBNF 中的形式语法指定。然而，这仅适用于RFC 4329 第 2.2 节中定义的 JSON，它不需要对象键的唯一性（许多人可能不知道，但 {"a":1,"a":2} 是有效的 JSON！）。但是，如果您需要 JSON 中的唯一键或XML 中的唯一属性名称，则无法通过上下文无关文法来表达。但是哪个是具有唯一键和格式良好的 XML 的 JSON 语言类（这意味着唯一的属性名称？）。

我在这个主题上找到的最好的论文之一（Murato et al, 2001: Taxonomy of XML Schema Languages using Formal Language Theory）明确排除了完整性约束，例如键/keyrefs 和要在附加层上检查的唯一性。除此之外，由 XML Schema 或 DTD 定义的 XML 子集是上下文无关的。但不是所有格式良好的 XML 文档的完整集。

我认为嵌套堆栈自动机（=索引语言）应该能够解析具有唯一键约束的 JSON。对于 XML 可以将问题简化为所有以逗号分隔的唯一整数列表的语言 S。有没有人知道更多，最好是引用？

PS：决定语言的简单算法（除了上下文无关部分）基于良好的排序算法。因此，在 O(n log n) 最坏情况下，它应该可以在“线性时间”中确定。我还没有发现复杂性类是例如“轻度上下文敏感”还是“索引”，但可能介于上下文无关和上下文敏感（？）之间。

考虑以下正则表达式：

1. 7+
2. (7)+

有没有非常熟悉数学中的正则表达式理论的人同意这两个正则表达式在语义上是相同的？

当您证明一种语言是可判定的时，您实际上在做什么？

我怀疑甚至可能有一个数学证明可以证明这个答案是否定的，但是，问题是：是否可以发明一种类似 php 的语言（即，一些行在幕后评估代码，而一些行评估为显示的 html）它总是可以正确嵌套的地方？举一个我在说什么的例子，在 rails/haml

第二个 %tr 应该与第一个垂直对齐（因为它们是输出 html 中的兄弟），但是每个块开始的行会导致它缩进一行。是否有人可以开发某种 html 元语言，其中缩进可以反映控制结构和适当的嵌套，而不会相互冲突？如果有，这样的事情是否存在？

什么是 R-平凡语言？即定义是什么？

什么是 R-平凡幺半群？

背景：正式语言。Afaik，R-trivial 语言是无星语言的子集。

我主要有形式语言和自动机理论的背景，但对句法幺半群表征不太了解。所以最好用这种语言的一个小例子来给出一个基本的定义。

（为了支持多个 QA 站点，因为我不想让任何 QA 站点留在后面，也不想让那个问题也出现在那里，我还在这些其他站点上发布了这个问题：cstheory.stackexchange.com，math .stackexchange.com , mathoverflow.net . 一般来说，我反对交叉发布，但在这种情况下，因为它们都有相同的目标，即成为特定领域问题的完整参考，交叉发布问题是最好的你可以做。）

本质上，我想知道是否可以用正则表达式替换特定的 XSD 架构。我知道 XML Schema 语言可以生成 XSD，其有效 XML 实例集可以是任何类型的语言（甚至是上下文相关的）。我想识别那些“正则表达式等效”的模式。在解决了以下问题后，我提出了这个问题：

我需要解析特定的文本格式，我首先尝试了正则表达式，我发现 regexp 足以解析它。然后我想为我收到的这种格式的消息制作一个 XML 表示，所以我用 XML 元素映射了正则表达式组。然后，我根据正则表达式的结构手动创建了一个 XSD 模式。最后，我有一个可以替换我的正则表达式的模式，从某种意义上说，原始的正则表达式可以从模式中构造出来。我还设法做相反的事情：从正则表达式自动创建模式。因此，我可以将消息转换为 XML 并同时对其进行验证。我的问题是：

1. 每个正则表达式都可以用 XSD 模式表示吗？（我的意思是，给定一个能够生成 XSD 模式的正则表达式）

2. 给定一个任意 XSD 模式，有没有办法确定是否存在一个表示给定模式的正则表达式？

   编辑：可能第一个问题的答案是肯定的，因为我用我的正则表达式做的，不依赖于特定的正则表达式（这不是每个正则表达式的证明）。

我正在阅读 Peter Linz 的一本名为“形式语言和自动机简介”的书。在它的一个问题中，它要求我，"Design an acceptor for integers in a programming language C"有人可以告诉我如何获得这个答案。任何帮助将不胜感激

首先，我不知道这是否是我所要求的正确翻译。

在我的一门课程中，我们只是盯着学习正则表达式、形式语言等。

在这种情况下，假设我从 1R 开始，然后我可以继续使用 1R 或 0R。

如果我从 1R 开始，那么只有 1....那么句子（在这种情况下是二进制数）是完整的，对吗？因为我不能在之后“附加”一些东西，所以说 1R 然后我选择 1 然后我再次选择 1R ？

在此先感谢，如果不正确，请重新标记/移动帖子。

添加：

如何生成 1100110？

这不是家庭作业，它是来自 powerpoint 的示例/问题。我不明白这是怎么做到的。

这样的事情存在吗？如果是这样，你能举个例子吗？谢谢。

ANTLR 中没有逻辑吗？我基本上试图否定我拥有的规则并且想知道它是否可能，还有逻辑吗？