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)*
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)*
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
Biểu thức chính quy a/b ký hiệu bởi tập:
{a}
{epsilon,a,b}
{a,b}
{ab}
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
>
<
=
<=
Trong biểu thức chính quy, toán tử * có chức năng:
Nối
Chọn
Lặp
Cộng
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
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
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
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
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
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
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
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
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
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
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
Luật sinh A -> XYZ có thể tạo thành mấy mục?
1
2
3
4
Luật sinh A -> BCDE có thể tạo thành mấy mục?
2
3
4
5
Luật sinh A -> BCDEF có thể tạo thành mấy mục?
3
4
5
6
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
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
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+
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
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
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*+
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
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
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
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