问题标签 [language-theory]

在 Java 中，构造函数不能是递归的。编译时错误：“递归构造函数调用”。假设我们没有这个限制。

要记住的事情：

• 构造函数的返回类型是 void。由于它是一种 void 方法，因此您无法利用递归的全部力量。
• 构造函数可以使用 this() 调用自身（或任何其他构造函数）。但是“对此的调用必须是构造函数中的第一条语句”
• 我们可以在连续调用之间使用非本地数据，以从递归构造函数中获得一些可能的收益。

允许递归构造函数有什么好处吗？

我知道这与编程没有直接关系，但我想知道是否有人知道如何将泵引理应用于以下证明：

证明L={(a^n)(b^n)(c^m) : n!=m}不是上下文无关语言

我对应用抽水引理非常有信心，但这真的让我很恼火。你怎么看？

如果给你一种语言，你如何判断它是正规的、CF 但不是正规的，还是短语结构而不是 CF？有没有解决这个问题的好方法？我可以随意尝试制作 FA 或 PDA，但我觉得有更好的方法来做。

经典例子：

L = { a^nb^nc^n | n >= 0 }

从哪里开始？谢谢。

我想知道形式语言。我有一种解析器：它读取类似 xml 的序列化树结构并将其转换为多维数组。

我的观点是所使用的算法与不同类型的自动机（状态机图灵机堆栈......）之间的相似之处。

所以问题是：我在这里隐含使用的自动机是什么，它适合哪些正式的语言家族？什么是递归？

我所说的“我隐式使用的自动机”的意思是“这是完成相同工作的最小自动机”。

这是完整的来源：

请不要在这里回答，而是在 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) 最坏情况下，它应该可以在“线性时间”中确定。我还没有发现复杂性类是例如“轻度上下文敏感”还是“索引”，但可能介于上下文无关和上下文敏感（？）之间。

在我不断努力兑现承诺和过度交付的过程中，我正在寻找一个 .Net 工具来创建非程序员上级可以使用的简单 .Net 应用程序。我将如何编写和编译代码？

意图解释：我希望我的上级，而不是要求我制作条形码标签应用程序，选择一些选项，进行一些测试打印，然后创建应用程序并准备好重复使用。但是我该如何编写输出应用程序让他们在其他机器上重用呢？

另外，这是一个糟糕的想法还是有一些优点？

编辑：对于所有建议可配置性而不是我原来的问题的人：我们发布的所有内部使用的应用程序基本上都被日工使用，我的上司更喜欢这些应用程序是静态的和不可配置的。话虽如此，我们的一些应用程序在 5 或 6 年内没有改变，因为它们是按照所需的规范制作的。在过去的几周里，他们请求了 2 个新的条码应用程序，其中第三个请求是通过的。

是否有一个库（任何语言）可以在矩阵中搜索模式，如正则表达式适用于字符串？类似于矩阵的正则表达式或任何矩阵模式搜索方法？

我的理解是，这意味着人们可能会编写一个程序来正式证明用静态类型语言编写的程序将没有某个（小）缺陷子集。

我的问题如下：

假设我们有两种图灵完备的语言，A 和 B。假定 A 是“类型安全的”，而假定“B”不是。假设我有一个程序 L 来检查任何用 A 编写的程序的正确性。是什么阻止我将任何用 B 编写的程序翻译成 A，应用 L。如果 P 从 A 翻译到 B，那么为什么 PL 不是用 B 编写的任何程序的有效类型检查器？

我接受过代数培训，并且才刚刚开始学习 CS，因此可能有一些明显的原因表明这不起作用，但我非常想知道。这整个“类型安全”的事情对我来说已经有一段时间了。

我喜欢阅读有关编程理论的内容，那么您能否告诉我是否有任何面向对象的静态类型语言允许变量具有几种类型？伪代码示例：

我考虑在这个对象上调用方法的方式。如果对象值的类型为BigInteger | 双语言可以允许用户只调用共享方法（湖加，减），但当类型为BigInteger | 双 | Nil那么 Nil 的对象没有方法加减法，所以我们不能对这个对象做任何有用的事情，因为它只有很少的共享方法（如 toString）。

那么有什么想法应该如何在静态类型的面向对象语言中调用具有少量类型的变量的方法？

我在解决问题时遇到了问题：- 这是一个作业，我解决了，但它似乎太长太模糊了，请任何人帮助我......

具有偶数个 a 和奇数个 b 的字符串的正则表达式，其中字符集={a,b}。