Trang 189
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Chương 6 Đơn giản hóa VPPNC
và các dạng chuẩn
6.1 Các phương pháp để biến đổi văn phạm
6.2 Hai dạng chuẩn quan trọng
6.3 Giải thuật thành viên cho văn phạm phi ngữ cảnh
Trang 190
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Các phương pháp để biến đổi văn phạm

Chuỗi trống đóng một vai trò khá đặc biệt trong nhiều định lý
và chứng minh, và thường cần có một sự chú ý đặc biệt cho nó.

Nếu L ∋λthì biểu diễn L = L
1
∪λvới L
1
= L - λ. Nếu
G
1
= (V
1
, T, S
1
, P
1
)
là văn phạm biểu diễn cho L
1
thì

| ... | y
n
là tập tất cả các luật sinh trong P mà có B ở vế trái.
Cho G
1
= (V, T, S, P
1
) là VP được xây dựng bằng cách xóa đi
A → x
1
Bx
2
từ P, và thêm vào nó
A → x
1
y
1
x
2
| x
1
y
2
x
2
| ... | x
1
y
n
x

Định lý 6.2 (Loại bỏ đệ qui trái)

Cho G = (V, T, S, P) là một VPPNC. Chia tập các luật sinh mà
vế trái của chúng là một biến đã cho nào đó(chẳng hạn là A),
thành hai tập con riêng biệt
A → Ax
1
| Ax
2
| ... | Ax
n
(6.2)
A → y
1
| y
2
| ... | y
m
(6.3)
với x
i
, y
i
∈ (V ∪ T)*, và A không là prefix của bất kỳ y
i
nào.
Xét G
1
= (V ∪ {Z}, T, S, P
1

n
)* ⇒ y
i
(x
1
+ x
2
+ ... + x
n
)*
Các dạng câu này cũng có thể được sinh ra trong G
1
bằng cách
chú ý Z có thể sinh ra các dạng câu có dạng
Z (x
1
+ x
2
+ ... + x
n
)(x
1
+ x
2
+ ... + x
n
)*
mà A → y
i
| y

Trang 195
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Ví dụ

Sử dụng Định lý 6.2 để loại bỏ các luật sinh đệ qui-trái khỏi VP
A → Aa | aBc | λ B → Bb | ba

Áp dụng định lý cho biến A ta được tập luật sinh mới như sau:
A → aBc | λ | aBcZ | Z B → Bb | ba
Z → a | aZ

Áp dụng định lý một lần nữa lần này cho biến B ta được tập
luật sinh kết quả cuối cùng như sau:
A → aBc | aBcZ | Z | λ B → ba | baY
Z → a | aZ Y → b | bY

Nhận xét

Việc loại bỏ các luật sinh đệ qui-trái đưa ra các biến mới. VP
kết quả có thể là "đơn giản" hơn đáng kể so với VP gốc nhưng
một cách tổng quát nó sẽ có nhiều biến và luật sinh hơn.
Trang 196
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Luật sinh vô dụng

Định nghĩa 6.1:

Cho G = (V, T, S, P) là một VPPNC. Một biến A ∈ V được gọi
là khả dụng nếu và chỉ nếu có ít nhất một chuỗi w ∈ L(G) sao
cho SxAyw,

) mà không chứa bất kỳ biến vô dụng nào.

Chứng minh

Loại bỏ các biến và luật sinh vô dụng loại 1
Tạo văn phạm G
1
= (V
1
, T, S, P
1
) với V
1
là tập biến không vô
dụng loại 1. Ta tìm V
1
như sau:
1. Khởi tạo V
1
= ∅.
2. Lặp lại bước sau cho đến khi không còn biến nào được thêm
vào V
1
.

Đối với mỗi A ∈ V mà có luật sinh A → x, x ∈ (V
1
∪T)*,
thì thêm A vào V
1

G = ({S, A, B, C}, {a, b}, S, P), với tập luật sinh P là:
S → aS | A | C B → aa
A → aC → aCb
A B
Trang 199
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Ví dụ

Loại bỏ các biến vô dụng loại 1 ta được
V
1
= {S, A, B} và tập luật sinh P
1
S → aS | A
A → a
B → aa

Loại bỏ các biến vô dụng loại 2 ta được
văn phạm kết quả
S → aS | A
A → a

Nhận xét

Nếu thay đổi thứ tự loại bỏ (loại bỏ các biến và luật sinh vô
dụng loại 2 trước) thì sẽ không loại bỏ được tất cả các biến và
luật sinh vô dụng chỉ bằng một lần như ví dụ sau cho thấy.
S → aS | A | C
A → a
B → aa

là có thể thì được gọi là khả trống (nullable).

Định lý 6.4

Cho G là một VPPNC bất kỳ mà L(G) không chứa λ, thì tồn tại
một văn phạm G
0
tương đương mà không có chứa luật sinh-λ.

Chứng minh:
Bước 1

Tìm tập V
N
tất cả các biến khả trống của G bằng các bước sau.
*
⇒
Trang 202
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Loại bỏ luật sinh-λ
1. Đối với mọi luật sinh A → λ, đưa A vào V
N
.
2. Lặp lại bước sau cho đến khi không còn biến nào được thêm
vào V
N
.

Đối với mọi luật sinh B → A
1

∈ V ∪ T, đặt luật sinh này vào cùng với các luật sinh
được sinh ra bằng cách thay thế các biến khả trống bằng λ trong
mọi tổ hợp có thể, ngoại trừ nếu tất cả các x
i
đều khả trống thì
không đặt luật sinh A → λ vào P
0
của G
0