feather12315
2017-07-08 21:03:25 +08:00
问题一：
我是这么理解正则表达式的：它是有限自动机的一个实现（或者说一个实例）。有限自动机的实现还有 TCP 状态之间的转换。那么，IF-ELSE 这算是上下文无关语法的实现吗？
我不明白你所谓的实现是什么意思。正则表达式描述了一个语言结构，有限自动机来识别这个语言，正则表达式可以转换为有限自动机，有限自动机运行时和程序差不多，从某种意义上看，正则表达式也就是程序。有限自动机可以认为是一个抽象的模型，具体化下来可以有很多实例，如程序运行，协议运行。同样，if 结构也是一个语言，但是正则表达式描述不了，上下文无关语法可以描述。你所谓的实现，前后含义好像并不一样。在形式化方法中，你要定义实现，才能讨论后续的问题。如果你定义实现为一个实例，那么把有限自动机定义中的 5 元组分别给出来，可以得到很多具体的有限自动机例子，当然可以包含 TCP 转换。同样 CFG 的 4 元组分别给出了，可以得到很多具体的 CFG 例子，当然包含 if 结构。从这个意义上看，正则表达式是有限自动机的一个实现，就是不对的。
问题二：
没记错的话，含有 顺序连接 / 循环(WHILE) / 跳转(IF-ELSE) 这三种连接结构的计算机语言是完备的，这个完备性是怎么证明的呢？能给点相关的资料吗？
结构化程序设计的思想最早是 Dijkstra 提出的，用 baidu 找“选择 循环 顺序 Dijkstra ”，可以找到相关资料，还有 1966 年 Corrado Böhm 和 Giuseppe Jacopini 给出了证明。这些太老了，实在没有必要浪费时间去看。
我老师的回答= =