theory - 乔姆斯基的层次结构和图灵机应如何影响语言设计？

Question

我目前正在研究离散数学测试，其中我们正在学习Chomsky's hierarchy和识别层次结构各个级别的自动机的类型。有人告诉我，大多数计算机语言都属于层次结构的“2级和1级”，但不完全属于该级别。

我的问题是:

每个级别都有哪些功能？

这仅是理论依据吗？我想知道像Dennis Ritchie和James Gosling这样的语言设计师在设计C和Java时是否必须考虑这些因素。有吗有人将如何应用呢？

我们被告知图灵机可以识别层次结构的级别0。如果是，那么是否存在属于级别0的语言功能？我猜这可能是自然语言处理，对吗？

Answer 1

无。 1级包括2级。
也许我误会了你，所以要完整一点:

正则表达式匹配中使用了正则语言。口语化:DFA无法计数。如果要匹配方括号，则需要计算。 [等级3]

语言语法通常是上下文无关语言。查看2)[等级2]

上下文敏感语言仅在理论上使用。查看3)[等级1]

它有助于设计词法分析器和解析器。我不知道C的创建者是否考虑过这一点，但是Java确实可以。 Parser Generator

Turing Machines可以计算任何东西。 “可以计算”甚至定义为:可以被图灵机接受。
当然，这包括自然语言处理。
高于2级的任何内容对于生成语言都不是很有用，因为读取此类输入的程序可能不会停止(无法解决Word Problem)。