NEW
Font size
S
M
L
XL
Worksheetschương trình dịch chương 3
Total questions: 40
Worksheet time: 30mins
Name
Class
Date
1.
Câu 1 : Có bao nhiêu chuỗi có độ dài nhỏ hơn 4 chứa ngôn ngữ được miêu tả bởi biểu thức chính quy (How many strings of length less than 4 contains the language described by the regular expression) (x+y)*y(a+ab)*?
a)
A. 7
b)
B. 10
c)
C. 12
d)
D. 11
2.
Câu 2 : Biểu thức chính quy nào đúng?
a)
A. (01)*0 = 0(10)*
b)
B. (0+1)*0(0+1)*1(0+1) = (0+1)*01(0+1)*
c)
C. (0+1)*01(0+1)*+1*0* = (0+1)*
d)
D. Cả ba biểu thức đã cho đều đúng
3.
Câu 3 : Một ngôn ngữ là chính quy nếu và chỉ nếu
a)
A. Được chấp nhận bởi DFA
b)
B. Được chấp nhận bởi PDA
c)
C. Được chấp nhận bởi LBA
d)
D. Được chấp nhận bởi máy Turing
4.
Câu 4 : Biểu thức nào không phải là biểu thức chính quy?
a)
A. [(a+b)*-(aa+bb)]*
b)
B. [(0+1)-(0b+a1)*(a+b)]*
c)
C. (01+11+10)*
d)
D. (1+2+0)*(1+2)*
5.
Câu 5 : Biểu thức chính quy là
a)
A. Ngôn ngữ thuộc lớp 0
b)
B. Ngôn ngữ thuộc lớp 1
c)
C. Ngôn ngữ thuộc lớp 2
d)
D. Ngôn ngữ thuộc lớp 3
6.
Câu 6 : Văn phạm gồm các luật sinh: S->AA A->aa A->bb mô tả ngôn ngữ nào?
a)
A. L = {aaaa,aabb,bbaa,bbbb}
b)
B. L = {abab,abaa,aaab,baaa}
c)
C. L = {aaab,baba,bbaa,bbbb}
d)
D. L = {aaaa,abab,bbaa,aaab}
7.
Câu 7 : Biểu thức chính quy (x/y)(x/y) ký hiệu bởi tập?
a)
A. {xy,xy}
b)
B. {xx,xy,yx,yy}
c)
C. {x,y}
d)
D. {x,y,xy}
8.
Câu 8 : Văn phạm gồm các luật sinh: S->aSbb, S->abb là
a)
A. Văn phạm lớp 3
b)
B. Văn phạm lớp 2
c)
C. Văn phạm lớp 1
d)
D. Văn phạm lớp 0
9.
Câu 9 : Biểu thức chính quy x/y ký hiệu bởi tập
a)
A. {x,y}
b)
B. {xy}
c)
C. {x}
d)
D. {y}
10.
Câu 10 : Biểu thức chính quy nào có thể không tồn tại ký hiệu 0 hoặc 1
a)
A. 1 + 0(1+0)*
b)
B. (0+1)(1+0)*
c)
C. (1+0)
d)
D. (00+0111+10)*
11.
Câu 11 : Biểu thức chính quy nào ký hiệu ZERO hoặc nhiều hơn x hoặc y
a)
A. (x+y)
b)
B. (x+y)*
c)
C. (x* + y)
d)
D. (xy)*
12.
Câu 12 : Tìm cặp biểu thức chính quy tương đương nhau
a)
A. (0+1)* và (0*+1*)*
b)
B. (0+1)* và (0+1*)*
c)
C. (0+10)* và (0*+10)*
d)
D. Tất cả các cặp đều tương đương
13.
Câu 13 : Biểu thức chính quy a/b ký hiệu bởi tập:
a)
A. {a}
b)
B. {epsilon,a,b}
c)
C. {a,b}
d)
D. {ab}
14.
Câu 14 : Mối quan hệ giữa ngôn ngữ được chấp nhận NFA và ngôn ngữ được chấp nhận DFA
a)
A. >
b)
B. <
c)
C. =
d)
D. <=
15.
Câu 15 : Trong biểu thức chính quy, toán tử * có chức năng:
a)
A. Nối
b)
B. Chọn
c)
C. Lặp
d)
D. Cộng
16.
Câu 16 : Cho trước ngôn ngữ L = {ab, aa, baa}, những chuỗi nào bên dưới thuộc ngôn ngữ L*? 1) abaabaaab; 2) aaaabaaaa; 3) baaaaabaaaab; 4) baaaaabaa
a)
A. 1, 2 và 3
b)
B. 2, 3 và 4
c)
C. 1, 2 và 4
d)
D. 1, 3 và 4
17.
Câu 17 : Văn phạm gồm các luật sinh S ->abS; S->a được gọi là
a)
A. Văn phạm tuyến tính phải
b)
B. Văn phạm tuyến tính trái
c)
C. Văn phạm tuyến tính trái và Phải
d)
D. Không phải văn phạm trái và Phải
18.
Câu 18 : Văn phạm gồm các luật sinh A->Bx; A->x là văn phạm?
a)
A. Tuyến tính phải
b)
B. Tuyến tính trái
c)
C. Không phải là tuyến tính phải và trái
d)
D. Tuyến tính phải và trái
19.
Câu 19 : Có hai lớp văn phạm tuyến tính là?
a)
A. Tuyến tính phải
b)
B. Tuyến tính trái
c)
C. Tuyến tính đệ quy
d)
D. Tuyến tính phải và trái
20.
Câu 20 : Văn phạm gồm các luật sinh: S->bA; S->aB; A->a B->b; A->aS B->bS; A->bAA B->aBB sinh ra được chuỗi nào?
a)
A. aaaabb
b)
B. aabbbb
c)
C. aabbab
d)
D. abbbba
21.
Câu 21 : Văn phạm gồm các luật sinh: S->bA; S->aB; A->a B->b; A->aS B->bS; A >bAA B->aBB sinh ra được bao nhiêu cây dẫn xuất?
a)
A. 1
b)
B. 2
c)
C. 3
d)
D. 4
22.
Câu 22 : Chuỗi nào không được sinh bởi văn phạm có luật sinh S->SaSbS; S>epsilon
a)
A. aabb
b)
B. abab
c)
C. aababb
d)
D. aaabbb
23.
Câu 23 : Văn phạm nào sau đây KHÔNG nhập nhằng:
a)
A. S→ aSb; S->bSa; S-> SS; S->a
b)
B. S → aSbS; S->bSaS; S->a; S->epsilon
c)
C. S→aS; S->aSb; S->b
d)
D. S→ aS; S->bS; S->epsilon
24.
Câu 24 : Văn phạm nào sau đây là văn phạm nhập nhằng:
a)
A. S → aSbS; S->aSb; S->epsilon
b)
B. S→aS; S->aSb; S->a
c)
C. S→ aSb; S->bSa; S->SS; S->a
d)
D. S→ aS; S->bS; S-> epsilon
25.
Câu 25 : Cho văn phạm G = {S ->aAAB; S->bC; A-> bB; A-> epsilon; B-> Aa; B->A; B->epsilon; C ->bA; C->B} Sau khi loại bỏ các sản xuất rỗng trong G, có bao nhiêu luật sinh có vế trái là S
a)
A. 8
b)
B. 7
c)
C. 6
d)
D. 8
26.
Câu 26 : Cho văn phạm gồm các luật sinh S -> aSbS; S->bSaS; S->a; S->epsilon. Văn phạm đã cho nhập nhằng trên chuỗi nào sau đây:
a)
A. aaba
b)
B. aab
c)
C. aaabb
d)
D. Tất cả đều sai
27.
Câu 27 : Luật sinh A -> XYZ có thể tạo thành mấy mục?
a)
A. 1
b)
B. 2
c)
C. 3
d)
D. 4
28.
Câu 28 : Luật sinh A -> BCDE có thể tạo thành mấy mục?
a)
A. 2
b)
B. 3
c)
C. 4
d)
D. 5
29.
Câu 29 : Luật sinh A -> BCDEF có thể tạo thành mấy mục?
a)
A. 3
b)
B. 4
c)
C. 5
d)
D. 6
30.
Câu 30 : Cho văn phạm G, với S là ký hiệu bắt đầu, phân tích xâu vào theo phương pháp phân tích bottom-up, trạng thái thành công là:
a)
A. ngăn xếp: dollar S, Đầu vào: dollar
b)
B. ngăn xếp: dollar, Đầu vào: dollar
c)
C. ngăn xếp: dollar S, Đầu vào: S dollar
d)
D. ngăn xếp: dollar S, Đầu vào: a dollar
31.
Câu 31 : Cho văn phạm G, với S là ký hiệu bắt đầu, phân tích xâu vào theo phương pháp phân tích LL(1), trạng thái thành công là:
a)
A. ngăn xếp: dollar S, Đầu vào: dollar
b)
B. ngăn xếp: dollar, Đầu vào: dollar
c)
C. ngăn xếp: dollar S, Đầu vào: S dollar
d)
D. ngăn xếp: dollar S, Đầu vào: a dollar
32.
Câu 32 : Cho văn phạm G gồm các luật sinh: E->EE*; E->EE+; E->a; E->b. Chuỗi nào sau đây được sinh ra bởi G
a)
A. a++b*a
b)
B. aab++a
c)
C. a+bb*
d)
D. ab*bb+
33.
Câu 33 : Cho văn phạm G gồm các luật sinh: E->EE*; E->EE+; E->a; E->b. Chuỗi nào sau đây được sinh ra bởi G
a)
A. a++b*
b)
B. ab++a*
c)
C. ab+ba*
d)
D. không có xâu nào đúng
34.
Câu 34 : Cho văn phạm G gồm các luật sinh: E->EE*; E->EE+; E->a; E->b. Dãy dẫn xuất của
a)
A. 7
b)
B. 8
c)
C. 9
d)
D. 10
35.
Câu 35 : Cho văn phạm G gồm các luật sinh: E->EE*; E->EE+; E->a; E->b. Dạng câu thứ 5 (tính dạng câu đầu tiên là E) trong dãy dẫn xuất trái nhất của chuỗi abb++a* trong G là:
a)
A. abE+E*+
b)
B. aEE*+
c)
C. aEE++E*
d)
D. abb+E*+
36.
Câu 36 : Cho văn phạm G = {S->aSb; S->bSa; S->SS; S->a; S->epsilon} Chuỗi nào sau đây
a)
A. abbaa
b)
B. aaba
c)
C. bbaaaa
d)
D. Tất cả đều đúng
37.
Câu 37 : Cho văn phạm G = {S->aSb; S->bSa; S->SS; S->a; S->epsilon} Chuỗi nào sau đây
a)
A. abbaab
b)
B. baabab
c)
C. abbaabb
d)
D. babbaaa
38.
Câu 38 : Cho văn phạm gồm 3 luật sinh: (1) S->aSbS; (2) S->aS; (3) S->c. Phân tích xâu vào“aacbc” bằng thuật toán Top-down. Từ gốc của cây, áp dụng suy dẫn (1) để triển khai, sau đó áp dụng suy dẫn (1) để triển khai bước sau thì cây suy dẫn tại thời điểm này có bao nhiêu nút?
a)
A. 6
b)
B. 7
c)
C. 8
d)
D. 9
39.
Câu 39 : Cho văn phạm gồm 3 luật sinh: (1) S->aSbS; (2) S->aS; (3) S->c. Phân tích xâu vào “aacbc” bằng thuật toán Top-down. Cây suy dẫn tại thời điểm bắt đầu có bao nhiêu nút?
a)
A. 1
b)
B. 2
c)
C. 3
d)
D. 4
40.
Câu 40 : Cho văn phạm gồm 3 luật sinh: (1) S->aSbS; (2) S->aS; (3) S->c. Phân tích xâu vào “aacbc” bằng thuật toán Top-down. Chọn lần lượt các sản xuất (1) (1) (1) (2) (3) (1) (2) (3) để phân tích thì tại thời điểm này của quá trình phân tích thì đầu đọc trên xâu vào đang trỏ tới kí tự thứ bao nhiêu?
a)
A. 3
b)
B. 4
c)
C. 5
d)
D. 6
Reset
