关于语言A与B的正则性、上下文无关性及可判定性的判定问询

语言A：A = {a^n b^(2n+6) | n >= 0} #

正则性判定 #

你说得对，A绝对不是正则语言。正则语言只能用有限状态自动机识别，而这类自动机没有存储能力来记录a的数量，根本无法匹配“b的数量是a的2倍加6”这种依赖关系，所以肯定不符合正则语言的特征。

上下文无关性判定 #

其实A是上下文无关语言，你的泵引理用法可能有误区哦。我们可以直接构造一个上下文无关文法（CFG）来生成它：

S → aSbb | C
C → bbbbbb  // 对应n=0时的6个b

这个文法的逻辑很直观：每生成一个a，就对应生成两个b，最后补上固定的6个b，完美匹配a^n b^(2n+6)的结构。至于上下文无关语言的泵引理，只要选对泵的部分（比如泵aSbb片段里的a和对应的bb），泵后的字符串依然满足数量关系，不会违反泵引理的要求，所以A确实是上下文无关语言。

可判定性判定 #

所有上下文无关语言都是可判定的——我们可以用下推自动机直接识别它，或者用CYK算法等方法判断任意字符串是否属于A，所以A肯定是可判定语言。

语言B：B = { (ab)^2n | n >= 0} #

正则性判定 #

B是正则语言，我们可以把它等价改写为((ab)(ab))^n，也就是(abab)^n（n≥0），对应正则表达式(abab)*。我们甚至可以很简单地构造有限状态自动机来识别它：初始态0→读a到状态1→读b到状态2→读a到状态3→读b回到状态0，状态0设为接受态，这样就能识别所有由abab重复任意次（包括0次，也就是空串）的字符串。

上下文无关性判定 #

正则语言是上下文无关语言的子集，所以B自然也是上下文无关语言——正则文法本身就是上下文无关文法的一种特例，直接沿用正则对应的文法即可。

可判定性判定 #

正则语言都是可判定的，所以B肯定是可判定语言，用对应的有限状态自动机就能直接判定任意字符串是否属于B。

备注：内容来源于stack exchange，提问作者user1179819