我对什么是turing-machineturing-complete语言有所了解,但是为了更好地理解,有人可以举出一些图灵不完整的语言示例吗? (也许甚至不是图灵机?)

最佳答案

在正式定义中,正则表达式仅包含:

  • 串联(ab)
  • 无界重复(a *)
  • 交替(a | b)
  • 分组((ab)|(cd))

  • 只能识别常规语言。图灵完备的编程语言可以识别递归枚举的语言。

    一个例子是,正则表达式不能告诉您字符串是否由匹配的括号对组成:例如,接受()(())而拒绝()((())(),而图灵完备的编程语言可以接受。

    (请注意,现代编程语言中的正则表达式比正则表达式的正式学术定义更强大。有些甚至可能是图灵完整的。)

    09-30 14:31
    查看更多