TRƯỜNG ĐẠI HỌC CẦN THƠ Đề thi môn: TIN HỌC LÝ THUYẾT
KHOA CNTT & TRUYỀN THÔNG Lớp: TIN HỌC K.29
Lần 2 – Học kỳ 1 – Năm học 06 - 07
Thời gian làm bài: 120 phút
NỘI DUNG ĐỀ
Câu 1 (1.0 điểm): Áp dụng bổ đề bơm, bạn hãy chứng minh ngôn ngữ sau đây không là ngôn ngữ
chính quy: L = {a
i
b
j
c
j
d
i
| i, j ≥ 1}
Câu 2 (2.0 điểm): Bạn hãy tìm một DFA tương đương với NFA sau:
Câu 3 (1.5 điểm): Bạn hãy vẽ một automata hữu hạn chấp nhận cho ngôn ngữ được ký hiệu bởi
biểu thức chính quy sau: ( (a + ab) b* a )*
Câu 4 (1.0 điểm): Bạn hãy chuyển văn phạm sau đây về dạng chuẩn Chomsky (cho biết rằng văn
phạm không có ký hiệu vô ích):
S → 0SA | 1SB | 01
A → 0A | 0
B → 1B | 1
Câu 5 (1.0 điểm): Bạn hãy chuyển văn phạm sau đây về dạng chuẩn Greibach:
S → SA | 0
A → AS | 1
Câu 6 (1.5 điểm): Bạn hãy thiết kế một PDA tương đương với văn phạm phi ngữ cảnh có tập luật
sinh như sau:
S → 0SA | 1SB | 0 | 1
A → 0A | 0
B → 1B | 1

d
i
| i, j ≥ 1}
Giả sử L là ngôn ngữ chính quy. Khi đó sẽ tồn tại một DFA M chấp nhận cho ngôn ngữ L.
Gọi n là số trạng thái của DFA M đó.
Xét chuỗi z = a
n
b
1
c
1
d
n
. Ta có độ dài của chuỗi z là: |z| = 2n + 2 > n . Theo bổ đề bơm, ta có
thể đặt z = uvw , trong đó u, v, w là các chuỗi con của z với điều kiện như sau:
|uv| ≤ n, |v| ≥ 1 và với mọi i ≥ 0 ta có uv
i
w ϵ L
Do uv là chuỗi tiền tố của chuỗi z = a
n
b
1
c
1
d
n
và uv có độ dài chuỗi không lớn hơn n nên uv
chỉ chứa ký tự a. Vậy v cũng chỉ chứa ký hiệu a (và có ít nhất một ký hiệu a).
Xét chuỗi uv
2

[q
2
]
[q
3
]
[q
1
, q
2
]
[q
2
, q
3
]
[q
1
,q
2
,q
3
]
a
b
a
b
b
a
b

S → 0SA | 1SB | 01
A → 0A | 0
B → 1B | 1
Bước 1: bỏ qua (vì đề bài đã cho biết văn phạm không có ký hiệu vô ích, và nhìn vào văn
phạm ta thấy không có luật sinh ε hay luật sinh đơn vị).
Bước 2: thay thế các ký hiệu kết thúc ở các luật sinh có độ dài vế phải lớn hơn 1 bằng các
biến tương ứng.
S → C
0
SA | C
1
SB | C
0
C
1
A → C
0
A | 0
B → C
1
B | 1
C
0
→ 0
C
1
→ 1
Bước 3: thay thế luật sinh có độ dài vế phải lớn hơn 2 bằng các luật sinh có độ dài vế phải
bằng 2.
S → C

S → SA | 0
A → AS | 1
Bước 1: văn phạm đã ở dạng chuẩn Chomsky.
Bước 2: thay biến S bằng biến A
1
, biến A bằng biến A
2
. Ta có tập luật sinh:
A
1
→ A
1
A
2
| 0
A
2
→ A
2
A
1
| 1
Bước 3: khử tính đệ quy trái ở tập luật sinh trên:
A
1
→ 0 | 0B
1
A
2
→ 1 | 1B

1
A
2
→ 1 | 1B
2
B
1
→ 1 | 1B
2
| 1B
1
| 1B
2
B
1
B
2
→ 0 | 0B
1
| 0B
2
| 0B
1
B
2
Tập luật sinh trên đã thỏa dạng chuẩn Greibach.
Câu 6 (1.5 điểm): Bạn hãy thiết kế một PDA tương đương với văn phạm phi ngữ cảnh có tập luật
sinh như sau:
S → 0SA | 1SB | 0 | 1
A → 0A | 0

5
q
6
q
2
q
3
q
4
(0, 1, R)
(0, 0, R)
(B, 2, R) (B, 2, L)
(0, 0, L)
(2, 2, L)
(1, 1, R)
(2, 2, R)
(2, 2, R)
(2, 2, R)
(B, B, L)
(2, 0, L)
(1, 0, L)
(B, B, Ø)