Trang 1
Đại học Quốc gia Tp. Hồ Chí Minh Đề Thi Học Kỳ 1/2003
Trường Đại Học Bách Khoa Môn Lý Thuyết Automat&NNHT - 501038
Khoa Công Nghệ Thông Tin Ngày 09/01/2004 - Thời gian 120 phút
---oOo---
ĐỀ 0001

Họ tên: .......................................................... MSSV:.......................
Lưu ý: 1. Sinh viên trả lời vào PHIẾU TRẢ LỜI TRẮC NGHIỆM. Sinh viên phải điền đầy đủ các thông tin vào
PHIẾU TRẢ LỜI TRẮC NGHIỆM chú ý MSMH: 501038.
2. Sinh viên phải điền họ tên và MSSV của mình vào đề thi. Sinh viên NỘP lại đề thi.
3. Đề gồm 4 trang, 50 câu.
4. Sinh viên chỉ được phép sử dụng tài liệu trong ba tờ giấy khổ A4.
5. Sinh viên chú ý một số kí hiệu và từ viết tắt. n
a
(w) là kí hiệu biểu diễn số kí hiệu a trong chuỗi w.
Dành cho câu 1 đến câu 3: Cho các ngôn ngữ sau (chú ý n, m nguyên không âm):
L
1
= {w ∈ {a, b, c}
*
: n
a
(w) = n
b
(w) + n
c
(w)}
L
2
= {a

S → aSb | aS | a
(C).
S → aSb | aS | λ
(D).
S → aSb | SS | a
(E). Tất cả đều sai.
3. Văn phạm nào sinh ra L
3

(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 | a | b

(D). Cả A, B, C đúng (E). Tất cả đều sai.
Dành cho câu 4 đến câu 8 7: Cho văn phạm G sau: E → EE* | EE+ | a | b. G có tập kí hiệu kết thúc là {a, b, *, +}
4. Chuỗ
i nào sau đây được sinh ra bởi G
(A). a+b*a (B). aab++a* (C). a+bb* (D).ab*bb+ (E). Tất cả đều sai.
5. Chuỗi nào sau đây được sinh ra bởi G
(A). a++b* (B). ab++a* (C). ab+ba* (D).b*ab+ (E). Tất cả đều sai.
6. Dãy dẫn xuất của chuỗi ab+ba*+ trong G
bao gồm bao nhiêu bước dẫn xuất (bao nhiêu lần áp dụng luật sinh)

(w)}
(C).
{w ∈ {a, b}
*
: n
a
(w) = n
b
(w) + 1}
(D).
{w∈{a, b}
*
: n
b
(w) ≤ n
a
(w) ≤ n
b
(w) + 2}
(E). Tất cả đều sai.
12. Cho văn phạm S → aSa | bSb | a | b | λ. Tìm ngôn ngữ tương ứng
(A).
{ww
R
: w ∈{a, b}*}
(B).
{w ∈{a, b}* : w = w
R
}
(C).

Trang 2
14. Văn phạm S → aSbS | bSaS | λ nhập nhằng trên chuỗi nào sau đây
(A). aabb (B). abba (C). abab (D). Cả A, B, C đúng. (E). Tất cả đều sai.
15. Văn phạm S → aSbS | bSaS | a | λ nhập nhằng trên chuỗi nào sau đây
(A). aaba (B). aab (C). aaabb (D). Cả A, B, C đúng. (E). Tất cả đều sai.
16.
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). Cả A, B, C đúng. (E). Tất cả đều sai.
Dành cho câu 17 đến câu 19: Cho văn phạm G sau S → aAAB | bC
A → bB | λ

B → Aa | A | λ
C → bA | B
17. Sau khi loại bỏ luật sinh - λ theo giải thuật đã học, biến S có bao nhiêu luật sinh (hay S có bao nhiêu vế phải)
(A). 8 (B). 9 (C). 7 (D). 6 (E). Tất cả đều sai.
18. Sau khi loại bỏ luật sinh - λ theo giải thuật đã học, văn phạm có bao nhiêu luật sinh
(A). 18 (B).
14 (C). 15 (D). 16 (E). 17
19. Sau khi loại bỏ luật sinh - λ và luật sinh đơn vị theo giải thuật đã học, biến C có bao nhiêu luật sinh
(A). 8 (B). 7 (C). 6 (D). 5 (E). 4
Dành cho câu 20 và 21: Cho văn phạm G sau S → aSbS | acS | bdS | e. Biến đổi G thành G’ tương đương có dạng chuẩn
Chomsky theo giải thuật đã học.
20. Trong G’ biến S có bao nhiêu luật sinh
(A). 4 (B). 5 (C). 6 (D). 7 (E). Tất cả đều sai.

22
)}
(B).
{A(
3
→
A
11
A
22
)}
(C).
{A(
4
→
B
11
A
22
)}
(D).
{B(
6
→
A
11
S
22
)}
(E). Tất cả đều sai.

(D).
{B(
6
→
A
11
S
23
)}
(E). Tất cả đều sai.
27. Tập V
24
có chứa phần tử nào sau đây
(A).
{S(
2
→
B
22
S
34
)}
(B).
{A(
4
→
B
22
A
34

24
)}
(B).
{S(
2
→
B
12
S
34
)}
(C).
{A(
3
→
A
11
A
24
)}
(D).
{B(
6
→
A
12
S
34
)}
(E). Tất cả đều sai.

b
m
: n > m > 0} L
4
= {a
n + m
b
n
c
m
: n, m > 0}
29. Npda nào sau đây chấp nhận đúng ngôn ngữ L
1

(A).
δ(q
0
, a, z) = (q
0
, az)
δ(q
0
, a, a) = (q
0
, aa)
δ(q
0
, b, a) = (q
1
, λ)

δ(q
1
, λ, z) = (q
f
, z)
(B).
δ(q
0
, a, z) = (q
0
, az)
δ(q
0
, a, a) = (q
0
, aa)
δ(q
0
, b, a) = (q
1
, λ)
δ(q
1
, b, a) = (q
1
, λ)
δ(q
1
, b, z) = (q
2

0
, az)
δ(q
0
, a, a) = (q
0
, aa)
δ(q
0
, b, a) = (q
1
, λ)
δ(q
1
, b, a) = (q
1
, λ)
δ(q
1
, b, z) = (q
2
, bz)
δ(q
2
, b, b) = (q
2
, bb)
δ(q
2
, c, b) = (q

, b, a) = (q
1
, λ)
δ(q
1
, b, z) = (q
2
, bz)
δ(q
0
, b, z) = (q
2
, bz)
δ(q
2
, b, b) = (q
2
, bb)
δ(q
2
, c, b) = (q
3
, λ)
δ(q
3
, c, b) = (q
3
, λ)
δ(q
3

, b, a) = (q
1
, λ)
δ(q
1
, b, z) = (q
2
, bz)
δ(q
0
, b, z) = (q
2
, bz)
δ(q
2
, b, b) = (q
2
, bb)
δ(q
0
, λ, a) = (q
f
, a)
δ(q
1
, λ, a) = (q
f
, a)
δ(q
2

1
, b, z) = (q
f
, bz)
δ(q
f
, b, b) = (q
f
, bb)
(C).
δ(q
0
, a, z) = (q
0
, az)
δ(q
0
, a, a) = (q
0
, aa)
δ(q
0
, b, a) = (q
1
, λ)
δ(q
1
, b, a) = (q
1
, λ)

0
, az)
δ(q
0
, a, a) = (q
0
, aa)
δ(q
0
, b, a) = (q
1
, λ)
δ(q
1
, b, a) = (q
1
, λ)
δ(q
1
, b, z) = (q
2
, bz)
δ(q
0
, b, z) = (q
2
, bz)
δ(q
2
, b, b) = (q

, b, z) = (q
0
, bz)
δ(q
0
, a, a) = (q
0
, aa)
δ(q
0
, b, a) = (q
0
, λ)
δ(q
0
, a, b) = (q
0
, λ)
δ(q
0
, b, b) = (q
0
, bb)
δ(q
0
, λ, z) = (q
f
, z)
δ(q
0

3
= L
1
∪ L
2

(D).
L
4
= {w ∈ {a, b}
*
: n
a
(w) ≥ n
b
(w)}
(E). Tất cả đều sai.
Dành cho câu 36: Xét ngôn ngữ L = {a
n
b
k
c
nk
: n, k ≥ 0}. Giả sử L phi ngữ cảnh, rõ ràng L vô hạn nên có thể áp dụng bổ
đề bơm. Gọi m là hằng số nguyên dương được chỉ ra trong bổ đề bơm, chuỗi w =
2
mmm
cba
∈ L thỏa | w | ≥ m.
Do đó có thể viết w = uvxyz với |vxy| ≤ m, vy không rỗng, và uv

= uv
2
xy
2
z có n
a
(w
2
) × n
b
(w
2
) > n
c
(w
2
). Do đó uv
2
xy
2
z ∉ L. Mâu thuẫn.
[4] Nếu vy chứa c, chọn i = 2, ta được chuỗi w
2
= uv
2
xy
2
z có n
a
(w

{a
n
b
m
c
n
: n ≤ m ≤ 2n}
(D). Cả A, B đúng. (E). Cả A, B, C đúng.
38. Ngôn ngữ nào sau đây KHÔNG phi ngữ cảnh
(A).
{ww: w ∈ {a, b}*}
(B).
{wcw: w ∈ {a, b}*}
(C).{a
n
b
m
c
m
a
n
} (D). Cả A, B đúng. (E). Cả A, B, C đúng.
39. Ngôn ngữ nào sau đây KHÔNG phi ngữ cảnh đơn định
(A).
{ww
R
: w∈ {a, b}*}
(B).
{w∈ {a, b}
*

1
, a) = (q
1
, a, R)
δ(q
1
, y) = (q
1
, y, R)
δ(q
1
, b) = (q
2
, y, L)
δ(q
2
, y) = (q
2
, y, L)
δ(q
2
, a) = (q
2
, a, L)
δ(q
2
, x) = (q
0
, x, R)
δ(q

bb (B). xaaq
1
yb (C). xaq
2
ayb (D).q
2
xaayb (E). xq
2
aayb
44. Máy Turing trên chấp nhận đúng ngôn ngữ nào sau đây
(A). {a
n
b
m
: n > m} (B). {a
n
b
m
: n < m} (C).
{a
n
b
m
: n ≠ m}
(D).
{w ∈ {a, b}*: n
a
(w) ≠ n
b
(w)}

(C).
L
1
∩
3
L
là PNC.
(D). Cả A, B, C đúng. (E). Chỉ có B, C đúng.
48. Một chuỗi w KHÔNG được chấp nhận bởi một máy Turing M nếu
(A). M dừng ở một trạng thái không kết thúc. (B). M không bao giờ dừng.
(C). M chưa duyệt hết chuỗi ngõ nhập ở trên băng. (D). Cả A, B đúng.
(E). Cả A, B, C đúng.
49. Từ việc nghiên cứu máy Turing chúng ta có thể phát biể
u
(A). Bất kỳ giải thuật nào cũng tồn tại máy Turing để thực hiện nó. (B). Số lượng máy Turing là vô hạn đếm được.
(C). Bất kỳ ngôn ngữ nào cũng tồn tại máy Turing chấp nhận nó. (D). Cả A, B, C đúng
(E). Chỉ có A, B đúng.
50. Từ các lớp ngôn ngữ đã nghiên cứu chúng ta có thể phát biểu (PNC: phi ngữ cảnh, CNC: cảm ngữ cảnh)
(A). Tồn tại m
ột ngôn ngữ CNC mà không PNC. (B). Lớp ngôn ngữ đệ qui và CNC là đồng nhất.
(C). Lớp ngôn ngữ khả liệt kê đệ qui bao trùm mọi ngôn ngữ. (D). Lớp ngôn ngữ PNC chỉ bao gồm hai lớp PNC
(E). Tất cả đều sai. tuyến tính và PNC đơn định.

Trang 5
ĐÁP ÁN
1 D 11 B 21 D 31 B 41 B
2 B 12 D 22 C 32 D 42 B
3 A 13 C 23 D 33 E 43 E
4 B 14 C 24 E 34 A 44 C
5 E 15 E 25 A 35 D 45 D