什么是概率上下文无关文法上下文无关文法能描述一个能被下推自动机识别的语言，即上下文无关语言；图灵机可以识别递归可枚举语言。X图灵等价是指X能做图灵机能做的所有事情， 图灵机能做X能做的所有事情。X图灵完备是指X能做图灵机能做的所有事情。通常说X编程语言是上下文无关语言是指能通过X编程语言的语法分析的语言是上下文无关语言，也就是说识别通过X编程语言的语法分析的语言的文法是上下文无关文法。而实际上，能通过X编程语言的编译的语言完全可能是递归可枚举语言。举个例子，通过C++的语法分析的语言是上下文无关语言（这里可能不是很严格，有可能通过语法分析的时候就已经不是上下文无关语言了），也就是说下面代码可能就能通过C++的语法分析，然而它并不能通过编译。
而由于C++强大的模板功能，所以实际上能通过C++的编译的语言实际上应该是递归可枚举语言。所以编译C++的自动机是图灵等价的（有趣的结论：大家可以写一个C++程序，使得编译器的编译过程陷入死循环；当然，这里的图灵等价不是严格的，毕竟大家的机器的存储空间不是无限的）。对于编译出来的文件，因为都是执行在图灵等价的计算机上（这里的图灵等价也不是严格的，理由跟之前一样），所以编译出来的文件最极限的就是能做所有图灵机能做的事情，因此，如果编译出来的文件是图灵等价的，那么他就已经到达极限了。不过是否有一个自动机能做图灵机做不了的事情现在还没有定论，所以如果存在这样的机器（比如假想的Oracle machine），就可以有不是图灵等价并且是图灵完备的编程语言了。因此：1.那如果文法就是图灵等价的，写出的程序会不一样么？不会。2.还是说二者本来就没关系，语言用哪类文法不过是设计者随性而为。没有关系。不是随性的吧。3.或者说因为图灵机定义了程序能力的上限，当然。不过可能有比图灵机更厉害的自动机哦，如果在上面跑程序就突破图灵机的上限了。4.所以反过来，语言文法越简单越好，比如3型文法更好？都说了不是随性的啦。