题目

请问编译原理中a(a|b)*a和aa*b*a有什么区别,

提问时间：2021-03-19

答案

涉及到一个优先序问题,前一个正则式接受两个a之间有0长度或任意长度的{a,b}字符串序列,而后一个正则式则只允许两个a之间有的{a,b}序列必须满足：如果a、b同时存在,则a必须在b前面,也就是只接受左右两端全是a,只有中间是b这种夹心饼***形式.举个栗子你就明白了：
a(a|b)*a可以接受的输入序列有：aa aaa aba abba aaba abaa
aa*b*a 可以接受的输入序列有：aa aaa aaba aba aaabba 不能接受abaa