文法、正规式相关习题

S-->bA

A--->aA|a

S-->AB

A-->aA|a

B-->bB|b

S-->aSb|ab

S-->aSb|b

S-->aSbb|ε

S-->aSbb|abb

S-->Xb|b

X-->aXbb|ε

S-->Xb

X-->aXbb|abb

以下哪个文法的语言是

A.S-->abbS|b

B.S-->aSbb|ε

C.S-->aSb|b

D.S-->aSbb|b

D

7.已知文法G[S]为：S-> aSbb | a 该文法描述的语言是：（ ）
A.L={anb2n |n≥1}
B.L={an+1b2n |n≥0}
C.L={ambn |m、n≥0}
D.L={anbn+1 |n≥0}

B

8.(多选题) 给定语法A–>bAcc|ε,下面的符号串中为该文法的句子是()
A. bcc
B. bcbc
C. bcbcc
D. bccbcc
E. bbcccc

AE

L(G)={bnc2n|n≥0}

14.(单选题) 有文法G[S]: S->aSbb|ε则L(G)是？
A. {ε,a,bb,abb}
B. {anbn|n≥0}
C. {anb2n|n≥1}
D. {anb2n|n≥0}

D

15.(单选题) 下列哪个文法是线性文法。
A.
G1[S]:S →aS|aB
B →bB|bC
C →cC|c

B.
G2[S]:S →aS|aB
B →Bb|Cb
C →Cc|c

C.
G3[S]:S →aSBC
B →bBC
C →cC|c

D.
G4[S]:S →aSb|ab

A

3型文法（左线性、右线性文法）

(1) {0,1}上的含有子串010的所有串；

(2) {0,1}上不含子串010的所有串。