关于编译原理中的关于正规式的一道验证题

Question

编译原理中(a|b)*与(a*b*)*相等 我知道是经典的相等 但我还是觉得搞不明白 所以希望大家能给出基本的验证么 我知道有点麻烦
希望大家能多帮帮

Answer 1

可以这样想：
1、 a|b的意思是a、b中任取一个，(a|b)*就是任取一个的任意组合，长度不限，且对a、b出现的顺序，个数等没有限制，也就是a、b两个字符组成的任意串。
2、a*b*的意思是a取0到任意多个，b也是。因为包含0个，所以对个数无限制，只是说a出现在b之前，而(a*b*)*则解除了这个顺序限制，也是任意串。
所以两者都是集合{a，b}的任意串。

Answer 2

个人感觉画出NFA最直观易懂了。前一个正规式仅有一个状态（开始和接受状态同），后一个虽然是三个状态，但是其中一个是绕着a闭包的状态，一个是绕着b闭包的状态，而这两个状态又是绕着第三状态（既是开始状态又是接受状态）进行闭包，所以实际上可合并为一种状态，即是说这两个正规式对应于同一个NFA，所以相等是显然成立的。本回答被网友采纳