gpt4 book ai didi

formal-languages - 递归语言与上下文敏感语言

转载 作者:行者123 更新时间:2023-12-01 02:55:40 25 4
gpt4 key购买 nike

在乔姆斯基的层次结构中,没有定义递归语言集。我知道递归语言是递归可枚举语言的一个子集,并且所有递归语言都是可判定的。

我很好奇递归语言与上下文敏感语言的比较。我可以假设上下文相关语言是递归语言的严格子集,因此所有上下文相关语言都是可判定的吗?

最佳答案

如果您的问题只是每个上下文敏感语言是否都在所有递归语言的集合中,那么您应该尝试通过形式自动机以经典方式证明它。问问自己什么正式自动机可以模拟上下文敏感语言的生成以及什么用于生成递归语言。然后尝试使用另一个来模拟一个。一旦你在你的教科书中找到了正确的自动机,你肯定能够证明你想要什么。

关于formal-languages - 递归语言与上下文敏感语言,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3057231/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com