乔姆斯基的层次结构和图灵机应该如何影响语言设计？
我目前正在学习离散数学测试，其中我们正在学习 乔姆斯基层次结构 和类型识别层次结构每个级别的自动机。 我被告知大多数计算机语言都属于层次结构的“第 2 级和第 1 级”，但不知道具体如何。
我的问题是：
每个级别都有哪些功能？
这只是理论依据吗？ 我想知道像 Dennis Ritchie 和 James Gosling 这样的语言设计师在设计 C 和 Java 时是否必须考虑到这一点。 他们有吗？ 有人会如何应用这个？
我们被告知图灵机可以识别层次结构的第 0 级。 如果有，是否有属于 0 级的语言特性？ 我猜这可能是自然语言处理，是吗？
I'm currently studying for a discrete mathematics test in which we are learning Chomsky's hierarchy and the type of automatas that recognize each level of the hierarchy. I'm being taught that most computer languages fall within "level 2 and 1" of the hierarchy, but not precisely how.
My questions are:
What features belong to each level?
Is this nothing more than theoretical basis? I'm wondering if language designers like Dennis Ritchie and James Gosling had to go into this considerations when designing C and Java. Do they? How would someone apply this?
We are being told that Turing Machines recognize the level 0 of the hierarchy. If so, are there any language features that belong to level 0? I'm guessing that this may be natural language processing, is it?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
没有。 1 级包括 2 级。
也许我误解了你的意思，所以要完整：
它有助于设计词法分析器和解析器。 我不知道 C 的创建者是否考虑过这一点，但 Java 肯定考虑过。 解析器生成器
图灵机计算任何可以计算的东西。 “可以计算”甚至被定义为：可以被图灵机接受。
当然，这包括自然语言处理。
任何高于 2 级的内容对于语言生成都不是很有用，因为读取此类输入的程序可能不会停止 (文字问题无法再解决）。
None. Level 1 includes Level 2.
Maybe I misunderstood you, so to be complete:
It helps in designing lexers and parsers. I do not know if the creators of C thought about that, but Java, certainly. Parser Generator
Turing Machines calculate anything that can be calculated. "Can be calculated" is even defined as: Can be accepted by a Turing Machine.
This includes, of course, natural language processing.
Anything above Level 2 is not very useful for language generation, because a program reading such inputs may not stop (Word Problem can no longer be solved).
类型 3 语法生成常规语言。 这些语言具有以下特征：以“xxx”开头、包含“xxx”、以“xxx”结尾、包含奇数个 y 等。有限自动机（确定性或非确定性）可识别这些语言。
类型 2 语法生成上下文无关语言。 这些语言具有一些特征，例如一定数量的 x 后面跟着更少、更多或相等数量的 y，或者一个单词后面跟着相同的单词，但顺序相反。 下推自动机识别这些语言......想想带有堆栈的有限自动机。
类型 1 语法生成上下文相关语言。 它们与 Type 0 语法非常接近，以至于通常很难发现它们之间的区别。 LBA（线性有界自动机）可以识别这些语言，想想资源有限的图灵机……想想现代计算机。
0 型语法生成图灵语言，有时称为递归可枚举语言。 这些基本上是您可以编写计算机程序来识别的任何语言，但它们实际上与 Type 1 混合，因为真正的计算机通常有某种内存限制。
有限自动机和下推自动机对于解决编写编译器时出现的问题非常重要。 然而，这不是你研究它们的原因，你研究它们是为了了解可以/不能计算的限制。 许多程序员认为可以用计算机解决任何问题。 可计算性理论告诉你的并非如此。
由“Dude”编辑 - 好吧，这是一个易于理解（且著名）的问题，任何图灵机或计算机或程序员或外星天才都无法解决该问题......
想象一下你有一些多米诺骨牌......但不是点，你在顶部和底部有一些简短的单词，比如“aba”和“cab”。 如果我给你 5 个、10 个或 50 个这样的多米诺骨牌，你能否将它们排列起来，使顶部所有连接在一起的单词与底部连接的单词完全匹配。 您可以为每张多米诺骨牌制作任意数量的副本。
示例多米诺骨牌（人为设计 :) (a/aab)、(aba/ac)、(cab/ab) 是一组 3 个多米诺骨牌，其中顶部 (a+aba+cab) 恰好等于底部 (aab+ac+ab) 。
尽管这听起来很简单，但一般来说它无法解决。
顺便说一句，当我第一次读/理解这个问题时......我在想......哦，n！ 开始看起来不错了！
Type 3 grammars generate regular languages. These are languages with features like begins with "xxx", contains "xxx", ends with "xxx", contains an odd number of y's, etc. Finite automata (deterministic or non) recognize these languages.
Type 2 grammars generate context-free languages. These are languages with features like some number of x's followed by fewer, or more, or equal number of y's, or where a word is followed by the same word, but reversed. Pushdown automata recognize these languages...think Finite automaton with a stack.
Type 1 grammars generate context-sensitive languages. These are so close to Type 0 grammars that it is often hard to find a difference between them. LBAs (linear bounded automatons) recognize these languages, think Turing machine with limited resources...think a modern computer.
Type 0 grammars generate Turing languages, sometimes called recursively enumerable languages. These are basically any language that you could write a computer program to recognize, but they really blend with Type 1, since real computers generally have some kind of memory limit.
Finite automata, and pushdown automata are very important in solving problems that arise when writing compilers. However, that isn't why you study them, you study them to learn the limits of what can/cannot be computed. Many programmers think you can solve any problem with a computer. Computability theory teaches you otherwise.
Edit by "Dude" - OK, here is an easy to understand (and famous) problem that cannot be solved by any Turing machine or computer or programmer or alien genius...
Imagine you have some dominoes...but instead of patterns of dots, you have some short word on the top and bottom, say words like "aba" and "cab". If I give you 5 or 10 or 50 of these dominoes, can you arrange them so that the words on top, all concatenated together, match exactly the concatenated words on the bottom. You can make as many copies as you like of each and any domino.
Example dominoes (contrived :) (a/aab), (aba/ac), (cab/ab) is a set of 3 dominoes where the tops (a+aba+cab) exactly equals the bottoms (aab+ac+ab).
As easy as this might sound, it cannot be solved in general.
BTW, when I first read/understood this problem...I was thinking....ooooh, n! is starting to look good!