Bài tập lý thuyết chương 4
Các đặc tính của ngôn ngữ chính qui
Môn: Automata và Ngôn ngữ hình thức.

Bổ đề bơm
1. Chứng minh các ngôn ngữ dưới đây không phải là ngôn ngữ chính qui:
a) {0
n
1
n
| n ≥ 1}.
b) Tập các chuỗi mở, đóng ngoặc tròn cân bằng (tương ứng với một biểu thức số học
đúng khi loại bỏ đi các toán tử và toán hạng).
c) {0
n
10
n
| n ≥ 1}.
d) {0
n
1
m
2
n
| n, m ≥ 1}.
e) {0
n
1
m
| n ≤ m}.
f) {0

chuyển thành 0}.

Tính đóng của ngôn ngữ chính qui
1. Gọi L là ngôn ngữ trên bảng chữ cái Σ, a ∈ Σ. Khi đó, L/a là thương (quotient) của L và a.
L/a = {w ∈ Σ* | wa ∈ L}
Ví dụ: L = {a, aab, baa} thì L/a = {ε, ba}.
Chứng minh: Nếu L là RL thì L/a cũng là RL.
Hướng dẫn: Xét DFA của L và chú ý đến các trạng thái chấp nhận.
2. Gọi L là ngôn ngữ trên bảng chữ cái Σ, a ∈ Σ. Khi đó, a\L là:
a\L = {w ∈ Σ* | aw ∈ L}
Ví dụ: L = {a, aab, baa} thì a\L = {ε, ab}.
Chứng minh: Nếu L là RL thì a\L cũng là RL.
Hướng dẫn: Chú ý tính đóng của phép đảo và thương.
3. Hãy chỉ ra rằng ngôn ngữ chính qui L là đóng dưới các thao tác sau:
a) min(L) = {w | w ∈ L và không có tiền tố nào của w thuộc L}.
b) max(L) = {w | w ∈ L và không có chuỗi x ≠ ε khiến cho wx thuộc L}.
c) init(L) = {w | với một chuỗi x nào đó, wx thuộc L}.
Hướng dẫn: Bắt đầu từ DFA của L, tiến hành xây dựng DFA cho ngôn ngữ min(L), max(L),
init(L).
4. Nếu x = x
1
x
2
… x
n
và y = y
1
y
2
… y

A
C
C
D
B
*D
D
A
E
D
F
F
G
E
G
F
G
H
G
D
a) Xây dựng bảng xác định các cặp trạng thái phân biệt/tương đương.
b) Xây dựng DFA tương đương có số lượng trạng thái tối thiểu.
2. Yêu cầu tương tự như Bài 1 cho DFA có bảng truyền sau:

0
1
A
B
E
B