Ng Duc Thuan
Lý Thuyết Ngôn Ngữ Hình Thức & Ôtômat 29 Nguyễn Đức Thuần Ch-ơng III

văn phạm phi ngữ cảnh

Trong ch-ơng này chúng ta sẽ khảo sát NN Phi ngữ cảnh, là ngôn ngữ khá gần với
ngôn ngữ tự nhiên và có vai trò quan trọng nhất trong việc ứng dụng xây dựng các ngôn
ngữ lập trình và ch-ơng trình dịch.

3.1 Xuất xứ và Cây suy dẫn của Văn phạm Phi ngữ cảnh:

3.1.1 Xuất xứ:

Xuất xứ của ngôn ngữ phi ngữ cảnh là việc mô tả ngôn ngữ tự nhiên. Cấu trúc câu
của ngôn ngữ tự nhiên đ-ợc định nghĩa bằng các qui tắc ngữ pháp. Ví dụ, câu của ngôn
ngữ tự nhiên (tiếng việt) ở trên bây giờ có thể đ-ợc định nghĩa bởi các qui tắc văn phạm
sau:

1. <Câu > đ <Chủ ngữ> <Vị ngữ>
2. <Chủ ngữ > đ <Danh từ> <Tính từ>
3. <Danh từ > đ gà
4. <Tính từ > đ trống
5. <Vị ngữ > đ <Động từ> <Bổ ngữ>
6. <Động từ> đ ăn
7. <Bổ ngữ > đ <Danh từ>
8. <Danh từ> đ thóc
Một câu đúng ngữ nghĩa đ-ợc suy dẫn từ văn phạm trên :
gà trống ăn thóc

( <biểu thức> ) db <biểu thức> + <biểu thức> db db 3.1 Hình sản sinh một xâu

Việc nghiên cứu các văn phạm phi ngữ cảnh tạo ra một cơ sở lý luận để
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 các ch-ơng trình dịch và cho nhiều ứng dụng khác cho việc xử lý xâu.

3.1.2 Cây suy dẫn trong văn phạm phi ngữ cảnh:

3.1.2.1 Định nghĩa : Cho văn phạm phi ngữ cảnh G = <ồ,D,S,P>. Cây suy dẫn
trong văn phạm phi ngữ cảnh là một cây đ-ợc thành lập từ một suy dẫn nào đó trong G.
Mỗi xâu x ẻồ* mà S
G
x sẽ t-ơng ứng với một cây suy dẫn nào đó. Xâu x đ-ợc gọi là
kết quả của cây suy dẫn.
Cây suy dẫn trong văn phạm phi ngữ cảnh G = <ồ,D,S,P> là một cây thỏa mãn 5
yêu cầu sau:

1. ở mỗi đỉnh đ-ợc gán 1 nhãn. Nhãn gán ở đỉnh là các ký hiệu trong tập
ồẩDẩ{e}. Gốc của cây đ-ợc gán nhãn là S.
2. Mỗi đỉnh trong đ-ợc gán nhãn là một ký hiệu nào đó trong D.
3. Mỗi đỉnh ngoài (lá của cây) đ-ợc gán nhãn là một ký hiệu trong tập ồẩ{e}.


Ng Duc Thuan
Lý Thuyết Ngôn Ngữ Hình Thức & Ôtômat 31 Nguyễn Đức Thuần P : S đ Bẵ BzD
B đ CE
C đ +ẵ-ẵe
D đ CF
E đ F*ẵF*Fẵ*F
F đ GẵFG
G đ 0 ẵ1ẵ2ẵ3ẵ ẵ9

Ta có thể nhận đ-ọc cây dẫn xuất:

S B z D

C E C F

e F * F - F G

F G F G G 3

G 4 G 5 1

3 2



c do

S
if

b S then A

else

a
a
Ng Duc Thuan
Lý Thuyết Ngôn Ngữ Hình Thức & Ôtômat 32 Nguyễn Đức Thuần


. . . X
nHình 3.2 A- cây với chỉ 1 nút trong

Bấy giờ, a= X
1
X
2
X
n
và Ađ a là một sản xuất trong P bởi định nghĩa của cây
suy dẫn. Vậy A a:
S
a
s

b if

then
else

A

a
for

c do


nào đó. Nếu nút mang nhãn X
i
là lá, thì cho a
i
= X
i
. Dễ thấy, nếu i< j, nút j và
mọi nút "con, cháu" của nó là ở bên trái nút i. Vậy thì a = a
1
a
2
a
n
. Vì một cây con thực
sự của cây phải có ít nút hơn trong cây, vậy giả thiết qui nạp là đúng với mọi X
i
-cây với
các nút i không là lá, tức là có X
i
a
i
. Còn các nút là lá thì a
i
= X
i
, vậy cũng có X
i

a
i.

n
= a

Vậy A a. ( Chú ý suy dẫn này chỉ là 1 trong nhiều suy dẫn có thể đ-ợc thành
lập từ cây suy dẫn đã cho).

#. (Điều kiện cần) Bây giờ giả sử A a. Ta cần chứng minh rằng có A-cây với
kết quả là a.
- Nếu A a chỉ với một b-ớc suy dẫn, thì A a là một sản xuất trong P và ta
có A cây nh- hình 3.2 với kết quả là a.
- Giả sử với mọi biến A, nếu có A a là một suy dẫn ít hơn k b-ớc, thì có 1 A-
cây với kết quả là a. Xét suy dẫn A a là k b-ớc. Giả sử trong b-ớc thứ nhất sản xuất
đ-ợc dùng là A đ X
1
X
2
X
n
tức là A X
1
X
2
X
n
a. Thế thì mọi ký hiệu trong a
phải hoặc là trùng với một X
i
nào đó, hoặc là đ-ợc suy dẫn từ một X
i
. hơn nữa, do các sản

Tr-ớc hết dựng một A-cây với n lá có nhãn X
1
, X
2
, ,X
n
; tiếp đó, mỗi nút có nhãn X
i
với
X
i
là biến, sẽ đ-ợc thay bởi cây T
i
t-ơng ứng; còn khi X
i
là ký hiệu cuối, thì không cần
thay gì nữa. kết quả này kết thúc chứng minh.

Hình 3.3 A- cây

3.1.4 Suy dẫn bên trái nhất, suy dẫn bên phải nhất; Sự nhập nhằng:

3.1.4.1 Định nghĩa : Suy dẫn bên trái nhất (nói gọn là suy dẫn trái), nếu ở mỗi
b-ớc suy dẫn, biến đ-ợc thay thế là biến nằm ở bên trái nhất trong dạng câu. T-ơng tự,
suy dẫn bên phải nhất (nói gọn là suy dẫn phải), nếu ở mỗi b-ớc suy dẫn, biến đ-ợc thay
thế là biến nằm ở bên phải nhất trong dạng câu.

Mỗi cây suy dẫn với kết quả a, t-ơng ứng với nhiều suy dẫn S a. Chúng có thể
chỉ khác nhau bởi thứ tự áp dụng các sản xuất.
L-u ý, với cùng một xâu aẻ L(G), có thể có nhiều cây suy dẫn khác nhau, có
cùng kết quả là a. Nói khác hơn xâu a có thể phân tích cú pháp theo nhiều cách khác
nhau.

3.4.1.2 Sự nhập nhằng trong ngôn ngữ phi ngữ cảnh:

Định nghĩa: Cho văn phạm phi ngữ cảnh G = <ồ,D,S,P>, ta nói văn phạm G là
nhập nhằng nếu tồn tại một xâu w là kết quả của 2 cây suy dẫn khác nhau trong G.
Ngôn ngữ do văn phạm G sinh ra là ngôn ngữ nhập nhằng nếu G là văn phạm
nhập nhằng.
Ví dụ 3: Cho văn phạm phi ngữ cảnh G = <ồ,D,S,P>,
ồ = {+,a,*}, D={S}, P = {SđS+S, SđS*S, Sđ a}
ở đây ký hiệu + là phép cộng, * là phép nhân.
Xâu a+a*a là kết quả của cây suy dẫn (thực hiện phép * tr-ớc)
Suy dẫn bên trái nhất ứng với cây suy dẫn là :
S S*S S+S*S a+S*S a+a*S a+a*a


a

a

+

*

S

S

S

S

S

a

+

*

a

a

Ng Duc Thuan
Lý Thuyết Ngôn Ngữ Hình Thức & Ôtômat 35 Nguyễn Đức Thuần

không hề tham gia vào quá trình sinh các ngôn ngữ, hoặc có những qui tắc dạng A đ B
chỉ làm mất thời gian trong quá trình hình thành các xâu của ngôn ngữ. Vì lẽ đó cần loại
bỏ những yếu tố của d- thừa không có ích trong việc sinh ngôn ngữ, sao cho việc loại bỏ
đó không làm ảnh h-ởng tới quá trình sinh ngôn ngữ. Điều đó có nghĩa là chỉ giữ lại các
ký hiệu và các qui tắc có ích trong văn phạm G mà chúng thực sự là cần thiết trong quá
trình sinh ngôn ngữ mà thôi.

3.2.1 Ký hiệu có ích và ký hiệu thừa:

Cho văn phạm phi ngữ cảnh G = <ồ,D,S,P>, X đ-ợc gọi là ký hiệu có ích, nếu tồn
tại suy dẫn S Xò w, ở đây ,ò ẻ(ồẩD)*, X ẻồẩD và wẻồ*.

Nếu ký hiệu X không thỏa mãn điều kiện trên thì X gọi là ký hiệu thừa. Nh- vậy
X là ký hiệu thừa nếu từ X không thể dẫn ra một xâu w ẻồ*. Ký hiệu X có tính chất nh-
vậy còn đ-ợc gọi là ký hiệu vô sinh. Nếu từ ký hiệu ban đầu S không dẫn đ-ợc một xâu
nào có chứa ký hiệu X thì ta nói X là ký hiệu không đến đ-ợc. Nh- vậy một ký hiệu thừa
nếu nó là ký hiệu vô sinh hoặc là không đến đ-ợc.

3.2.2 Bổ đề 1 (loại ký hiệu vô sinh)
Cho một VPPNC G = <ồ,D,S,P>, với L(G) ạặ. Ta có thể xây dựng đ-ợc văn
phạm PNC G' = <ồ,D',S,P'>, t-ơng đ-ơng với G, sao cho mỗi A ẻD' có một xâu w ẻồ*
để A
G
w.

Chứng minh: Duyệt tập sản xuất P của G và kết nạp dần các biến vào D' nh- sau:
- Nếu A đ w là một sản xuất, với AẻD,wẻồ* thì kết nạp A vào D'
Ng Duc Thuan
Lý Thuyết Ngôn Ngữ Hình Thức & Ôtômat 36 Nguyễn Đức Thuần


A tr-ớc sau sẽ đ-ợc đ-a vào D mới. Chứng minh điều đó bằng qui nạp theo độ dài của suy
dẫn A w.

Cơ sở qui nạp:
- Nếu độ dài suy dẫn là 1, thì A đw là một sản xuất, và A đ-ợc kết nạp vào D mới
ở b-ớc 2).
- Giả sử A X
1
X
2
X
n
w bởi suy dẫn k b-ớc. Vậy có thể viết w = w
1
w
2
w
n
,
trong đó X
i
w
i
, với 1 Ê i Ê n, bởi suy dẫn không đến k b-ớc.Theo giả thiết qui nạp, các
X
i
là các b-ớc tr-ớc sau đ-ợc kết nạp vào D mới. Ngay sau khi X
i
đ-ợc kết nạp vào D mới
ở b-ớc 5), trở lại dòng 3) ta có Dcũ ạ D mới vì X

dựng đó ta có L(G) = L(G'), trong đó G' gồm các ký hiệu đến đ-ợc.

Từ 2 bổ đề trên, ta có định lý:

3.2.4 Định lý : Mọi ngôn ngữ PNC không rỗng đều có thể đ-ợc sinh ra từ một văn
phạm phi ngữ cảnh không có ký hiệu thừa.

Ví dụ 4: Cho văn phạm phi ngữ cảnh G = <ồ,D,S,P>, ở đây ồ={a}, D= {S,A,B},
P= {SđAB, Sđa, Ađa} văn phạm sinh ra ngôn ngữ L(G) = {a} ( tập gồm một xâu a).

Văn phạm phi ngữ cảnh G' nhận đ-ợc từ G bằng cách áp dụng các kết quả trên là
văn phạm không có ký hiệu thừa có dạng nh- sau:

G' = <ồ',D',S,P'>, với ồ'= {a}, D'={S}, P' = {S đ a}.
Rõ ràng L(G') = L(G)= {a}.

4%5"6"7"8 9*":;"+<'0"*:*"="#>"?@""$)A'"?B"CDE"+F'0"GGHG4"$I"JK$"8HHG4"
L%M'0"*N"L6"% 9O"$%I,P"'QO":;"+<'0"$%&("$%R"$F"#>"?@"="P")S "?Q'"#>"?@"TP"$%U"L%M'0"
'%V$"$% Q$"-(W "#X"?YZ*"%Q$"*:*"L6"% 9O"$%I,.

Ví dụ 5: Xét văn phạm :
S đ ABẵa
A đ a
áp dụng bổ đề 1, B bị loại cùng với sản xuất S đ AB.
áp dụng bổ đề 2 cho văn phạm
S đ a
A đ a
ta thấy chỉ S và a là đến đ-ợc. Vậy văn phạm t-ơng đ-ơng không chứa ký hiệu
thừa là <{a}, {S}, S ,{Sđa} >.


X
2
X
n
là một sản xuất trong P thì ta đ-a vào P' các sản xuất có dạng
A đa
1
a
2
a
3
a
n
, trong đó:
1. Nếu X
i
là ký hiệu không triệt tiêu thì đặt a
i
= X
i
.
2. Nếu ký hiệu X
i
là ký hiệu triệt tiêu thì a
i
= e hoặc a
i
= X
i
.


3.2.6.1 Định lý : Mọi ngôn ngữ phi ngữ cảnh không chứa xâu e đều có thể sinh ra
từ một văn phạm phi ngữ cảnh không có ký hiệu thừa , các e-sản xuất, và các sản xuất
đơn.

Chứng minh : Giả sử G = <ồ,D,S,P> là văn phạm phi ngữ cảnh và L(G) là ngôn
ngữ của văn phạm G. Không mất tính tổng quát ta có thể giả sử G không có ký hiệu thừa,
không có các e-sản xuất . Ta xây dựng văn phạm phi ngữ cảnh G* = <ồ,D*,S,P*> sinh ra
ngôn ngữ L\{e}=L(G*) trong đó G* không có ký hiệu thừa, không có các e-sản xuất, và
các sản xuất đơn.

Đặt D* = D. Xây dựng P* nh- sau:

Đ-a tất cả các sản xuất không đơn của P vào P*.

Nếu trong P có Ađ B, với A,B ẻD' khi đó sẽ tồn tại dẫn xuất
S aAbaBb awb, ở đây abẻ(ồẩD)*,wẻồ* (do D gồm các ký
hiệu không thừa).

Vậy thay cho A đ B ta đ-a vào P* sản xuất S đ aAb và Ađ w đều là các sản
xuất không đơn nh-ng chức năng sinh ngôn ngữ t-ơng đ-ơng với sản xuất A đ B.

Có thể kiểm chứng L(G*) = L-{e} (Kiểm tra nh- bài tập)

Ví dụ 7 : a. Cho văn phạm phi ngữ cảnh G = <ồ,D,S,P>, trong đó:
ồ= {+,*,a}, D={S,A,B},P= {SđS+A, SđA, AđA*B, AđB, Bđa}

Hãy loại các qui tắc đơn trong văn phạm trên.
Ta xây dựng G* = <ồ,D,S,P*>,
với P* = { SđS+A, AđA*B, Bđa, SđA*B, Ađ a, Sđa} không còn qui tắc đơn và

chuẩn Chomsky nếu mọi sản xuất trong P đều có dạng : A đ BC hoặc A đ a, với A,B,C
ẻD, a là một ký hiệu kết thúc (aẻồ).

3.3.2 Định lý : (+W'0"*%O]'"4%(J.LE): Mọi Văn phạm PNC G = <ồ,D,S,P>,
(L(G) không chứa
e
) bao giờ cũng tồn tại 1 văn phạm dạng chuẩn G
1
= <ồ,D
1
,S,P
1
>, t-ơng
đ-ơng với nó, tức là L(G)=L(G
1
).

Chứng minh : Giả sử G = <ồ,D,S,P>, là văn phạm phi ngữ cảnh nào đó. Theo
định lý 3.2.6.1 thì có thể giả thiết trong P không chứa e-sản xuất, và các sản xuất đơn
AđB với A,BẻD.

Ta có thể giả thiết trong P chỉ gồm các sản xuất có dạng Ađa, hoặc AđB
1
B
2
B
n
ở
đây aẻồ, còn A, B
1


Khi đó ta nhận đ-ợc văn phạm G' = <ồ',D',S,P'> t-ơng đ-ơng với với G nh-ng P'
chỉ gồm sản xuất dạng Ađa, AẻD', aẻồ, AđB
1
B
2
B
n
, với A,B
i
ẻD', i=1,2, n.

Vậy ta có thể giả thiết văn phạm G= <ồ,D,S,P> chỉ chứa các sản xuất dạng :
Ađa, hoặc AđB
1
B
2
B
n
, với A, B
1
B
2
B
n
ẻD, aẻồ.
Có 2 tr-ờng hợp sau xảy ra đối với G:

Tr-ờng hợp 1: Nếu các tập P gồm các sản xuất có dạng:
A đa, AđBC, A,B,C ẻD, aẻồ.

3
, ,K
n-2
đB
n-1
B
n
. ở
đây K
1
, K
2
, ,K
n-2
là các ký hiệu thêm vào.

Đặt D
1
= D'ẩ {K
1
, K
2
, ,K
n-2
}, R
1
={Ađa, AđB
1
K
1

1
> ằ G= <ồ,D,S,P> thỏa mãn điều kiện định lý. Định lý đã
d-ợc chứng minh.

Ví dụ 8: Cho văn phạm phi ngữ cảnh G= <ồ,D,S,P>, ồ= {a,b}, D={S,A},
P={SđaAS, Sđa, AđSbA, AđSS, Ađba}

Ta xây dựng văn phạm G
1
= <ồ,D
1
,S,P
1
>, t-ơng đ-ơng với văn phạm G sao cho G
1

là dạng chuẩn CHOMSKY, tr-ớc hết ta xây dựng văn phạm G'= <ồ,D',S,P'>, với
D'={S,A,
a
,
b
}, P' = {S đ a, Sđ
a
AS, S đS
b
A, AđSS, Ađ
b
a
,
a

}, P
1
= {Sđa, Sđ
a
B
1
, B
1
đAS, AđSB
2
, B
2
đ
b
A, AđSS,
Ađ
b
a
,
a
đa,
b
đ b}.

Ta có thể kiểm chứng đ-ợc L(G') = L(G
1
). Vì L(G') = L(G), suy ra L(G)=L(G
1
) với
G

Bđb,
a
đa,
b
đb}
Kiểm chứng ra có L(G') = L(G).

Từ G' ta xây dựng dạng chuẩn CHOMSKY G
1
= <ồ,D
1
,S,P
1
> nh- sau:
ồ= {a,b}, D
1
={S,A,B, ,
a
,
b
, F
1
, F
2
}
P
1
= {S đ
b
A, Sđ


3.4 Một số bài toán quyết định đối với các NNPNC

Các bài toán mà kết quả mang tính chất tổng quát trả lời tính đặc tr-ng cho
NNPNC gọi là các bài toán quyết định. Ví dụ: Một xâu w có phải thuộc về ngôn ngữ L(G)
không? Hai ngôn ngữ PNC có t-ơng đ-ơng nhau không ? Có một số bài toán quyết
định có thể giải đ-ợc nghĩa là tồn tại giải thuật, và cũng có một số bài toán không giải
đ-ợc .Ví dụ bài toán NNPNC đã cho có nhập nhằng hay không ? là bài toán không giải
đ-ợc.
Ng Duc Thuan
Lý Thuyết Ngôn Ngữ Hình Thức & Ôtômat 42 Nguyễn Đức Thuần
Trong phần này chúng ta sẽ nghiên cứu một số bài toán quyết định giải đ-ợc đối
với các NNPNC.

3.4.1 Tính hữu hạn

3.4.1.1 Định lý : Tồn tại thuật toán để xác định phải chăng một NNPNC cho biết
bất kỳ là :
a. Rỗng
b. Hữu hạn
c. Vô hạn

Chứng minh:
Cho một NNPNC L= L(G) với G = <ồ,D,S,P>.
a. Tính rỗng
- Bổ đề 1, mục 3.2.2 đã cho giải thuật để xác định phải chăng một biến có sinh
một xâu các ký hiệu cuối hay không. Vậy giải thuật đó sẽ khẳng định ký hiệu đầu S có

w: 2
n+1

Ta thấy 1 đ-ờng đi dài nhất trong cây T qua nhiều hơn n+1 đỉnh, và có ít nhất n+1
đỉnh không kết thúc. Do ẵDẵ= n, nên có ít nhất 2 đỉnh chứa 2 ký hiệu không kết thúc
trùng nhau trong T. Goi A là ký tự không kết thúc trùng nhau lần cuối cùng.

Gọi C là đ-ờng đi dài nhất từ ký hiệu A là l thì l Ê n+1. Nói khác hơn xâu sinh ra
ttừ A này là 1 xâu con của w có thể biểu diễn d-ới dạng vxy và ẵvxyẵÊ 2
n+1
= m
Ng Duc Thuan
Lý Thuyết Ngôn Ngữ Hình Thức & Ôtômat 43 Nguyễn Đức Thuần S A

l
A u v x y z

Xét S uAz uvAyz (*)

k
c
k
ẻL , theo định
lý Pumping, chọn k >m ta có w = a
k
b
k
c
k
= uvxyz ẻL.
- Nếu vxy chỉ chứa 1 ký tự hoặc a, hoặc b, hoặc c
ị uv
i
xy
i
z (i 1) sẽ có số l-ợng ký tự a, b, c không bằng nhau ị uv
i
xy
i
zẽL
- Nếu vxy chỉ chứa 2 ký tự hoặc ab, hoặc bc t-ơng tự nh- trên
ị uv
i
xy
i
z (i 1) sẽ có số l-ợng ký tự a, b, c không bằng nhau ị uv
i
xy
i

1
A
1
b
1
a
2
A
2
b
2
a
n+1
A
0
b
n+1
vì vậy để kiểm chứng tính hữu
hạn của G , ta lập một đồ thị có h-ớng nh- sau : Mỗi đỉnh là mộtký tự ch-a kết
Ng Duc Thuan
Lý Thuyết Ngôn Ngữ Hình Thức & Ôtômat 44 Nguyễn Đức Thuần thúc, nếu AđBC thì có một cung từ A đến b, và một cung từ A đến C. Ta
chứng minh rằng L(G) là hữu hạn khi và chỉ khi đồ thị đó không có chu trình.

bcd Nếu có một chu trình, chẳng hạn A
0
A
1

n+1

trong đó các a
i
,b
i
là các xâu biến và ẵ a
i
b
i
ẵ= 1 . Vì văn phạm không có ký hiệu thừa,
nên a
n+1
v, b
n+1
w, với v,w ẻồ* và ẵvwẵ n+1. Vì n 0, nên v và w không thể
đồng thời là e. Mặt khác, vì không có ký hiệu thừa, nên phải có suy dẫn S xA
0
y và suy
dẫn A
0
z. Với x, y, z ẻồ*. Với mọi i ta có :
S xA
0
y xvA
0
wy xv
2
A
0

Đồ thị đ-ợc lập đ-ợc cho ở hình sau: Đồ thị đó không có chu trình. Cấp của S,A,B,C lần l-ợt là 3,2,1, và 0. Chẳng hạn
đ-ờng đi dài nhất của S là S,A,B,C. Vậy văn phạm này sản sinh hữu hạn xâu, và các xâu
này có độ dài không lớn hơn 2
3
= 8. Thực ra, xâu dài nhất suy dẫn đ-ợc từ S là:

S AB BCB CCCB CCCCC aaaaa
Nếu ta thêm vào văn phạm một sản xuất nữa: C đ AB, thì ta đ-ợc đồ thị mới nh-
sau:

Đồ thị này có nhiều chu trình, chẳng hạn A,B,C,A. Vậy ngôn ngữ là vô hạn.



Giả sử G đã ở dạng chuẩn chomsky và ẵxẵ=n 1. tr-ớc hết ta chỉ ra cách xác
định với mỗi i,j và mỗi biến A, phải chăng A x
ịj
?, trong đó x
ịj
là xâu con của x kể từ vị
trí i và có độ dài j.
Qui nạp theo j : - với j =1, A x
ịj
khi và chỉ khi A đ x
ịj
là một sản xuất.
Với j >1, thì A x
ịj
khi và chỉ khi có một sản xuất AđBC và k, 1Ê k Ê j, sao cho
B suy dẫn k ký hiệu đầu của x
ịj
và C suy dẫn j-k ký hiệu cuối của x
ịj
. Cũng tức là:

B x
ịk
và C x
ị+k, j-k

Vì k và j-k cả 2 đều bé hơn j, theo giả thiết qui nạp, ta đã xác định đ-ợc 2 suy dẫn này tồn
tại hay không? đồng thời cũng xác định đ-ợc A x
ịj

begin
5) D
ij
:= ặ;
6) For k:=1 to j-1 do
7) D
ij
:= D
ij
ẩ {AẵAđ BC là một sản xuất, BẻD
ik
,
và C ẻD
i+k,j-k
}
end;
end;
8) If S ẻD
1n
then wẻ L(G)
B-ớc 1 và 2 xử lý tr-ờng hợp j=1. Vì văn phạm G đã cho sẳn, nên b-ớc thứ 2
chiếm một thời gian cố định. Vậy các b-ớc 1 và 2 chiếm thời gian O(n). Các vòng lặp for
ở các dòng 3 và 4 làm cho các b-ớc từ 5 đến 7 lặp lại nhiều nhất là n
2
lần (do i,j Ên).
Ng Duc Thuan
Lý Thuyết Ngôn Ngữ Hình Thức & Ôtômat 46 Nguyễn Đức Thuần B-ớc 5 mỗi lần thực hiện chiếm một thời gian cố định. Vậy tổng thời gian để thực hiện

21
=
x
31
= x
51
= a. Suy ra D
21
= D
31
= D
51
= {A,C}

b a a b a

i 1 2 3 4 5
j
1 B A,C A,C B A,C
2 S,A B S,C S,A
3
ặ
B B
4
ặ
S,A,C5 S,A,C
Chẳng hạn để tính D
24.
đầu tiên đối chiếu D
21
={A,C} với D
33
={B}. Ta có
D
21
D
33
={AB,CB}. Vì có các sản xuất Sđ AB và CđAB nên S và C đ-ợc đ-a vào D
24
. Tiếp
đến lại xét D
22
D
42
={BS,BA} Vì có các sản xuất Ađ BA nên đ-a thêm A vào D
24
. Xét
D
23
D
51
={BA,BC} Vậy D