【编译原理】构造下述文法G[S]的确定有限自动机,并给出该文法的语言的正规表达式 S->Aa|ε A->Aa|Sb|a
答案:1 悬赏:40
解决时间 2021-01-23 14:38
- 提问者网友:疯子也有疯子的情调
- 2021-01-22 19:16
【编译原理】构造下述文法G[S]的确定有限自动机,并给出该文法的语言的正规表达式 S->Aa|ε A->Aa|Sb|a
最佳答案
- 二级知识专家网友:何以畏孤独
- 2021-01-22 19:36
通过联立方程组求正规表达式:
A = Aa|Sb|a = Aa|(Aa|ε)b|a= Aa+(Aa+ε)b+a=Aa+(Aab+b)+a=Aa+Aab+b+a=A(a+ab)+(b+a)
根据方程X=Xt+r 必有X=t*r解的论断,可得A=(a+ab)*(b+a),进而可求得:
S = Aa|ε = Aa+ε = Aa = (a+ab)*(b+a)a = (a|ab)*(b|a)a
即文法的正规表达式为: (a|ab)*(b|a)a。
注意:以上求解的过程中“|”和“+”是等价的,都表示“或”的意思,它们的相互替换是为了描述的方便。
A = Aa|Sb|a = Aa|(Aa|ε)b|a= Aa+(Aa+ε)b+a=Aa+(Aab+b)+a=Aa+Aab+b+a=A(a+ab)+(b+a)
根据方程X=Xt+r 必有X=t*r解的论断,可得A=(a+ab)*(b+a),进而可求得:
S = Aa|ε = Aa+ε = Aa = (a+ab)*(b+a)a = (a|ab)*(b|a)a
即文法的正规表达式为: (a|ab)*(b|a)a。
注意:以上求解的过程中“|”和“+”是等价的,都表示“或”的意思,它们的相互替换是为了描述的方便。
我要举报
如以上问答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
推荐资讯