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

Câu 3
Cho văn phạm G = {S → aSb|bSa|SS|a|ε} ∑ = {a, b } ∆= {S} G sinh ra
ngôn ngữ nào sau đây: (w
R
là xâu ngược của xâu w)
A)
{ww
R
| w ∈ {a,b}*}
B)
{w ∈ {a,b}*| số kí tự của a >= số kí tự của b trong xâu w }
C)
{wxw
R
| x ∈ {a, b, ε}, w ∈ {a,b}*}
D)
{w ∈ {a,b}*| số kí tự của a = số kí tự của b trong xâu w }
Đáp án B
Câu 4
Cho văn phạm G = {S → aSb|bSa|SS|a|ε} ∑ = {a, b } ∆= {S} G sinh ra
ngôn ngữ nào sau đây: (w
R
là xâu ngược của xâu w)
A)
{ww
R
| w ∈ {a,b}*}
B)
{w ∈ {a,b}*| số kí tự của a >= số kí tự của b trong xâu w }
C)

{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

b
n
| n≥ 0, m≥ 0, m ≤ n ≤ 2m}
Đáp án B
Câu 6
Cho văn phạm G = {S → aSbS|bSaS|a|ε} ∑ = {a, b } ∆= {S} . Văn
phạm G nhập nhằng trên chuỗi nào sau đây:
A)
aaba
B)
aab
C)
aaabb
D)
tất cả đều sai
Đáp án D
Câu 7
Văn phạm nào sau đây KHÔNG nhập nhằng:
A)
S→ aSb|bSa|SS|a
B)
S → aSbS|bSaS|a|ε
C)
S→aS|aSb|b
D)
S→ aS|bS|ε
Đáp án D
Câu 8
Văn phạm nào sau đây là văn phạm nhập nhằng:
A)

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?

A) 8
B) 7
C) 6
D) 5
Đáp án
Câu 12
Cho văn phạm G = {E → aFFT| bC; F → bT| ε; T → Fa|F|ε; C → bF|
T} 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?
A) 8
B) 7
C) 6
D) 5
Đáp án
Câu 13
Cho văn phạm G = {E → aFFT| bC; F → bT| ε; T → Fa|F|ε; C → bF|
T} 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
Câu 14
Cho văn phạm G = {S → AB| BS; A → AA| AS|a|b; B → AB} Sau khi
loại bỏ đệ quy trái cho biến A đầu tiên và gọi A’ là biến mới được sinh
ra từ việc loại bỏ đệ quy trái này. Trong văn phạm biến B có bao nhiêu
luật sinh?
A) 1
B) 2

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 18
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à A?
A) 3
B) 4
C) 5
D) 6
Đáp án
Câu 19
Cho văn phạm G = {S → AB| BS; A → AA| AS|a|b; B → AB} Sau khi
loại bỏ đệ quy trái cho biến A đầu tiên và gọi A’ là biến mới được sinh
ra từ việc loại bỏ đệ quy trái này. Trong văn phạm biến S có bao nhiêu
luật sinh?
A) 2
B) 4
C) 6
D) 8
Đáp án
Câu 20
Cho văn phạm G = {S → AB| BS; A → AA| AS|a|b; B → AB} Sau khi
loại bỏ đệ quy trái cho biến A đầu tiên và gọi A’ là biến mới được sinh
ra từ việc loại bỏ đệ quy trái này. Trong văn phạm biến A’ có bao
nhiêu luật sinh?
A) 4
B) 8
C) 16
D)
tất cả đều sai
Đá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

Câu 24
Cho văn phạm G = { S → Aa|b; A→Ab | Sa|b} 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) 10
Đáp án
Câu 25
Cho văn phạm G = { S → Aa|b; A→Ab | Sa|b} 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ó bao nhiêu luật
sinh có vế trái là A?
A) 4
B) 5
C) 6
D) 7
Đáp án
Câu 26
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. Trong văn phạm có tất cả bao
nhiêu luật sinh?
A) 4
B) 6
C) 8
D) 10
Đáp án
Câu 27
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. 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 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