问题标签 [language-theory]

一直以为type-3语法以下没有真正的语言课，现在我发现了“极限语言识别”模型，它允许学习模式语言而不是常规语言。

模式语言到底是什么，它们与常规语言有什么区别？

我将在我的理论课上讨论这个问题，我很好奇这里有多少人知道正则表达式编译实际上是什么。我在网上看过，在我看来，这是一个比我认为的更古老的话题。

所以，是的，在阅读这个问题之前，谁知道正则表达式编译是通过将正则表达式转换为 epsilon-nondeterministic 有限自动机来执行的？谁不知道那是什么？

对于初学者来说，这是一个家庭作业问题。我有一个想法，但我仍然无法得到正确的答案。我不是在寻求答案，我只是在寻求帮助来回答问题。

我目前正在尝试为该语言编写上下文无关语法

因此，基本上 a 的数量是 b 的两倍，而两者之间的 ad。例如：

这是关于我所拥有的，我没有太多......我理解这些CFG的概念我只是不确定这个问题的逻辑。我不确定我是否朝着正确的方向前进......

谢谢。

我正在寻找一种算法，如果正则表达式和上下文无关语法的交集为空，则输出该算法。我知道这个问题是可判定的，但是，我找不到任何示例实现（在伪代码中）。

如果可能的话，有人可以在.NET 中为我提供这样的算法，但这不是必须的。这个问题也被称为“正则交叉”。谷歌搜索它只会给我几何算法或关于它的理论。

编辑：

任何人。我真的坚持下去，还找不到任何东西。

我在网上找不到任何小程序或程序来将上下文无关语言转换为下推自动机......任何帮助将不胜感激。

I have a language with statements of 4 kinds: s00, s01, s10, s11 where a leading 1 means initial keyword, a trailing 1 means terminated, and I have a separator ";". I can terminate any statement with ";". I would like to parse a language allowing a list of statements which allows minimal use of ";". The parser is Dypgen which is GLR+.

Example:

Is it possible to do this at all? If so, how? If not, why?

I believe it can't be done, mainly because I can't think of how to do it :) However it does seem context sensitive: the rule is you have to insert a ";" between A and B if A is not terminated and B is not initiated, ditto for B and C which means B is used twice.

However because the parser is GLR+ it is tempting to just use

as the rule, and if it misparses throw in a ";" (which is an s11 no-op) to resolve the ambiguity. It would be nicer if the parser would report a syntax error though. Perhaps this could be done when merging alternate s productions. The real problem is when they overlap instead of merging: if this occurs a program parse could explode.

我正在复习（不是家庭作业）一些计算理论并遇到了这个问题：

您如何证明常规语言集是上下文无关语言集的适当子集。

现在我知道一种语言是规则的，如果它被有限自动机接受。

而且我知道一种语言是无上下文的，前提是它被下推自动机接受。

但我不确定解决方案是什么。

我与另一位程序员同事就接口的范围发生了争执。

假设我们有以下内容：

所以问题是： 1. fooClassInstance 是否有可能在其他东西释放 fooInterface 实例之前超出范围？

有人认为对象 (fooClassInstance) 可能超出范围。

我相信它不能。当然，当 GC 决定对象不再在范围内时，对象可能会或可能不会被 GC 处理掉。然而，由于接口在设计上是一个抽象契约，其成员必须由使用它的对象实现，所以只要使用接口，接口就不会失去其实现。它不像是创建一个“接口”类型的另一个对象。接口只是指向实现者的那些抽象成员的指针。

你们能帮我解决这个纠纷吗？

谢谢，

真正的现代正则表达式实际上可以识别哪一类语言？

每当存在带有反向引用（例如(.*)_\1）的无限长度捕获组时，正则表达式现在正在匹配非常规语言。但这本身并不足以匹配诸如S ::= '(' S ')' | ε匹配括号对的上下文无关语言之类的东西。

递归正则表达式（对我来说是新的，但我确信存在于 Perl 和 PCRE 中）似乎至少可以识别大多数 CFL。

有没有人做过或读过这方面的研究？这些“现代”正则表达式的局限性是什么？他们对 LL 或 LR 语法的识别比 CFG 严格多还是严格少？或者是否存在两种语言都可以被正则表达式识别但不能被 CFG 识别，反之亦然？

相关论文的链接将不胜感激。

有一次，一位数学家告诉我，只要我们掌握一门语言，一个项目就可以实现。你能帮我理解我们如何知道我们什么时候做，什么时候不做吗？例如示例或自动化测试是否可以知道什么是“语言”，什么不是。谢谢