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

Question

我正在学习一项离散数学测试,我们正在学习乔姆斯基的层次结构和识别层次结构各个层次的自动机类型.我被教导说大多数计算机语言属于层次结构的"2级和1级",但不是精确的.

我的问题是:

1. 每个级别有哪些功能？

2. 这不过是理论基础吗？我想知道Dennis Ritchie和James Gosling这样的语言设计师在设计C和Java时是否需要考虑这些因素.他们呢？怎么会有人申请这个？

3. 我们被告知图灵机器识别层次结构的0级.如果是这样,是否有任何属于0级的语言功能？我猜这可能是自然语言处理,是吗？

Answer 1

1. 没有.1级包括2级.也许我误解了你,所以要完整:

   • 正则表达式匹配中使用常规语言.口语:DFA无法计算.如果你想匹配括号,你需要计算.[等级3]
   • 语言语法通常是上下文无关语言.见2)[等级2]
   • 上下文敏感语言仅在理论上使用.见3)[等级1]

2. 它有助于设计词法分析器和解析器.我不知道C的创造者是否会想到这一点,当然还有Java.分析器生成器

3. 图灵机计算任何可以计算的东西."可以计算"甚至定义为:图灵机可以接受.当然,这包括自然语言处理.高于等级2的任何内容对于语言生成都不是很有用,因为读取此类输入的程序可能无法停止(Word问题无法再解决).