什么是概率上下文无关文法

问题描述

精选答案

上下文无关文法能描述一个能被下推自动机识别的语言，即上下文无关语言；图灵机可以识别递归可枚举语言。

X图灵等价是指X能做图灵机能做的所有事情， 图灵机能做X能做的所有事情。X图灵完备是指X能做图灵机能做的所有事情。通常说X编程语言是上下文无关语言是指能通过X编程语言的语法分析的语言是上下文无关语言，也就是说识别通过X编程语言的语法分析的语言的文法是上下文无关文法。而实际上，能通过X编程语言的编译的语言完全可能是递归可枚举语言。举个例子，通过C++的语法分析的语言是上下文无关语言（这里可能不是很严格，有可能通过语法分析的时候就已经不是上下文无关语言了），也就是说下面代码可能就能通过C++的语法分析，然而它并不能通过编译。而由于C++强大的模板功能，所以实际上能通过C++的编译的语言实际上应该是递归可枚举语言。所以编译C++的自动机是图灵等价的（有趣的结论：我们可以写一个C++程序，使得编译器的编译过程陷入死循环；当然，这里的图灵等价不是严格的，毕竟我们的机器的存储空间不是无限的）。对于编译出来的文件，因为都是执行在图灵等价的计算机上（这里的图灵等价也不是严格的，理由跟之前一样），所以编译出来的文件最极限的就是能做所有图灵机能做的事情，因此，如果编译出来的文件是图灵等价的，那么他就已经到达极限了。不过是否有一个自动机能做图灵机做不了的事情现在还没有定论，所以如果存在这样的机器（比如假想的Oracle machine），就可以有不是图灵等价并且是图灵完备的编程语言了。因此：

1. 那如果文法就是图灵等价的，写出的程序会不一样么？不会。

2. 还是说二者本来就没关系，语言用哪类文法不过是设计者随性而为。没有关系。不是随性的吧。

3. 或者说因为图灵机定义了程序能力的上限，当然。不过可能有比图灵机更厉害的自动机哦，如果在上面跑程序就突破图灵机的上限了。

4. 所以反过来，语言文法越简单越好，比如3型文法更好？都说了不是随性的啦。