如果您记住自动机生成这些语言,您可能会更好地理解。
正则语言由正则自动机生成。它们只具有过去的有限知识(与计算内存限制相关),所以每当您有一个依赖于前缀的后缀的语言(回文语言),就无法使用正则语言进行处理。
上下文无关语言由非确定性下推自动机生成。它们具有某种有限的过去知识(堆栈,与正则自动机不同,堆栈没有限制),但是堆栈只能从顶部查看,因此您不具有完整的过去知识。
上下文相关语言由线性受限非确定性图灵机生成。它们知道过去并且可以处理不同的上下文,因为它们是非确定性的并且可以在任何时间访问所有过去的内容。
无限制语言由图灵机生成。根据Church-Turing-Thesis,图灵机能够计算您能想象到的一切(这意味着一切可判定的事情)。
常规语言:这些语言可以用有限自动机回答是/否问题。
上下文无关语言:当给定输入单词(使用状态机和堆栈)时,我们总是可以回答是/否是否为该语言的成员。
上下文相关语言:只要语法中的产生式不会缩小(α -> β),我们就可以回答是/否(使用状态机和与输入大小成线性关系的一块内存)。
递归可枚举语言:它可以回答是,但在否的情况下将进入无限循环。
请参见此视频以获取完整说明。