shrik3
·
字问题（决策问题）、复杂性与计算模型
💡
原文英文，约500词，阅读约需2分钟。
📝
内容提要
文章讨论了语言的字问题及其复杂性。字问题是判断一个单词是否属于某个语言。可判定语言的特征函数可计算，而半可判定语言只能确认单词是否在语言中。不同类型语言的字问题复杂性从线性时间到指数时间不等，文章还提到语言描述的不同形式及其相互转换。
🎯
关键要点
- 字问题是判断一个单词是否属于某个语言。
- 可判定语言的特征函数是可计算的，可以确定单词是否在语言中。
- 半可判定语言只能确认单词是否在语言中，但无法确定单词是否不在语言中。
- 不同类型语言的字问题复杂性从线性时间到指数时间不等。
- 语言的描述形式多样，包括文法和自动机等，且可以相互转换。
❓
延伸问答
什么是字问题？
字问题是判断一个单词是否属于某个语言的决策问题。
可判定语言和半可判定语言有什么区别？
可判定语言的特征函数可计算，可以确定单词是否在语言中；而半可判定语言只能确认单词是否在语言中，但无法确定单词是否不在语言中。
不同类型语言的字问题复杂性如何？
不同类型语言的字问题复杂性从线性时间到指数时间不等，具体取决于语言的类型。
字问题的计算模型有哪些？
字问题的计算模型包括图灵机、非确定性图灵机、非确定性下推自动机和有限状态机等。
如何判断一个单词是否属于某个语言？
可以通过计算语言的特征函数来判断，若特征函数返回真，则单词属于该语言。
语言的描述形式有哪些？
语言的描述形式包括文法和自动机等，且这些描述形式可以相互转换。
➡️
