[编译原理]构造一个正则表达式,它接受S={a,b,c}上符合以下规则的字符串：如果以a开头,则串内至少包含一个c；如果以b开头,则串内至多包含一个a.求编译原理大神解答>

Question

[编译原理]构造一个正则表达式,它接受S={a,b,c}上符合以下规则的字符串：
如果以a开头,则串内至少包含一个c；如果以b开头,则串内至多包含一个 a.
求编译原理大神解答>_

Answer 1

（1）如果以a开头,则串内至少包含一个c ----> 可以写成a(a|b|c)*c(a|b|c)*
（2）如果以b开头,则串内至多包含一个 a ----> 有两种情况,一个是不包含a,可以写成b(b|c)*；另一个是只有一个a,可以写成b(b|c)*a(b|c)* ,结合起来就是b(b|c)* | b(b|c)*a(b|c)*
（3）综合前面（1）和（2）,有
a(a|b|c)*c(a|b|c)* | b(b|c)* | b(b|c)*a(b|c)*