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。
注意：以上求解的过程中“|”和“+”是等价的，都表示“或”的意思，它们的相互替换是为了描述的方便。
编译原理题目
1、文法G:S→xSx|y所识别的语言是 。 a. xyx b. (xyx)* c. xnyxn(n≥0) d. x*yx*2、文法G描述的语言L(G)是指 。 a. L(G)={α|S+ ⇒α , α∈VT*} b. L(G)={α|S*⇒α, α∈VT*}c. L(G)={α|S*⇒α,α∈(VT∪VN*)} d. L(G)={α|S+ ⇒α, α∈(...
给力!2011年新年散分啦。高分求助编译原理高手帮忙做几道模拟题_百度知...
(1)若出现 a ，则其后至少紧跟两个 c ；(2)若出现 b ，其后至少紧跟一个 c 。试构造识别 L 的最小化的 DFA ，并给出描述 L 的正规表达式。答：DFA 如图所示。相应的正规式为 (c|acc|bc)* 。五、（ 12 分） 已给文法 G[S] ： S → SaP | Sf | P P → qbP | q 将 G[...
as=bbb,a=bc,s=cc,asb=( )c.
7、Chomsky把文法分为种类型,编译器构造中采用和文法,它们分别产生和语言,并分别用和自动机识别所产生的语言。解答1、空集终结符右2、最左3、自上而上自下而上4、自上而上5、语法分析6、移进接受7、42型3型上下文无关语言正规语言下推自动机有限四、判断题1、文法S→aS|bR|ε描述的语言是(a|bc)*()R→...
编译原理试题
1、文法G:S→xSx|y所识别的语言是 。 a. xyx b. (xyx)* c. xnyxn(n≥0) d. x*yx*2、文法G描述的语言L(G)是指 。 a. L(G)={α|S+ ⇒α , α∈VT*} b. L(G)={α|S*⇒α, α∈VT*}c. L(G)={α|S*⇒α,α∈(VT∪VN*)} d. L(G)={α|S+ ⇒α, α∈(...
编译原理题目
2、文法G描述的语言L(G)是指 。 a. L(G)={α|S+ ⇒α , α∈VT*} b. L(G)={α|S*⇒α, α∈VT*}c. L(G)={α|S*⇒α,α∈(VT∪VN*)} d. L(G)={α|S+ ⇒α, α∈(VT∪VN*)} 3、有限状态自动机能识别 。 a. 上下文无关文法 b. 上下文有关文法c.正规文法 d. ...
