Xem mẫu
- Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống
Chƣơng 3. VĂN PHẠM PHI NGỮ CẢNH
VÀ AUTOMAT ĐẨY XUỐNG
(Contexet free Grammar - CFG and push down Automata - PDA)
Mục tiêu:
Giúp sinh viên có khả năng:
- Hiểu đƣợc khái niệm và xác định đƣợc các thành phần của một CFG.
- Nhận dạng đƣợc lớp ngôn ngữ phi ngữ cảnh (CFL) do văn phạm CFG sinh
ra và tính chất của CFL.
- Xây dựng đƣợc các thành phần của CFG đặc tả một lớp CFL.
- Hiểu và xây dựng đƣợc dẫn xuất và cây dẫn xuất.
- Rút gọn và chuẩn hoá đƣợc CFG.
- Hiểu đƣợc khái niệm và xác định đƣợc các thành phần của một PDA
- Xây dựng đƣợc các thành phần của PDA đoán nhận ngôn ngữ sinh bởi
CFG và xây dựng đƣợc CFG sinh ra ngôn ngữ đƣợc đoán nhận bởi PDA.
Nội dung chính:
- Văn phạm phi ngữ cảnh: định nghĩa, dẫn xuất và ngôn ngữ và cây dẫn xuất.
- Rút gọn văn phạm phi ngữ cảnh.
- Chuẩn hoá văn phạm phi ngữ cảnh.
- Tính chất của CFL.
- Automat đẩy xuống: định nghĩa, ngôn ngữ đoán nhận bởi PDA.
- Quan hệ của PDA và CFG.
3.1. Văn phạm phi ngữ cảnh (CFG: Context Free Grammar)
Xuất xứ của văn phạm phi ngữ cảnh là sự mô tả thông qua các ngôn ngữ tự
nhiên. Ta có thể viết các quy tắc cú pháp để diễn tả câu “An là sinh viên giỏi“ nhƣ
sau:
< câu đơn > → < chủ ngữ > < vị ngữ >
< chủ ngữ > → < danh từ >
< vị ngữ > → < động từ > < bổ ngữ >
< bổ ngữ > → < danh từ > < tính từ >
107 Phạm Hùng Phú
- Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống
< danh từ > → An
< danh từ > → sinh viên
< động từ > → là
< tính từ > → giỏi
Các từ trong cặp dấu < > nhƣ , , , ... là các
phạm trù cú pháp, cho ta vai trò của các bộ phận hợp thành câu. Ta thấy một câu
đƣợ sinh ra qua các bƣớc triển khai dần dần theo các quy tắc cú pháp. Đây cũng
chính là dạng của các luật sinh trong văn phạm phi ngữ cảnh. Nhƣ vậy, văn phạm
phi ngữ cảnh cũng có thể chọn làm mô hình cho các văn phạm của các ngôn ngữ tự
nhiên.
Tuy nhiên, trong khoa học máy tính, với nhu cầu biểu diễn các ngôn ngữ lập
trình, văn phạm phi ngữ cảnh CFG còn đƣợc thiết kế thành một dạng tƣơng đƣơng
gọi là văn phạm BNF (Backus - Naur Form). Đây cũng là văn phạm CFG với
những thay đổi nhỏ về dạng thức và một số ký hiệu viết tắt mà các nhà khoa học
máy tính thƣờng ứng dụng trong việc diễn tả cú pháp của các ngôn ngữ lập trình cấp
cao (nhƣ ALGOL, PASCAL, ... ). Trong dạng thức của văn phạm BNF, ký hiệu::=
đƣợc dùng thay cho ký hiệu →. Chẳng hạn, để định nghĩa một biểu thức số học
(expression) bao gồm các danh biểu (identifier) tham gia vào các phép toán +, *
hoặc biểu thức con lồng trong dấu ngoặc đơn , ta viết:
::= +
::= *
::= ( )
::=
Việc nghiên cứu các văn phạm phi ngữ cảnh đã tạo nên một cơ sở lý luận
vững chắc cho việc biểu diễn ngôn ngữ lập trình, việc tìm kiếm các giải thuật phân
tích cú pháp vận dụng trong chƣơng trình dịch và cho nhiều ứng dụng khác về xử lý
xâu. Chẳng hạn, nó rất hữu ích trong việc mô tả các biểu thức số học với nhiều dấu
ngoặc lồng nhau hoặc cấu trúc khối trong ngôn ngữ lập trình có cấu trúc mà biểu
thức chính quy không thể đặc tả đƣợc.
Văn phạm phi ngữ cảnh là một tập hợp hữu hạn các biến (còn gọi là các ký
hiệu chưa kết thúc), mỗi biến biểu diễn một ngôn ngữ. Ngôn ngữ đƣợc biểu diễn bởi
108 Phạm Hùng Phú
- Câu hỏi và bài tập chƣơng 3
các biến đƣợc mô tả một cách đệ quy theo thuật ngữ của một khái niệm khác gọi là
ký hiệu kết thúc. Quy tắc quan hệ giữa các biến và các ký hiệu kết thúc đƣợc gọi là
luật sinh. Mỗi luật sinh có dạng một biến ở vế trái sinh ra một xâu có thể gồm các
biến lẫn các ký hiệu kết thúc trong văn phạm.
3.1.1. Định nghĩa
Văn phạm phi ngữ cảnh (CFG) là một hệ thống gồm bốn thành phần, ký hiệu
là G = (N, T, P, S); trong đó:
- N là tập hữu hạn các ký tự không kết thúc (hay các biến) ;
- T là tập hữu hạn các ký tự kết thúc; N T = ∅ ;
- P là tập hữu hạn các luật sinh mà mỗi luật sinh có dạng A → α với A N và
α (N T)*;
- S là một ký tự không kết thúc đặc biệt gọi là ký tự bắt đầu văn phạm.
Ví dụ: Văn phạm phi ngữ cảnh G = (N, T, P, S); trong đó:
N = {S, A, B};
T = {a, b};
S = S;
P gồm các luật sinh sau:
S → AB;
A → aA;
A → a;
B → bB;
B → b.
Quy ƣớc ký hiệu:
- Các chữ in hoa A, B, C, D, E, ... đầu bảng chữ cái La tinh và S ký hiệu cho
các ký tự không kết thúc (S thƣờng đƣợc dùng làm ký tự bắt đầu ).
- Các chữ nhỏ a, b, c, d, e, ..., các chữ số và một số ký tự khác ký hiệu cho
các ký tự kết thúc.
- Các chữ in hoa X, Y, Z ký hiệu cho các ký tự có thể kết thúc hoặc không
kết thúc.
Phạm Hùng Phú 109
- Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống
- Các chữ Hi-Lạp α, β, γ, ... ký hiệu cho các xâu gồm các ký tự kết thúc và
không kết thúc.
Ta sẽ biểu diễn văn phạm một cách tóm tắt bằng cách chỉ liệt kê các luật sinh
của nó. Nếu A → α ; A → α ; ... ; A → α là các luật sinh của biến A trong văn
1 2 k
phạm nào đó, ta sẽ ghi ngắn gọn là A → α | α | ... | α
1 2 k
Ví dụ: Văn phạm cho trong ví dụ trên có thể viết gọn là:
S → AB;
A → aA | a;
B → bB | b‟
3.1.2. Dẫn xuất và ngôn ngữ
1) Dẫn xuất
Cho văn phạm CFG: G = (N, T, P, S), giả sử luật sinh A → β P và xâu
αAγ (N T)* với α , β, γ (N T)* . Nếu thay ký tự không kết thúc A trong xâu
αAγ bằng xâu β để thu đƣợc xâu αβγ hay còn nói áp dụng luật sinh A → β vào xâu
αAγ để thu đƣợc xâu αβγ; khi đó, ta nói rằng xâu αAγ dẫn xuất trực tiếp ra xâu αβγ
hay xâu αβγ đƣợc dẫn xuất trực tiếp từ xâu αAγ trong văn phạm G và đƣợc ký hiệu
là αAγ αβγ.
G
Giả sử α , α , ..., α là các xâu thuộc (N T)* với m ≥ 1 và
1 2 m
α α ; α α ; …; α α
1 G 2 2 G 3 m -1 G m
thì ta ký hiệu là α * α và nói là α dẫn xuất (không, một hoặc nhiều bƣớc) ra α
1 G m 1 m
hay α đƣợc dẫn xuất từ α trong văn phạm G.
m 1
Nếu α dẫn xuất ra α bằng i bƣớc dẫn xuất thì ta ký hiệu là α i α .
1 m 1 G m
Nếu α dẫn xuất ra α bằng một hoặc nhiều bƣớc dẫn xuất thì ta ký hiệu là
1 m
α + α .
1 G m
Chú ý rằng α * α với mọi xâu α. và nếu α * ; * thì α * với
G G G G
mọi xâu α, , .
110 Phạm Hùng Phú
- Câu hỏi và bài tập chƣơng 3
Thông thƣờng, nếu không có nhầm lẫn, ta sẽ dùng các ký hiệu , *, +
i thay cho ký hiệu tƣơng ứng , * , + , i .
G G G G
2) Ngôn ngữ sinh bởi văn phạm phi ngữ cảnh
Cho văn phạm CFG: G = (N, T, P, S), Ngôn ngữ sinh bởi văn phạm phi ngữ
*
cảnh G là L(G) = {w | w T và S * w} và đƣợc gọi là ngôn ngữ phi ngữ cảnh.
G
Nghĩa là, một xâu thuộc L(G) nếu:
1. Xâu gồm toàn ký tự kết thúc.
2. Xâu đƣợc dẫn xuất ra từ ký tự bắt đầu S.
Xâu α gồm các ký tự kết thúc và các ký tự không kết thúc, đƣợc gọi là một
dạng câu sinh từ văn phạm G nếu S * α .
G
Hai văn phạm phi ngữ cảnh G , G đƣợc gọi là tƣơng đƣơng nếu L(G ) = L(G ).
1 2 1 2
Ví dụ: 1. Xét văn phạm CLG: G = (N, T, P, S), trong đó:
N = {S}; T = {a, b}; P = {S → aSb, S → ab}.
Bằng cách áp dụng luật sinh thứ nhất n-1 lần và luật sinh thứ hai 1 lần, ta có:
3 3 n-1 n-1 n n
S aSb aaSbb a Sb ... a b a b
n n n n
Vậy, L(G) chứa các xâu có dạng a b với n ≥ 1; hay L(G) = {a b | n ≥ 1}.
2. Xét văn phạm CLG: G‟ = (N‟, T, P‟, S), trong đó:
N‟ = {S, A}; T = {a, b}; P‟ = {S → aAb; A → aAb; A → }.
Bằng cách áp dụng luật sinh thứ nhất 1 lần, luật sinh thứ hai n -1 lần và luật
sinh thứ ba 1 lần , ta có:
3 3 n-1 n-1 n n n n
S aAb aaAbb a Ab ... a Ab a Ab a b
n n n n
Vậy, L(G‟) chứa các xâu có dạng a b với n ≥ 1; hay L(G‟) = {a b | n ≥ 1}.
Và ta có L(G) =L(G‟) nên hai văn phạm phi ngữ cảnh trên là tƣơng đƣơng.
3.1.3. Cây dẫn xuất
Để hình dung một cách trực quan việc sinh ra các xâu trong văn phạm phi
ngữ cảnh, ngƣời ta thƣờng diễn tả một dãy dẫn xuất qua hình ảnh một cây. Một
cách hình thức, ta định nghĩa cây dẫn xuất nhƣ sau:
1) Định nghĩa
Phạm Hùng Phú 111
- Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống
Cho văn phạm CFG: G = (N, T, P, S). Cây dẫn xuất (hay cây phân tích cú
pháp) của G đƣợc định nghĩa nhƣ sau:
1. Mỗi nút có một nhãn, là một ký tự (N T{ε}).
2. Nút gốc có nhãn là ký tự bắt đầu S.
3. Nếu nút trong (trung gian) có nhãn A thì A N.
4. Nếu nút n có nhãn A và các nút n , n , ..., n là con của n theo thứ tự từ trái
1 2 k
sang phải có nhãn lần lƣợt là X , X , ..., X thì A → X X ... X là một luật sinh
1 2 k 1 2 k
trong tập luật sinh P.
5. Nếu nút n có nhãn là từ rỗng ε thì n phải là nút lá và là nút con duy nhất
của nút cha của nó.
2) Ví dụ:
a) Cho văn phạm G = ({S, A}, {a, b}, P, S), trong đó P gồm:
S → aAS | a;
A → SbA | SS | ba.
Một cây dẫn xuất từ văn phạm có dạng nhƣ sau:
S
S
a
A
a
S b A
a b a
Hình 3.1. Cây dẫn xuất từ văn phạm
Ta thấy, nút 1 có nhãn S và các con của nó lần lƣợt là a, A, S (chú ý S →
aAS là một luật sinh). Tƣơng tự, nút 3 có nhãn A và các con của nó là S, b, A (từ
luật sinh A → SbA). Nút 4, 5 có cùng nhãn S và có nút con nhãn a (luật sinh S →
a). Cuối cùng nút 7 có nhãn A và có các nút con b, a (luật sinh A → ba).
Trên cây dẫn xuất, nếu ta đọc các lá theo thứ tự từ “trái sang phải“ thì ta có
một dạng câu trong G. Ta gọi xâu này là xâu sinh bởi cây dẫn xuất.
112 Phạm Hùng Phú
- Câu hỏi và bài tập chƣơng 3
Một cây con (subtree) của cây dẫn xuất có nút gốc nhãn là A còn đƣợc gọi là
A-cây con (hoặc A-cây). Cây con cũng giống nhƣ cây dẫn xuất, chỉ khác là nhãn
của nút gốc không nhất thiết phải là ký tự bắt đầu S.
b) Xét văn phạm và cây dẫn xuất trên. Đọc các lá theo thứ tự từ trái sang phải
ta có xâu aabbaa. Trong trƣờng hợp này, tất cả các lá đều là ký tự kết thúc. Tuy
nhiên, nói chung cũng không bắt buộc nhƣ thế; lá có thể có nhãn là ε hoặc biến.
Ta thấy dẫn xuất S * aabbaa bằng dãy dẫn xuất: S aAS aSbAS aabAS
aabbaS aabbaa.
A-cây (nút 3) nhãn của nút gốc là A tạo ra xâu con abba theo dãy dẫn xuất:
A SbA abA abba.
3.1.4. Quan hệ giữa dẫn xuất và cây dẫn xuất
1) Định lý
Cho G = (N, T, P, S) là một văn phạm phi ngữ cảnh.
S * α tồn tại cây dẫn xuất trong văn phạm G sinh ra α từ S.
Chứng minh:
Ta chứng minh rằng với biến A bất kỳ, A * α có một A-cây sinh ra α.
- Đảo: Giả sử α đƣợc sinh bởi A-cây, ta chứng minh quy nạp theo số nút trong
của cây dẫn xuất rằng A * α.
Nếu A có số nút trong là 1 thì cây phải có dạng nhƣ hình sau:
Khi đó X X ... X là xâu α và A → α là một luật sinh trong P theo định nghĩa cây
1 2 n
dẫn xuất. S
X1 X2 ... Xn
Hình 3.2(a). A-cây với một nút trong
Giả sử kết quả đúng tới số nút trong là k -1 ( k > 1)
Ta chứng minh kết quả cũng đúng với số nút trong là k.
Phạm Hùng Phú 113
- Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống
Xét α đƣợc sinh ra bởi A-cây có số nút trong là k. Rõ ràng các nút con của
nút gốc không phải tất cả đều là lá, ta gọi chúng từ trái sang phải là X , X , ..., X thì
1 2 n
chắc chắn rằng A → X X ... X là một luật sinh. Xét nút X bất kỳ:
1 2 n i
+ Nếu X không là nút lá thì X phải là một biến và X - cây con sẽ sinh ra một
i i i
xâu α nào đó.
i
+ Nếu X là nút lá, ta đặt α = X . Dễ thấy rằng nếu j < i thì các α ở bên trái α , do
i i i j j
vậy xâu đọc từ lá vẫn có dạng α = α α ... α . Mỗi X - cây con phải có ít nút trong hơn
1 2 n i
cây ban đầu, vì thế theo giả thiết quy nạp, với mỗi đỉnh i không phải là lá thì X * α .
i i
Vậy A X X ... X * α X ... X * α α X ... X * ... * α α ... α = α
1 2 n 1 2 n 1 2 3 n 1 2 n
Hay ta có A * α . Chú ý rằng đây chỉ là một trong nhiều cách dẫn xuất ra α.
- Thuận: giả sử A * α , ta cần chỉ ra một A - cây sinh ra α.
Nếu A * α bằng một bƣớc dẫn xuất thì A → α là một luật sinh trong P và
có cây dẫn xuất sinh ra α nhƣ trong hình trên.
Giả sử kết quả đúng tới k-1 bƣớc dẫn xuất
Xét A * α bằng k bƣớc dẫn xuất, gọi bƣớc đầu tiên là A → X X ... X .
1 2 n
Rõ ràng, một ký tự trong α phải đƣợc dẫn ra từ một biến X nào đó. Vì vậy, ta
i
có thể viết α = α α ... α , trong đó mỗi 1 ≤ i ≤ n thoả mãn:
1 2 n
+ α = X nếu X là ký tự kết thúc.
i i i
+ X * α nếu X là một biến (ký tự không kết thúc).
i i i
Nếu X là biến thì dẫn xuất của α từ X phải có ít hơn k bƣớc. Vì vậy, theo giả
i i i
thiết quy nạp ta có X - cây sinh ra α , đặt cây này là T
i i i
Bây giờ ta dựng A - cây có n lá X X ... X . Mỗi X không là ký tự kết thúc ta
1 2 n i
thay bằng cây T tƣơng ứng. Cuối cùng, ta có cây dẫn xuất sinh ra có dạng nhƣ sau:
i
114 Phạm Hùng Phú
- Câu hỏi và bài tập chƣơng 3
S
X3 ... Xn-1
X1 X2 Xn
T2 T3 Tn
Hình 3.2(b). A-cây
2) Ví dụ: Xét dãy dẫn xuất S * aabbaa của văn phạm trên
Bƣớc đầu tiên trong dẫn xuất đó là S aAS. Theo dõi các bƣớc suy dẫn sau
đó, ta thấy biến A đƣợc thay bởi SbA, rồi trở thành abA và cuối cùng thành abba,
đó chính là kết quả của cây T (A - cây). Còn biến S thì đƣợc thay bởi a và đó là kết
2
quả của cây T (S -cây). Ghép nối lại, ta đƣợc cây dẫn xuất mà kết quả là xâu
3
aabbaa.
S S S
a A S S b A
a
T2 T3
b a
Cây T2 Cây T3
Hình 3.3. Ghép nối các cây dẫn xuất
3.1.5. Dẫn xuất trái nhất, dẫn xuất phải nhất
1) Định nghĩa
Nếu tại mỗi bƣớc dẫn xuất, luật sinh đƣợc áp dụng vào biến bên trái nhất thì
ta gọi đó là dẫn xuất trái nhất (leftmost - lm) hay dẫn xuất trái.
Tƣơng tự, nếu biến bên phải nhất đƣợc thay thế ở mỗi bƣớc dẫn xuất thì đó
là dẫn xuất phải nhất (rightmost - rm) hay dẫn xuất phải.
Nếu xâu w L(G) với CFG G thì w sẽ có ít nhất một cây dẫn xuất ra nó và
tƣơng ứng với các cây này, w chỉ có duy nhất một dẫn xuất trái nhất và duy nhất
Phạm Hùng Phú 115
- Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống
một dẫn xuất phải nhất. Dĩ nhiên, w có thể có nhiều dẫn xuất trái (phải) nhất vì nó
có thể có nhiều cây dẫn xuất.
2) Ví dụ: Xét cây dẫn xuất ở hình 3.1
- Dẫn xuất trái nhất của cây:
S aAS aSbAS aabAS aabbaS aabbaa.
-Dẫn xuất phải nhất tƣơng ứng là:
S aAS aAa aSbAa aSbbaa aabbaa.
3.1.6. Văn phạm nhập nhằng (mơ hồ)
1) Định nghĩa
Một văn phạm phi ngữ cảnh G có nhiều hơn một cây dẫn xuất trái nhất hay
phải nhất cho cùng một xâu w thì G đƣợc gọi là văn phạm nhập nhằng (ambiguity).
Dĩ nhiên, cũng có thể nói rằng văn phạm G là nhập nhằng nếu có một xâu w
đƣợc dẫn ra từ ký tự bắt đầu S với hai dẫn xuất trái nhất hoặc hai dẫn xuất phải
nhất.
2) Ví dụ
Xét văn phạm phi ngữ cảnh G với các luật sinh nhƣ sau:
E→E+E|E*E|(E)|a
Văn phạm này sinh ra các xâu biểu thức số học với 2 phép toán + và * .
Xét xâu a + a * a , xâu này có hai dẫn xuất trái nhất là:
1. E E + E a + E a + E * E a + a * E a + a * a
2. E E * E E + E *E a + E * E a + a * E a + a * a
Và có hai cây dẫn xuất trái nhất tƣơng ứng là:
E
E
E
+ E E
E * E
E E
a
* E +
a a a
a
a
a) b)
Hình 3.4. Hai cây dẫn xuất trái nhất cho cùng xâu
116 Phạm Hùng Phú
- Câu hỏi và bài tập chƣơng 3
Vậy văn phạm trên là văn phạm nhập nhằng.
Điều này có nghĩa là biểu thức a + a * a có thể hiểu theo hai cách khác nhau:
thực hiện phép cộng trƣớc hay phép nhân trƣớc ? Để khắc phục sự nhập nhằng này,
ta có thể:
- Hoặc quy định rằng các phép cộng và nhân luôn luôn đƣợc thực hiện theo
thứ tự từ trái sang phải (trừ khi gặp ngoặc đơn). Ta viết văn phạm G không mơ hồ
1
tƣơng đƣơng nhƣ sau:
E→E+T|E*T|T;
T→(E)|a.
- Hoặc quy định rằng khi không có dấu ngoặc đơn ngăn cách thì phép nhân
luôn luôn đƣợc ƣu tiên hơn phép cộng. Ta viết văn phạm G không mơ hồ tƣơng
2
đƣơng nhƣ sau:
E → E + T | T;
T → T * F | F;
F → ( E ) | a.
3.2. Rút gọn văn phạm phi ngữ cảnh
Thông thƣờng, một văn phạm phi ngữ cảnh có thể còn chứa đựng một vài
yếu tố thừa. Chẳng hạn nhƣ theo các đặc tính trên, có những ký tự không thực sự
tham gia vào quá trình dẫn xuất ra xâu, hoặc sẽ có những luật sinh dạng A → B
làm kéo dài dãy dẫn xuất một cách không cần thiết. Vì vậy, việc rút gọn văn phạm
phi ngữ cảnh là nhằm loại bỏ những yếu tố thừa đó mà không làm giảm bớt khả
năng sản sinh ngôn ngữ của văn phạm.
Nếu L là một CFL, nó có thể tạo ra văn phạm CFG với các đặc tính sau:
1. Mỗi biến và mỗi ký tự kết thúc của G đều xuất hiện trong dẫn xuất của
một số xâu trong L.
2. Không có luật sinh nào dạng A → B, mà trong đó A, B đều là biến.
Hơn nữa, nếu ε ∉ L thì không cần luật sinh A → ε. Thực tế, nếu ε ∉ L, ta có
mọi luật sinh trong G đều có một trong hai dạng:
A → BC và A → a với A, B, C N; aT
Phạm Hùng Phú 117
- Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống
hoặc A → aα (α là xâu các biến hoặc ε).
Hai dạng đặc biệt này gọi là dạng chuẩn Chomsky và dạng chuẩn Greibach.
3.2.1. Loại bỏ các ký tự thừa
1) Định nghĩa
Một ký tự văn phạm X (X V = NT) gọi là không thừa nếu tồn tại một
dẫn xuất S * αXβ * w với các xâu α, β bất kỳ V* và w T*. Ngƣợc lại X gọi
là thừa.
Vậy, ký tự không thừa có 2 đặc điểm:
- X là biến thì X phải dẫn ra một xâu các ký tự kết thúc;
- X phải nằm trong dẫn xuất từ S.
2) Bổ đề 1 (Dùng loại bỏ các biến không dẫn ra xâu ký tự kết thúc)
Cho CFG G = (N, T, P, S) với L(G) ≠ ∅, có một CFG G‟= (N‟, T, P‟, S)
tƣơng đƣơng sao cho mỗi A N‟ tồn tại w T* để A * w.
Chứng minh:
Với mỗi biến A N và với mỗi luật sinh A → w với w T* nằm trong P thì
rõ ràng A N‟.
Nếu A → X X ... X là một luật sinh, trong đó mỗi X hoặc là ký tự kết thúc
1 2 n i
hoặc là một biến đã có sẵn trong N‟ thì một xâu các ký tự kết thúc có thể đƣợc dẫn
ra từ A bằng dẫn xuất bắt đầu A X X ... X , vì vậy A N‟.
1 2 n
Tập N‟ có thể tính đƣợc bằng cách lặp lại bƣớc trên cho đến khi không thêm
đƣợc ký tự nào nữa vào N‟.
P‟ là tập tất cả các luật sinh mà các ký tự của nó thuộc N‟ T.
Giải thuật tìm N‟ nhƣ sau:
Begin
OLDN:= ∅; (1)
NEWN:= {A N | A → w P và w T*}; (2)
While OLDN NEWN do (3)
begin
OLDN:= NEWN; (4)
118 Phạm Hùng Phú
- Câu hỏi và bài tập chƣơng 3
NEWN:= {A N | A → α với α (T OLDN)*} (5)
end;
N‟:= NEWN; (6)
end;
Rõ ràng rằng nếu biến A đƣợc thêm vào N‟ tại bƣớc (2) hoặc (5) thì A sẽ dẫn
ra đƣợc xâu ký tự kết thúc. Ta chứng minh rằng nếu A dẫn ra đƣợc một xâu ký tự
kết thúc thì A đƣợc thêm vào tập NEWN.
Dùng chứng minh quy nạp theo độ dài của dẫn xuất A * w.
Nếu độ dài bằng 1 thì A → α là một luật sinh trong P. Vậy A đƣợc đƣa vào
N‟ tại bƣớc (2).
Giả sử kết quả đúng tới k -1 bƣớc dẫn xuất ( k >1)
Nếu A X X ... X * w bằng k bƣớc thì ta có thể viết w = w w ... w ,
1 2 n 1 2 n
trong đó X * w , với 1 ≤ i ≤ n bằng ít hơn k bƣớc dẫn xuất. Theo giả thiết quy nạp
i i
thì các biến X này đƣợc thêm vào N‟. Khi X cuối cùng đƣợc thêm vào N‟ thì vòng
i i
lặp (3) vẫn tiếp tục lặp một lần nữa và A sẽ đƣợc thêm vào N‟ tại (5).
Ta chứng minh L(G‟) = L(G):
Chọn N‟ là tập hợp tại (6) và P‟ là tập tất cả các luật sinh mà các ký tự của
nó thuộc (N‟T) thì chắc chắn rằng có tồn tại văn phạm G‟= (N‟, T, P‟, S) thoả
mãn tính chất: nếu A N‟ thì A * w với w nào đó thuộc T*. Hơn nữa, mỗi luật
sinh của P‟ đều là luật sinh của P nên ta có L(G‟) L(G).
Ngƣợc lại giả sử một từ w L(G) – L(G‟) thì một dẫn xuất bất kỳ của w
phải liên quan đến các biến thuộc N – N‟ hoặc luật sinh thuộc P – P‟ (các dẫn xuất
này đƣa ra các biến thuộc N – N‟), nhƣng do không có biến nào trong N – N‟ dẫn
đến xâu các ký tự kết thúc, điều này dẫn đến mâu thuẫn. Vậy L(G‟) = L(G).
Từ việc chứng minh bổ đề 1, ta có giải thuật sau.
3) Giải thuật loại bỏ biến không dẫn xuất ra xâu các ký tự kết thúc
Input G = (N, T, P, S) - CFG
Output G‟= (N‟, T‟, P‟, S‟) - CFG mà mọi biến của nó đều sinh ra xâu ký tự kết
thúc và L(G‟) = L(G)
Phạm Hùng Phú 119
- Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống
Process
Bước 1: khởi tạo
S‟ = S; T‟ = T; N‟ = {A N A → w P và w T*};
Bước 2: Xác định N‟
Với mỗi luật sinh A → X X ... X P kiểm tra
1 2 n
Nếu X N‟ T‟ i thì N‟ = N‟{A};
i
Bước 3: Quay lại bƣớc 2 cho đến khi gặp một lƣợt không thêm đƣợc biến nào vào
N‟ nữa.
Bước 4: xác định p’
P‟ ={ A → X X ... X P AN‟ và X (N‟ T‟)* i}
1 2 n i
Ví dụ: Xét văn phạm G = (N, T, P, S):
N = S, A, B, C, D
T = a, b, c, d
S = S;
P: có các luật sinh sau:
S → AB | a;
A→a;
C → b;
D → bA.
Áp dụng giải thuật trên, ta có:
1. G‟= (N‟, T‟, P‟, S‟):
T‟ = a, b, c, d S‟ = S;
2. N‟:
Bƣớc N‟ Giải thích
KT {S, A, C} S → a; A → a; C → b
1 {S, A, C, D} D → bA; S → a; A → a; C → b
2 {S, A, C, D} D → bA; S → a; A → a; C → b
3. P‟ = {S → a; A → a; C → b; D → bA}.
4) Bổ đề 2 (Dùng loại bỏ các ký tự không nằm trong xâu đƣợc dẫn xuất ra từ ký tự
bắt đầu văn phạm)
120 Phạm Hùng Phú
- Câu hỏi và bài tập chƣơng 3
Nếu G = (N, T, P, S) là CFG thì ta có thể tìm đƣợc CFG G‟ = (N‟, T‟, P‟, S)
tƣơng đƣơng sao cho mỗi X N‟ T‟ tồn tại α, β (N‟ T‟)* để S * αXβ.
Chứng minh:
Tập N‟ T‟ gồm các ký tự xuất hiện trong dạng câu của G đƣợc xây dựng
bởi giải thuật lặp nhƣ sau:
Bước1: Đặt N‟ = {S}; T‟ = ∅;
Bước2: Với mỗi A N‟ thực hiện
- Tìm tất cả các luật sinh A → α | α | ... | α là các luật sinh trong P
1 2 n
- Nếu có thì thêm tất cả các biến của α , α , ... , α vào N‟ và các ký tự
1 2 n
kết thúc của α , α ,..., α vào T‟.
1 2 n
Bước3: Lặp lại bƣớc 2 cho đến khi không còn biến hoặc ký tự kết thúc nào
đƣợc thêm vào nữa.
Dễ thấy, X N‟ T‟ thì tồn tại α, β (N‟ T‟)* để S * αXβ, trong đó P‟
là tập hợp tất cả các luật sinh của P chỉ chứa các ký tự thuộc (N‟ T‟).
Ta dễ dàng chứng minh L(G‟) = L(G) .
Từ việc chứng minh bổ đề 2, ta có giải thuật sau.
5) Giải thuật loại bỏ ký hiệu không được dẫn xuất ra từ ký hiệu bắt đầu
Input G = (N, T, P, S) - CFG
Output G‟= (N‟, T‟, P‟, S‟) - CFG mà mọi ký hiệu của nó đều đƣợc dẫn xuất ra từ
ký hiệu bắt đầu và L(G‟) = L(G)
Process
Bước1: Khởi tạo
S‟ = S; N‟ = {S}; T‟ = ∅
Bước2: Xác định N‟, T‟
+ Với mỗi A N‟ thực hiện
- Tìm tất cả các luật sinh A → α | α | ... | α là các luật sinh trong P
1 2 n
- Nếu có thì thêm tất cả các biến của α , α , ... , α vào N‟ và các ký tự
1 2 n
kết thúc của α , α ,..., α vào T‟ ;
1 2 n
Phạm Hùng Phú 121
- Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống
Bước3: Quay lại bƣớc 2 cho đến khi gặp một lƣợt không còn biến hoặc ký tự
kết thúc nào đƣợc thêm vào N‟ và T‟ nữa.
Bước 4: xác định p’
P‟ ={ A → X X ... X P AN‟ và X (N‟ T‟)* i}
1 2 n i
Ví dụ 1: Loại bỏ ký tự không đƣợc dẫn xuất ra từ ký hiệu bắt đầu trong văn
phạm sau: G = (N, T, P, S):
N = S, A, B, C, D
T = a, b, c, d
S = S;
P: có các luật sinh sau:
S → AB | a;
A → a;
C → b;
D → bA.
Áp dụng giải thuật trên, ta có:
1. G‟= (N‟, T‟, P‟, S‟):
S‟ = S;
2. N‟, T‟:
Bƣớc N‟ T‟ Giải thích
KT {S}
1 {S, A, B} {a} S → AB a
2 {S, A, B} {a} A→a
3. P‟= {S → AB a; A → a}.
Ví dụ2: Loại bỏ các ký thừa trong văn phạm trên
- Theo ví dụ trên loại bỏ ký tự không đƣợc sinh ra từ ký hiệu bắt đầu ta có văn
phạm với tập luật sinh: S → AB a; A → a.
- Áp dụng giải thuật loại bỏ các biến không sinh ra ký tự kết thúc, ta thu đƣợc
văn phạm với tập luật sinh: S → a
Nhƣ vậy, để loại bỏ các ký thừa trong văn phạm phi ngữ cảnh, ta chỉ việc
thực hiện hai công việc: Loại bỏ các biến không sinh ra ký tự kết thúc và các ký tự
không đƣợc dẫn xuất ra từ ký hiệu bắt đầu. Từ đó ta có định lý.
122 Phạm Hùng Phú
- Câu hỏi và bài tập chƣơng 3
6) Định lý
Mỗi ngôn ngữ phi ngữ cảnh (CFL) không rỗng đƣợc sinh ra từ một văn phạm
phi ngữ cảnh (CFG) không có ký tự thừa.
Chứng minh:
Đặt L = L(G) là CFL không rỗng.
Đặt G là kết quả của việc áp dụng bổ đề 1 vào G và G là kết quả của việc áp
1 2
dụng bổ đề 2 vào G .
1
Giả sử G có ký tự thừa là X. Theo bổ đề 2 ta có S * αXβ. Vì tất cả các ký tự
2 G2
trong G đều có trong G nên theo bổ đề 1: S * αXβ * w với w là xâu ký tự kết
2 1 G1 G1
thúc. Vì vậy không có ký tự nào trong dẫn xuất αXβ * w bị loại bỏ bởi bổ đề 2, vậy X
G1
dẫn ra ký tự kết thúc trong G . Suy ra X là ký tự không thừa (mâu thuẫn).
2
Vậy văn phạm G không có ký tự thừa nào.
2
Ví dụ: Cho văn phạm G = (N, T, P, S):
N = S, , , C, D
T = a, b, c
S = S;
P: S a; a;
S b; b;
D c; A BC;
Hãy loại bỏ các ký tự thừa trong văn phạm trên.
- Áp dụng giải thuật loại bỏ các biến không sinh ra ký tự kết thúc:
1. G‟= (N‟, T‟, P‟, S‟):
T‟ = a, b, c S‟ = S;
2. N‟:
Bƣớc N‟ Giải thích
KT {A, B, D} B → a; A → b; D → c
1 {S, B, D, A} S a; S b; B → a; A → b; D → c
2 {S, A, B, D} S a; S b; B → a; A → b; D → c
Phạm Hùng Phú 123
- Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống
3. P‟= {S →Aa; S → Bb; B → a; A → b; D → c }.
- Áp dụng giải thuật loại bỏ các ký tự không đƣợc dẫn xuất ra từ ký hiệu bắt đầu:
1. G” = (N”, T”, P”, S”):
S” = S;
2. N” và T”:
Bƣớc N” T” Giải thích
KT {S}
1 {S , A, B} {a, b} S a; S b
2 {S, A, B} {a, b} S a; S b; A → b; a
3. P” = {S → Aa; S → Bb; A → b; B → a}.
Khi đó L(G) = L(G”) và G” không chứa ký hiệu thừa.
3.2.2. Luật sinh ε (ε quy tắc)
1) Định nghĩa
- Một luật sinh có dạng A → ε đƣợc gọi là luật sinh ε (ε quy tắc).
- Một biến A đƣợc gọi là biến rỗng (nullable) nếu A + ε
Ta xét đến việc loại bỏ các luật sinh ε. Nếu ε L(G) thì không thể loại đƣợc
tất cả các luật sinh ε, nhƣng nếu ε ∉ L(G) thì có thể. Phƣơng pháp loại bỏ dựa trên
việc xác định liệu một biến A có là biến rỗng hay không ?. Ta có thể thay thế mỗi
luật sinh B → X X ... X bằng tất cả các luật sinh đƣợc định dạng bởi việc xóa bỏ
1 2 n
tập hợp con các biến X rỗng, nhƣng không bao gồm luật sinh B → ε, ngay cả khi tất
i
cả các X đều là biến rỗng.
i
2) Bổ đề 3 (Dùng để loại bỏ luật sinh ε)
Cho CFG G = (N, T, P, S) với ε L(G), có một CFG G‟= (N‟, T, P‟, S)
tƣơng đƣơng sao cho G‟ không chứa luật sinh ε.
Chứng minh:
Ta có thể xác định tập hợp các biến rỗng (nullable) của G bằng giải thuật lặp
nhƣ sau:
- Bắt đầu, nếu A → ε là một luật sinh thì A là biến rỗng.
124 Phạm Hùng Phú
- Câu hỏi và bài tập chƣơng 3
- Kế tiếp, nếu B → α, trong đó α gồm toàn các ký tự là các biến rỗng đã đƣợc
tìm thấy trƣớc đó thì B cũng là biến rỗng.
- Lặp lại cho đến khi không còn biến rỗng nào đƣợc tìm thấy nữa.
Tập luật sinh P‟ đƣợc xây dựng nhƣ sau: Nếu A → X X ... X là một luật sinh trong
1 2 n
P thì ta thêm tất cả các luật sinh A → α α ... α vào P‟ với điều kiện:
1 2 n
1. Nếu X không là biến rỗng thì α = X ;
i i i
2. Nếu X là biến rỗng thì α là X hoặc ε;
i i i
3. Không phải tất cả α đều bằng ε.
i
Đặt G‟ = (N, T, P‟, S). Ta sẽ chứng minh rằng với mọi A N và w T*;
A * ‟ w nếu và chỉ nếu w ≠ ε và A * w.
G G
- Thuận:
i
Đặt A w và w ≠ ε, ta chứng minh quy nạp rằng A * ‟‟ w.
G G
Nếu i = 1 ta có A → w là một luật sinh trong P, và vì w ≠ ε nên luật sinh này
cũng thuộc P‟.
Giả sử kết quả đúng tới i - 1 (i >1)
i -1
Xét A X X ...X w. Ta viết w = w w ...w sao cho với j, X * w .
G 1 2 n G 1 2 n j j
Nếu w ≠ ε và X là biến thì theo giả thiết quy nạp, ta có X ‟‟ w (vì dẫn *
j j j G j
xuất X * w có ít hơn i bƣớc). Nếu w = ε thì X là biến rỗng, vậy A → β β ...β là
j j j j 1 2 n
một luật sinh trong P‟, trong đó β = X nếu w ≠ ε và β = ε nếu w = ε.
j j j j j
Vì w ≠ ε nên không phải tất cả β là ε. Vậy, ta có dẫn xuất:
j
A β β ...β * w β ...β * w w β ...β * ... * w w ...w = w trong G‟‟.
1 2 n 1 2 n 1 2 3 n 1 2 n
- Đảo:
i
Giả sử A ‟ w. Chắc chắn rằng w ≠ ε vì G‟ không có luật sinh ε. Ta quy
G
nạp theo i rằng A * w.
G
Nếu i = 1: Ta thấy A → w là một luật sinh trong P‟, do đó cũng phải có luật
sinh A → w trong P sao cho bằng việc loại bỏ các ký tự rỗng trong α, ta có w. Vậy,
Phạm Hùng Phú 125
- Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống
có tồn tại dẫn xuất A α * w, trong đó α * w liên quan đến các dẫn xuất ε từ
G G
các biến rỗng của α mà chúng ta đã loại bỏ khỏi w.
Giả sử kết quả đúng tới i - 1 (i >1)
i-1
Xét A ‟ X X ... X ‟ w. Phải có luật sinh A → β trong P sao cho
G 1 2 n G
X X ... X tìm đƣợc khi loại bỏ các biến rỗng của β. Vậy A * X X ...X (chứng
1 2 n G 1 2 n
minh tƣơng tự nhƣ ở trên). Ta viết w = w w ...w sao cho với j ta có X * ‟ w
1 2 n j G j
(bằng ít hơn i bƣớc). Theo giả thiết quy nạp X * ‟ w nếu X là biến. Nếu X là ký
j G j j j
tự kết thúc thì w = X và X * w là hiển nhiên. Vậy A * w.
j j j G j G
Hơn nữa S w nếu và chỉ nếu S w. Vậy L(G‟) = L(G) - {ε}.
* *
G‟ G
Từ việc chứng minh bổ đề trên, ta có giải thuật sau.
3) Giải thuật loại bỏ luật sinh
Input G = (N, T, P, S) – CFG, L(G)
Output G‟= (N‟, T‟, P‟, S‟) – CFG, G‟ không chứa luật sinh và L(G‟) = L(G)
Process
Bước1: Khởi tạo
N‟ = N; T‟ = T; S‟ = S; P‟ = ;
R = {AN‟ A → P}
Bước2: Tìm Tập các biến rỗng R
Với mỗi luật sinh A → X X ... X P kiểm tra
1 2 n
Nếu X R i thì R = R{A};
i
Bước3: Quay lại bƣớc 2 cho đến khi không còn biến rỗng nào đƣợc thêm vào
R nữa.
Bước4: Xác định P‟
Với mỗi luật sinh A → X X ... X P không là luật sinh ε thực hiện
1 2 n
Thêm tất cả các luật sinh A → α α ... α vào P‟ với điều kiện:
1 2 n
1. Nếu X không là biến rỗng thì α = X ;
i i i
2. Nếu X là biến rỗng thì α là X hoặc ε;
i i i
126 Phạm Hùng Phú
nguon tai.lieu . vn
