有没有用“真实”语言抽取引理的例子？

L = {0 ^ÑÑÑ：N ≥ 0}

（顺便说一下，是不一个上下文无关的语言）。

但我感兴趣的是：是否有任何使用任何远程真实或有用语言的例子？我一直无法找到任何。这些东西之一还是纯粹的理论价值，绝对没有实际应用？

2010-01-26 cletus

能够证明一种语言是否经常使用？ – 2010-01-26 01:37:16

@Anon：是的，因为语言是否可以用上下文无关语法来描述对解析器生成器是有价值的。 – cletus 2010-01-26 01:38:42

我花了一段时间才弄清楚为什么L不是上下文无关的语言。我认为一个很好的方法来思考答案是：如果你想写n 0的话，通过向堆栈添加一些东西来追踪它。然后打印n 1，通过删除堆栈中的所有项目来跟踪。但是，现在没有办法记住n是打印n 2的。 – 2010-03-13 17:31:24

L = {0 ^ÑÑ：N ≥ 0}是一个上下文无关语言。

在表达括号匹配可以被认为是类似的形式的即

L = {（^Ñ）^Ñ：N ≥ 0}

2010-01-26 01:39:57 Arnkrishn

呃......这些都不是我称之为“真实”的语言。我知道它是如何应用于这些人造的例子。我想要的是至少有一个它被应用于编程语言或任何远程“现实世界”的例子。 – cletus 2010-01-26 02:17:19

匹配圆括号（或括号，引号）是不是现实世界？ – 2010-07-16 13:54:17

实际用途之一是，每个人可以停止尝试构建有限自动机来识别C＃或Fortran的语法。

另一个实际用途是，每个人都可以停止尝试构建一个下推自动机来识别C＃或Fortran的语义。（即使在Fortran中，如果拼错了变量名称，您将获得一个免费的新变量，但新变量可能不适用于您打算命名其中一个声明变量时编码的操作员。）

2010-01-26 01:59:06

我并没有描述为什么它很有用，但它如何被应用到真正的语言，而不是abc或012的序列。 – cletus 2010-01-26 02:16:11

@cletus设计编译器是在真实世界之外，以非真实语言进行设计的吗？ – 2010-01-26 21:30:15

“Is这些东西还是纯粹的理论价值，绝对没有实际应用？“

Hrm。什么是实际应用？你明智地标记了你的问题“计算机科学”。所以，我想你的问题意味着要问，“是不是实用的计算机科学？

在这种情况下，答案是...

当然是！这是教作为第一途径之一对于不同的语言复杂性类进行分类，不仅仅是“big-O（whateverthehell）” 它表明除了运行时之外，还有一些关于计算的问题，在这种情况下，某些模型根本无法计算某些函数* 这是一个相当低的 - 关于自动机理论的正式证明的球介绍

大部分计算机科学专业的学生（我的同学）热衷于避免的是计算理论，这是一种抽象外观明显落后的分类。

这个充满希望的事实是计算理论是否是计算机科学的基础。为了不掌握不同复杂类别的想法（大O本身并不能削减它）不会拼写出计算机科学家的死亡，但它将隐藏他或她的视野中相当大一部分的领域。

*是的，通常暂停问题显示为第一次，但他们从来没有第一次得到它。

至于你的问题可能是对你的问题更加愤世嫉俗的解释，你的意思是“任何一个软件真的使用这个？”，我的答案当然不是。它是计算基础的一部分，而不是其应用。这不是对其申请表示不屑一顾，完全没有。两者都是平等的，高贵的价值。

2010-01-26 21:20:27 agorenst

这是一个可爱的演讲和所有，但它并没有回答这个问题：我在使用它的真实世界的例子 – cletus 2010-01-26 21:52:58

也许你错过了森林的树木**教育**或者你最好澄清你认为“真实世界”是什么意思？ – agorenst 2010-01-27 06:23:04

这Python程序是有效的：

print ((((((((((((((((((((((((1))))))))))))))))))))))))

以及与右侧等量的(在左侧和)所有其它等效的语句。

您不能构建正则表达式来验证，因此您必须使用解析器。

这完全不是理论上的。这是你不能使用正则表达式来解析HTML的原因。

2010-07-16 06:26:57

回答