NỘI DUNG ÔN TẬP
MÔN LÝ THUYẾT AUTOMATA & NNHT
DÀNH CHO CÁC LỚP CHÍNH QUI
Lưu ý
Nội dung thi Chương 5 đến Chương 9
Hình thức thi Trắc nghiệm
Thời gian 120 phút
Số lượng câu dự kiến 50 câu
Lý thuyết dự kiến 10 đến 15 câu
Bài tập dự kiến 35 đến 40 câu
Cho phép xem tài liệu trong 2 tờ giấy A4

Lý thuyết
STT Nội dung dự kiến
1 Ngôn ngữ phi ngữ cảnh (NNPNC), VPPNC, NNPNC tuyến tính, VPPNC tuyến tính
2 Dẫn xuất (DX), DX trái nhất - phải nhất, cây DX
3 Tính nhập nhằng trong văn phạm và ngôn ngữ
4 Các phép biến đổi văn phạm và hai dạng chuẩn
5 Phân tích cú pháp (PTCP), độ phức tạp của các giải thuật PTCP
6 Phương pháp vét cạn, giải thuật PTCP theo CYK
7 Automata đẩy xuống không đơn định (NPDA) và đơn định DPDA
8 NNPNC đơn định, các văn phạm cho NNPNC đơn định, văn phạm LL(k)
9 Bổ đề bơm cho NNPNC và NNPNC tuyến tính
10 Tính đóng của họ NNPNC và các tính chất khả quyết định
11 Máy Turing
12 Mô hình phân cấp theo Chomsky Bài tập
STT Bài tập dự kiến
1 Cho ngôn ngữ L tìm văn phạm G

: n ≥ 0}
L
2
= {w ∈ {a, b}*: n
a
(w) = n
b
(w) + 1}
L
3
= {w ∈ {a, b}*: n
a
(w) = n
b
(w) + 1}
L
4
= {w ∈ {a, b}*: n
a
(w) = 2n
b
(w) + 1}
Đáp án:
G
1
: S → aaSb | abb
G
2
(1): S → aSbS | bSaS | λ
G

1
: S → aSbS | λ
G
2
: E → E+T | E-T | T
T → T*F | T/F | F
F → (E) | a | b
G
3
: S → aEbS | aEbScS | λ
E → d | e
Đáp án:
L
1
= {w ∈ {a, b}*: n
a
(w) = n
b
(w), n
a
(v) ≥ n
b
(v) với v là một tiếp đầu ngữ bất kỳ của w}
trong đó n
a
(w), n
b
(w) là các kí hiệu biểu thị số kí tự a và b có trong w.
Chú ý: Nếu thay a bằng dấu mở ngoặc “(“ (hoặc bằng từ khoá begin) và b bằng dấu đóng ngoặc “)”
(hoặc từ khoá end) thì ngôn ngữ trên biểu thị cấu trúc ngoặc lồng nhau, chẳng hạn ((()())(()))((())())

: E → E+T | E-T | T
T → T*F | T/F | F
F → (E) | a | b
Chú ý: Văn phạm G
1
và G
2
biểu diễn cùng một ngôn ngữ, văn phạm G
4
và G
5
biểu diễn cùng một
ngôn ngữ.
Đáp án:
G
1
nhập nhằng trên chuỗi abab.
G
2
nhập nhằng trên chuỗi abab.
G
4
nhập nhằng trên chuỗi a+b*c.
G
3
và G
5
không nhập nhằng.
Ở mỗi chuỗi được chỉ ra mà một văn phạm nhập nhằng, sinh
viên tự tìm hai cây dẫn xuất cho chuỗi trên văn phạm đó.

a
(v) ≥ n
b
(v) với v là tiếp đầu ngữ bất kỳ của w}
Đáp án:
Chú ý: q
0
là trạng thái khởi đầu, q
f
là trạng thái kết thúc.
M
1
:
δ(q
0
, λ, z) = (q
1
, c
k
z)
δ(q
1
, a, c) = (q
1
, λ)
δ(q
1
, a, z) = (q
1
, az)

3
, λ)
δ(q
3
, λ, z) = (q
f
, z)
δ(q
1
, b, z) = (q
3
, c
l - 1
z)
M
2
:
δ(q
0
, λ, z) = (q
1
, bz)
δ(q
1
, a, a) = (q
1
, aa)
δ(q
1
, b, a) = (q

δ(q
0
, a, z) = (q
0
, az)
δ(q
0
, 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)

, λ, z) = (q
f
, z)

5. Cho các ngôn ngữ L sau, tìm các dpda M tương ứng:
L
1
= {a
2n+k
b
n+l
: n ≥ 0, k, l ≥ 1}
L
2
= {w ∈ {a, b}*: n
a
(w) = n
b
(w) + 1}
L
3
= {w ∈ {a, b}*: n
a
(w) > n
b
(w)}
L
4
= {w ∈ {a, b}*: n
a

δ(q
1
, a, z) = (q
1
, az)
δ(q
1
, a, a) = (q
1
, aa)
δ(q
1
, b, a) = (q
t
, λ)
δ(q
t
, λ, a) = (q
2
, λ)
δ(q
2
, b, a) = (q
t
, λ)
δ(q
2
, b, z) = (q
3
, c

1
, aa)
δ(q
1
, b, a) = (q
1
, λ)
δ(q
1
, a, b) = (q
1
, λ)
δ(q
1
, b, b) = (q
1
, bb)
δ(q
1
, λ, z) = (q
f
, z)
δ(q
f
, a, z) = (q
1
, az)
δ(q
f
, b, z) = (q

δ(q
t
, λ, a) = (q
f
, a)
δ(q
0
, a, b) = (q
t
, λ)
δ(q
t
, λ, b) = (q
0
, b)
δ(q
0
, b, b) = (q
0
, bb)
M
4
:
δ(q
0f
, a, z) = (q
1
, az)
δ(q
1

(w) ≥ 1, n
a
(v) ≥ n
b
(v) với v là tiếp đầu ngữ bất kỳ của w}
L
3
= {w ∈ {a, b}*: n
a
(w) = n
b
(w) ≥ 0}
L
4
= {ww
R
∈ {a, b}*}
Đáp án:
M
1
:
δ(q
0
, a) = (q
1
, x, R)
δ(q
1
, a) = (q
1

, z, L)
δ(q
3
, b) = (q
3
, b, L)
δ(q
3
, y) = (q
3
, y, L)
δ(q
3
, a) = (q
3
, a, L)
δ(q
3
, x) = (q
0
, x, R)
δ(q
0
, y) = (q
4
, y, R)
δ(q
4
, y) = (q
4

1
, x) = (q
1
, x, L)
δ(q
1
, a) = (q
0
, x, R)
δ(q
0
, x) = (q
0
, x, R)
δ(q
0
, y) = (q
0
, y, R)
δ(q
0
, ) = (q
2
, , L)
δ(q
2
, y) = (q
2
, y, L)
δ(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
0
, y) = (q
0
, y, R)

δ(q
0
, b) = (q
3
, y, R)
δ(q
3

, x) = (q
0
, x, R)

δ(q
0
, ) = (q
f
, , R)
M
4
:
δ(q
0
, a) = (q
1
, x, R)
δ(q
1
, a) = (q
1
, a, R)
δ(q
1
, b) = (q
1
, b, R)
δ(q
1
, ) = (q

, b) = (q
4
, b, R)
δ(q
4
, a) = (q
4
, a, R)
δ(q
4
, ) = (q
5
, , L)
δ(q
5
, b) = (q
6
, y, L)
δ(q
6
, b) = (q
6
, b, L)
δ(q
6
, a) = (q
6
, a, L)
δ(q
6

: n > m}
{a
n
b
m
: n < m}
{a
n
b
m
: n ≠ m}
{a
n
b
2n
: n > m}
{a
n+2
b
2n
: n > m}
{a
2n
b
n+1
: n > m}
...
Nhóm các ngôn ngữ dạng {w ∈ {a, b}*: n
a
(w) = n

b
(w)}
{w ∈ {a, b}*: n
a
(w) + 1 = 2n
b
(w)}
{w ∈ {a, b, c}*: n
a
(w) = n
b
(w) + n
c
(w)}
...

Nhóm các ngôn ngữ dạng {a
n
b
j
b
k
}
{a
n
b
n
c
n
: n ≥ 0}

b
j
c
k
: n > jk}
{a
n
b
j
c
k
: n > j, n > k}
{a
n
b
j
c
k
: j > n, j > k}
{a
n
b
j
c
k
: n > j > k}
...
Nhóm các ngôn ngữ dạng {w ∈ {a, b, c}*: n
a
= n