【编译原理】构造下述文法G[S]的确定有限自动机，并给出该文法的语言的正规表达式 S->Aa|ε A->Aa|Sb|a

Question

麻烦帮忙给出NFA图，谢谢

Answer 1

通过联立方程组求正规表达式：
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。
注意：以上求解的过程中“|”和“+”是等价的，都表示“或”的意思，它们的相互替换是为了描述的方便。