Câu 1
Ngôn ngữ L = {a
n
b
m
| n> m} Văn phạm nào sau đây sinh ra ngôn ngữ L
A)
S → aSb|a
B)
S → aSb|aS|a
C)
S → aSb|aS| ε
D)
S → aSb| SS|a
Đáp án B
Câu 2
Ngôn ngữ L = {a
n
b
m
| n<> m} Văn phạm nào sau đây sinh ra ngôn ngữ
L
A)
S → A|B; A → aA| aX; B → Bb|Xb; X → aXb| ε
B)
S → A|B; A → aAb| a; B → aAb|b
C)
S → aS|Sb| ε
D)
Cả 3 văn phạm trên đều sinh ra
Đáp án A

{w ∈ {a,b}*| số kí tự của a = số kí tự của b trong xâu w }
D)
{w | w ∈ {a,b}* và w = w
R
}
Đáp án B
Câu 5
Cho văn phạm G = {S → aSa|bSb|a|b|ε} ∑ = {a, b } ∆= {S} Tìm ngôn
ngữ tương ứng với ngôn ngữ do G sinh ra:
A)
{a
2n
b
n
| n≥ 0}
B)
{a
n
b
n
|n ≥ m}
C)
{a
n
b
n
|n ≠ m}
D)
{ a
n

S → aSbS|aSb|ε
B)
S→aS|aSb|a
C)
S→ aSb|bSa|SS|a
D)
S→ aS|bS|ε
Đáp án B
Câu 9
Cho văn phạm G = {S → aAAB| bC; A → bB| ε; B → Aa|A|ε; C →
bA|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) 8
B) 7
C) 6
D) 8
Đáp án A
Câu 10
Cho văn phạm G = {S → aAAB| bC; A → bB| ε; B → Aa|A|ε; C →
bA|B} Sau khi loại bỏ các sản xuất rỗng trong G, văn phạm có bao
nhiêu luật sinh?
A) 18
B) 17
C) 16
D) 15
Đáp án XXX
Câu 11
Cho văn phạm G = {S → aAAB| bC; A → bB| ε; B → Aa|A|ε; C →
bA|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à C?

C) 4
D) 5
Đáp án
Câu 15
Cho văn phạm G = {S → AB; A → A0| B0|1; B → A1|0} Sau khi loại
bỏ đệ quy trái cho văn phạm G thu được văn phạm G’ tương đương.
Trong G’ có bao nhiêu luật sinh có vế trái là B?
A) 2
B) 4
C) 6
D) 8
Đáp án
Câu 16
Cho văn phạm G = {S → AB; A → A0| B0|1; B → A1|0} Sau khi loại
bỏ đệ quy trái cho văn phạm G thu được văn phạm G’ tương đương.
Trong G’ có tất cả bao nhiêu luật sinh?
A) 10
B) 13
C) 14
D) 16
Đáp án
Câu 17
Cho văn phạm G = {S → AB; A → A0| B0|1; B → A1|0} Sau khi loại
bỏ đệ quy trái cho văn phạm G thu được văn phạm G’ tương đương.
Trong G’ có tất cả bao nhiêu biến (kí hiệu không kết thúc)?
A) 5
B) 6
C) 7
D) 8
Đáp án

Câu 21
Cho văn phạm G = { S → Aa | b; A→Ac | Sd} Sau khi loại bỏ đệ quy
trái cho các biến trong văn phạm G . Trong văn phạm biến A’ có bao
nhiêu luật sinh?
A) 4
B) 5
C) 6
D)
tất cả đều sai
Đáp án
Câu 22
Cho văn phạm G = { S → Aa | b; A→Ac | Sd} Sau khi loại bỏ đệ quy
trái cho các biến trong văn phạm G. Trong văn phạm G có tất cả bao
nhiêu luật sinh?
A) 4
B) 6
C) 8
D)
tất cả đều sai
Đáp án
Câu 23
Cho văn phạm G = { S → Aa | b; A→Ac | Sd} Sau khi loại bỏ đệ quy
trái cho các biến trong văn phạm G. Trong văn phạm có tất cả bao
nhiêu luật sinh?
A) 4
B) 6
C) 8
D)
tất cả đều sai
Đáp án

sinh có vế trái là A?
A)
2
B) 3
C) 4
D) 5
Đáp án
Câu 28
Cho văn phạm G = { S → Aa|b; A→Ab | Sa} Sau khi loại bỏ đệ quy
trái cho các biến trong văn phạm G (gọi biến A’ là biến mới được sinh
ra từ việc loại bỏ đệ quy trái). Trong văn phạm có bao nhiêu luật sinh
có vế trái là A’ ?
A) 2
B) 3
C) 4
D) 5
Đáp án
Câu 29
Cho văn phạm G = { S → aaA|abA; A→bA | a} Sau khi thực hiện
phép thừa số hóa trái cho văn phạm thì trong văn phạm có tất cả bao
nhiêu luật sinh?
A) 2
B) 3
C) 4
D) 5
Đáp án
Câu 30
Cho văn phạm G = { S → aaA|abA; A→bA | a} Sau khi thực hiện
phép thừa số hóa trái cho văn phạm thì trong văn phạm có bao nhiêu