200+ câu trắc nghiệm Chương trình dịch có đáp án - Phần 4
30 câu hỏi
Biểu thức chính quy nào có thể không tồn tại ký hiệu 0 hoặc 1
1 + 0(1+0)*
(0+1)(1+0)*
(1+0)
(00+0111+10)*
Chọn đáp án D
Biểu thức chính quy nào ký hiệu ZERO hoặc nhiều hơn x hoặc y
(x+y)
(x+y)*
(x* + y)
(xy)*
Chọn đáp án B
Tìm cặp biểu thức chính quy tương đương nhau
(0+1)* và (0*+1*)*
(0+1)* và (0+1*)*
(0+10)* và (0*+10)*
Tất cả các cặp đều tương đương
Chọn đáp án D
Biểu thức chính quy a/b ký hiệu bởi tập:
{a}
{epsilon,a,b}
{a,b}
{ab}
Chọn đáp án C
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
>
<
=
<=
Chọn đáp án C
Trong biểu thức chính quy, toán tử * có chức năng:
Nối
Chọn
Lặp
Cộng
Chọn đáp án C
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
1, 2 và 3
2, 3 và 4
1, 2 và 4
1, 3 và 4
Chọn đáp án C
Văn phạm gồm các luật sinh S ->abS; S->a được gọi là
Văn phạm tuyến tính phải
Văn phạm tuyến tính trái
Văn phạm tuyến tính trái và Phải
Không phải văn phạm trái và Phải
Chọn đáp án A
Văn phạm gồm các luật sinh A->Bx; A->x là văn phạm?
Tuyến tính phải
Tuyến tính trái
Không phải là tuyến tính phải và trái
Tuyến tính phải và trái
Chọn đáp án B
Có hai lớp văn phạm tuyến tính là?
Tuyến tính phải
Tuyến tính trái
Tuyến tính đệ quy
Tuyến tính phải và trái
Chọn đáp án D
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?
aaaabb
aabbbb
aabbab
abbbba
Chọn đáp án C
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?
1
2
3
4
Chọn đáp án D
Chuỗi nào không được sinh bởi văn phạm có luật sinh S- >SaSbS; S->epsilon
aabb
abab
aababb
aaabbb
Chọn đáp án B
Văn phạm nào sau đây KHÔNG nhập nhằng:
S→ aSb; S->bSa; S-> SS; S->a
S → aSbS; S->bSaS; S->a; S->epsilon
S→aS; S->aSb; S->b
S→ aS; S->bS; S->epsilon
Chọn đáp án B
Văn phạm nào sau đây là văn phạm nhập nhằng:
S → aSbS; S->aSb; S->epsilon
S→aS; S->aSb; S->a
S→ aSb; S->bSa; S->SS; S->a
S→ aS; S->bS; S-> epsilon
Chọn đáp án D
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
8
7
6
8
Chọn đáp án A
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:
aaba
aab
aaabb
Tất cả đều sai
Chọn đáp án D
Luật sinh A -> XYZ có thể tạo thành mấy mục?
1
2
3
4
Chọn đáp án D
Luật sinh A -> BCDE có thể tạo thành mấy mục?
2
3
4
5
Chọn đáp án D
Luật sinh A -> BCDEF có thể tạo thành mấy mục?
3
4
5
6
Chọn đáp án D
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à:
ngăn xếp: dollar S, Đầu vào: dollar
ngăn xếp: dollar, Đầu vào: dollar
ngăn xếp: dollar S, Đầu vào: S dollar
ngăn xếp: dollar S, Đầu vào: a dollar
Chọn đáp án A
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à:
ngăn xếp: dollar S, Đầu vào: dollar
ngăn xếp: dollar, Đầu vào: dollar
ngăn xếp: dollar S, Đầu vào: S dollar
ngăn xếp: dollar S, Đầu vào: a dollar
Chọn đáp án B
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++b*a
aab++a
a+bb*
ab*bb+
Chọn đáp án B
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++b*
ab++a*
ab+ba*
không có xâu nào đúng
Chọn đáp án D
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 chuỗi abb++a* trong G gồm bao nhiêu bước suy dẫn (bao nhiêu lần áp dụng luật sinh)
7
8
9
10
Chọn đáp án A
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à:
abE+E*+
aEE*+
aEE++E*
abb+E*+
Chọn đáp án C
Cho văn phạm G = {S->aSb; S->bSa; S->SS; S->a; S->epsilon} Chuỗi nào sau đây được sinh ra bởi G:
abbaa
aaba
bbaaaa
Tất cả đều đúng
Chọn đáp án C
Cho văn phạm G = {S->aSb; S->bSa; S->SS; S->a; S->epsilon} Chuỗi nào sau đây KHÔNG được sinh ra bởi G:
abbaab
baabab
abbaabb
babbaaa
Chọn đáp án C
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?
6
7
8
9
Chọn đáp án D
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?
1
2
3
4
Chọn đáp án A
