已知2型文法G(S)相对应的2型语言为:L(G(S))={ambnanbm|m≥0,n≥1),则它的文法G(S)可描述为_______。
已知2型文法G(S)相对应的2型语言为:L(G(S))={ambnanbm|m≥0,n≥1),则它的文法G(S)可描述为_______。
已知2型文法G(S)相对应的2型语言为:L(G(S))={ambnanbm|m≥0,n≥1),则它的文法G(S)可描述为_______。
1. 文法G=({A,B,S},{a,b,c},P,S), 其中P 为: S→Ac|aB A→ab B→bc 写出L(G[S])的全部元素。 2. 文法G[S]为: S→Ac|aB A→ab B→bc 该文法是否为二义的?为什么? 3. 考虑下面上下文无关文法: S→SS*|SS+|a (1)表明通过此文法如何生成串aa+a*,并为该串构造语法树。 (2)G[S]的语言是什么? 4. 给出生成下述语言的二型文法: (1) {anbn | n >=0 } (2) { ambn | m≥n ≥0 } (3) {uawb | u,w ∈{a,b}*∧|u|=|w| } (4) { anbm | n≥2m ≥0 } (5) { anbm | n ≥ 0, m ≥ 0,3n≥m≥2n } (6) {wwR|w∈{a,b}*,wR 表示w的逆} (7) {uvwvR|u,v,w∈{a,b}+=1 } 5. 给出生成下述语言的三型文法: (1) {an | n >=0 } (2) { anbm | n,m>=1 } (3) {anbmck | n,m,k>=0 }
设有文法G(S)为: S→(B)a B→Bb|b|ε 下列叙述错误的是_______。
A.G是2型文法
B.L(G)={(bn)a|n≥0)
C.L(G)={(b)na|n≥0}
D.有文法G′为S→()a|(B)a B→bB|b,则G′=G
文法G(N)和G(S)为 G(N):N→NE|E|ND|D G(S):S→S(S)S|ε E→0|2|4|6|8|10 D→0|1|2|…|9 (1)文法G(N)和G(S)表示的语言分别是什么? (2)证明文法G(N)和G(S)均为二义文法。 (3)改写文法G(N)和G(S)为等价的非二义文法。
设文法G(S)的BNF描述为 S→S,E|E E→E+T|T T→T*F|F F→a|(E)|a[S] (1)给出G(S)的元语言符号集、文法符号集、终结符号集和非终结符号集。 (2)G(S)属于哪类文法?写出L(G(S))集合。 (3)判断符号串 $1:a,a+a[a[S]] $2:a*a,a+a[a] 是否为文法G(S)的句子,对是L(G(S))的句子给出对应的分析树。
设有文法G(S):S→SS*|SS+|a (1)G(S)的语言L(G(S))是什么? (2)下列字符串哪些是该文法的句子? $1:aa+aa*+a $2:aa+aaa*++ $3:aS+a* (3)对属于该文法的句子$i,画出其分析树。
已知语言 L(G(S))={a2m+1bm+1|m≥0}∪{a2mbm+2|m≥0} 则文法G(S)是_______。
给出下列文法Gi(i=1,2,3,4),写出G的语言L(Gi),并给出L(Gi)中的任意两个句子的最左推导和最右推导。 (1)G1:S→aa|aRa R→b|Rb (2)G2S→aSb|ab (3)C3:V→aaV|bc (4)G4=N→D|ND D→0 |1| 2 |…| 9