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

Ch-ơng I

Nhập môn về văn phạm & Ngôn ngữ hình thức

1.khái niệm chung về ngôn ngữ

Ngôn ngữ là ph-ơng tiện giao tiếp. Sự giao tiếp ở đây có thể là giao tiếp giữa
ng-ời với ng-ời, hoặc giữa ng-ời và máy, hoặc giữa máy và máy. Ngôn ngữ giao tiếp
giữa ng-ời với ng-ời gọi là ngôn ngữ tự nhiên, chẳng hạn nh- tiếng Anh, tiếng Pháp
Ngôn ngữ giao tiếp giữa ng-ời và máy nh- các ngôn ngữ lập trình Pascal,C Dù là
ngôn ngữ nào, cũng có thể xem ngôn ngữ là tập hợp các câu có 1 cấu trúc qui định nào
đó. Cấu trúc của ngôn ngữ tự nhiên rất phong phú, đa dạng và phức tạp. Tuy nhiên,
những yêu cầu nghiêm ngặt về mặt ngữ nghĩa trong các ngôn ngữ tự nhiên ch-a cao,
chẳng hạn cùng một từ, hoặc cùng một câu ta có thể hiểu chúng theo những nghĩa khác
nhau tùy theo ngữ cảnh. Để có sự giao tiếp giữa ng-ời và máy, hoặc giữa máy và máy
cần phải có 1 ngôn ngữ mà các qui tắc, cú pháp chặt chẽ hơn, nói khác hơn là 1 từ, 1 câu
thì ngữ nghĩa của chúng phải là duy nhất. Những ngôn ngữ nh- thế gọi là ngôn ngữ
hình thức.

Để xây dựng 1 ngôn ngữ hình thức cần có 1 tập hữu hạn khác rỗng các ký
hiệu nào đó gọi là bảng chữ cái. Dãy hữu hạn các phần tử của 1 bảng chữ cái gọi là
1 từ hay xâu trên bảng chữ cái. Một tập hợp các từ trên bảng chữ cái đ-ợc gọi là ngôn
ngữ.

1.1 bảng chữ cái

Cho
ồ


Ng-òi ta qui -ớc xâu rỗng là xâu có độ dài 0. Xâu rỗng đ-ợc ký hiệu là
e
.
Xâu v đ-ợc gọi là xâu con của xâu w, nếu xâu v đ-ợc tạo bởi 1 dãy các ký hiệu
kề nhau trong w.
Ng Duc Thuan
Lý Thuyết Ngôn ngữ Hình thức & Ôtômat 2 Nguyễn Đức Thuần Ví dụ 4 : ter là một xâu con của xâu Internet.

Tiền tố của 1 xâu là một xâu con nằm ở đầu xâu đó.
Hậu tố của 1 xâu là một xâu con nằm cuối xâu đó.

Ví dụ 5 : Xâu abc có : các tiền tố a, ab, abc, e.
các hậu tố e, c, bc, abc.

Phép ghép: của 2 xâu v và w, ký hiệu vw là 1 xâu tạo bằng cách viết v rồi đến
viết w tiếp theo sau ( không có khoảng cách)

Ví dụ : v = ab, w = ehg thì vw = abehg

(Phép ghép là một phép toán 2 ngôi trên các xâu, đơn vị của phép ghép là xâu
rỗng vì : we = ew = w, "w)

Ng-ời ta ký hiệu : v
0
= e, v
1

*
.

Tập tất cả các từ trên bảng chữ cái ồ mà mọi từ trong nó đều có độ dài khác 0,
đuợc ký hiệu ồ
+
. Từ đó : ồ
+
= ồ
*
\ {e}.

Mỗi tập con của ồ
*
đIợc gọi là 1 ngôn ngữ hình thức trên ồ, nói gọn là một
ngôn ngữ trên ồ
Các tập { } và tập {e} đ-ợc xem là các ngôn ngữ trên bảng chữ cái bất kỳ.

Từ các ngôn ngữ cho tr-ớc, ta có thể thu đ-ợc các ngôn ngữ mới nhờ áp dụng các
phép toán lên ngôn ngữ. vì các ngôn ngữ là tập hợp nên các phép toán tập hợp : giao,
hợp, hiệu đều có thể áp dụng lên các ngôn ngữ.

- Một số phép toán khác lên ngôn ngữ:

Phép ghép tiếp : Cho ngôn ngữ L
1
trên bộ chữ cái ồ
1
, và ngôn ngữ L
2

b. Không có tính giao hoán : L
1
L
2
# L
2
L
1
.
c. Lf = fL = f
d. L{e} = {e}L = L
e. Phép hợp không có tính phân bố với phép ghép tiếp:
L
1
ẩ(L
2
L
3
) # L
1
L
2
ẩ L
1
L
3

f. Phép ghép tiếp có tính phân bố đối với phép hợp:
Ng Duc Thuan
Lý Thuyết Ngôn ngữ Hình thức & Ôtômat 3 Nguyễn Đức Thuần

L
3
)
L
1
ầ (L
2
L
3
) # (L
1
ầL
2
)(L
1
ầL
3
)

Bao đóng của 1 ngôn ngữ L : Ký hiệu L
*
là ngôn ngữ

L
*
= L
0
ẩL
1
ẩL

+
= LL
*
= L
*
L
L
*
= L
+
ẩ {e}

1.4 vấn đề biểu diễn ngôn ngữ và hệ viết lại :

Đối với một ngôn ngữ L trên bảng chữ cái ồ ị L ồ
*
, ng-ời ta th-ờng quan
tâm các vấn đề sau:

-Đối với các ngôn ngữ L , làm sao chỉ rõ các xâu thuộc L. Đây là vấn đề biểu
diễn ngôn ngữ.

Với các xâu hữu hạn, thì để biểu diễn chúng chỉ cần liệt kê các xâu.

Ví dụ 6:
L
1
= { }
L
2

hay nhờ 1 Ôtômat. Văn phạm là một cơ chế cho phép sản sinh ra mọi xâu của ngôn ngữ.
Ng Duc Thuan
Lý Thuyết Ngôn ngữ Hình thức & Ôtômat 4 Nguyễn Đức Thuần

Còn Ôtômat (automata) là một cơ chế cho phép đoán nhận 1 xâu bất kỳ có thuộc về
ngôn ngữ hay không. Tuy nhiên, về mặt hình thức thì cả văn phạm và ôtômat đều là các
biểu hiện khác nhau của cùng 1 quan niệm gọi là hệ viết lại ( Rewriting System).

Một vài ví dụ về ngôn ngữ:

Ví dụ 7: Xét ngôn ngữ L trên bộ chữ cái {a,b,c} gồm các từ có dạng:

c
i
wc
j
, i 0, j 0

Trong đó, w hoặc là từ rỗng, hoặc có tiền tố là chữ a, hoặc có hậu tố là
chữ b. (chẳng hạn
e
, c
3
, cacbac
2
, ca và bc đều thuộc L, trong khi đó không 1 từ nào trong
số các từ ba, c
3
bca
3

2
chứa L)

- Gọi ALPH(L) là bộ chữ cái nhỏ nhất ồ sao cho L là ngôn ngữ trên ồ.
Nếu b là tiền tố của x, ta có thể viết x d-ới dạng x = bz hoặc x = bybz với các từ
y, và z sao cho b không thuộc ALPH(z). Rõ ràng các từ b, byb và z thuộc L. Do đó, x
thuộc L
2
. (Trong phần này ta biểu diễn ALPH(z) cho ALPH({z}; Đúng ra ta cần xét x
phải có dạng x = b
i
z hoặc x = b
i
yb
j
z, nh-ng do b
i
, b
j
thuộc L nên chỉ cần xét các dạng
trên).

Cuối cùng, giả sử c là tiền tố của x. Nếu b không thuộc ALPH(x) thì rõ ràng x
thuộc L. Nếu không, ta có thể viết x d-ới dạng:

x = c
i
ybz với i 0.
và các từ y và z sao cho b không thuộc ALPH(z). Cả 2 : c
i

Từ xâu : aabbab
abab
ab
e

ị aabbab ẻ L. Nếu xem a là dấu (, b là dấu ) thì L gồm các xâu ngoặc đơn lồng
nhau mà không gối lên nhau ( nghĩa là các ngoặc đơn có thể thu đ-ợc từ nhiều biểu thức
toán học đúng đắn khi bỏ các toán hạng, toán tử):

Ví dụ từ biểu thức : (7 + ( x-y)) /(y-1)
ị ( ( ) ) ( ) ằ aabbab Định nghĩa Hệ viết lại :

a. Định nghĩa : Cho 1 bảng chữ cái ồ, P gọi là 1 qui tắc viết lại hay các tập sản xuất
trên ồ nếu P è ồxồ . Nếu (u,v) ẻ P , ký hiệu u đ v. đ-ợc gọi là 1 sản xuất.

b. Định nghĩa : Cho 1 bảng chữ cái ồ, P gọi là 1 qui tắc viết lại hay các tập sản xuất
trên ồ , x,y ẻ ồ* . x đ-ợc gọi là sản sinh trực tiếp y ký hiệu xy $(u,v) ẻP,
x
1
, x
2
ẻ ồ* : x = x
1
ux
2,
y=


ẻồ* : s
1
s
2
, s
2
s
3
ị s
1
s
3

3. " s
1
, s
2
ẻồ* : s
1
s
2
, nếu chỉ thoả 1, 2.

d. Định nghĩa : Một hệ viết lại RW xác định trên bảng chữ cái ồ, là 1 cặp (ồ,P), với
P è ồxồ .

e. Định nghĩa : Một ngôn ngữ đ-ợc sản sinh bởi 1 hệ viết lại RW và 1 tập tiên đề A
( Aèồ*) là tập : L
s
(RW, A) = {w ẻồ*, x w, x ẻ A}

sinh và văn phạm (hệ viết lại) đoán nhận là đối ngẫu và t-ơng đ-ơng . Vì vậy trong giáo
trình này, chỉ đề cập đến văn phạm sinh.

1.6.1 Định nghĩa Văn phạm sinh:

Văn phạm sinh là bộ bốn : G = <ồ, D,S,P>. Trong đó:
ồ : là một bảng chữ , gọi là bảng chữ kết thúc.
D : là một bảng chữ , gọi là bảng chữ không kết thúc thỏa ồầD = ặ
S ẻD đ-ợc gọi là ký hiệu đầu.
P là tập các cặp có thứ tự (a,b) , với a,b ẻ (ồẩD)
*
. (a,b) đ-ợc gọi là một sản
xuất (hay một qui tắc viết lại) th-ờng đ-ợc ký hiệu là ađb. P gọi là tập các qui tắc thay
thế.

Nh- vậy, mỗi văn phạm sinh G tạo thành một hệ viết lại RW = (V,P) với tiên đề
S (ký hiệu V= (ồẩD)), trong đó đ-ợc thiết lập các quan hệ , và (suy dẫn trực tiếp,
suy dẫn - Xem định nghĩa hệ viết lại).

Ví dụ 11: Cho G = <ồ, D,S,P>,
với ồ = {a,b}, D={S}, P ={Sđ aSb,S đab}. Khi đó G là một văn phạm.

Một số định nghĩa bổ sung:

- Cho văn phạm G = <
ồ
,
D
,S,P>,
aẻ

- Hai văn phạm G và G' đ-ợc gọi là t-ơng đ-ơng với nhau nếu L(G) = L(G').

Ví dụ 14 : a. Cho văn phạm G = <ồ, D,S,P>
với ồ = {a,b}, D ={S}, P={S đ aSb, S đe}
L(G) = {a
n
b
n
/ nẻ N, n1}
Cho văn phạm G' = <ồ', D',S',P'>
với ồ' = {a,b}, D' ={S}, P'={S đ aSb, S đab}
L(G') = {a
n
b
n
/ nẻ N, n1}
Ng Duc Thuan
Lý Thuyết Ngôn ngữ Hình thức & Ôtômat 7 Nguyễn Đức Thuần Vậy G và G' là hai văn phạm t-ơng đ-ơng nhau sai khác từ e.

b. Xét văn phạm G = <ồ, D,S,P> với:
ồ = {a,b,c}
D = { S,A,B,C}
P = { S đ abc, S đ aAbc, Ab đ bA, Ac đ Bbcc, bB đBb,
aB đ aaA, aB đ aa}
Xét văn phạm G' = <ồ', D',S,P'> với:
ồ' = {a,b,c}
D' = { S,A,B,C}


Vì S đ a ẻ P nên S' đ a ẻ P' và mọi qui tắc của P là qui tắc của P', nên ta có:
S' đ a w. Vậy S' w hay w ẻ L(G').

Ng-ợc lại, giả sử w ẻ L(G'), lúc đó S' w, ta có thể phân tích suy dẫn này nh-
sau : S' đ a w. Vì S' đ a ẻ P' nên tồn tại S đ a ẻ P; mặt khác trong a không chứa
S' nên các suy dẫn trực tiếp trong a w chỉ sử dụng các qui tắc của P. Vậy ta có:
S w hay w ẻ L(G).

Tóm lại L(G) = L(G').

Ví dụ 15:
G = <{a,b},{S},S,{SđaSbẵab}
G' =<{a,b},{S,S'},S',{SđaSb, S'đaSb,S'đab,Sđab}>

1.7 phân loại văn phạm của chomsky

Chomsky phân loại văn phạm thành 4 nhóm trên cơ sở định nghĩa văn phạm nói
chung:

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

Văn phạm loại 0 : Văn phạm Tổng quát
Văn phạm loại 1 : Văn phạm Cảm ngữ cảnh
Văn phạm loại 2 : Văn phạm Phi ngữ cảnh
Văn phạm loại 3 : Văn phạm Chính qui.

1.7.1 Định nghiã : Văn phạm Tổng quát (General grammar)
Văn phạm G = <

Ví dụ 16 : Văn phạm G = <ồ, D,S,P> với:
ồ = {computer, information, the, swallowed}
D = { S, N
p
, V
p
, N, V, A}
P = {S đ N
p
V
p
, N
p
đ AN, V
p
đ VN
p
, N đ computer, N đ information,
A đ the, V đ swallowed }

G văn phạm loại 0. Ta có đ-ợc một dẫn xuất :
S N
p
V
p
ANV
p
ANVN
p
ANVAN

ẻ
(
ồẩ

D
)
+
. và
ẵaẵÊẵbẵ
. Qui
tắc của văn phạm cảm ngữ cảnh gọi là qui tắc cảm ngữ cảnh. Ngôn ngữ do văn phạm
cảm ngữ cảnh sinh ra đ-ợc gọi là ngôn ngữ cảm ngữ cảnh
(L
1
)
.

Ví dụ 17 : Xét văn phạm G = <ồ, D,S,P> với:
ồ = {a,b,c}
D = { S,A,B,C}
P = { S đ abc, S đ aAbc, Ab đ bA, Ac đ Bbcc, bB đBb,
aB đ aaA, aB đ aa}

ta có thể kiểm chứng đ-ợc G là văn phạm cảm ngữ cảnh và
L(G) = { a
n
b
n
c
n

ồ = {0,1}
D = { S}
P = { S đ SS, S đ 0S1, S đ 10, S đ 01}

ta có thể kiểm chứng đ-ợc G là văn phạm phi ngữ cảnh và
Ng Duc Thuan
Lý Thuyết Ngôn ngữ Hình thức & Ôtômat 9 Nguyễn Đức Thuần

L(G) = { a ẻ {0,1}
*
/ ẵaẵ 2, trong a chữ số 0 bằng chữ số 1}.

b. Xét văn phạm G = <ồ, D,S,P> với:
ồ = {if , then , else , for , do , a, b, c } {S,A}
D = {S,A}
P = { S đ a, S đ if b then A, S đ if b then A else S,A đ a,
A đ for c do S}
cũng là một văn phạm phi ngữ cảnh.

1.7.4 Định nghiã : Văn phạm chính qui (Regular grammar)
Văn phạm G = <
ồ
,
D
,S,P>đ-ợc gọi là văn phạm chính qui, nếu tập qui tắc P
gồm các qui tắc có dạng A
đ
aB, A
đ
a (hoặc A

L
3
L
2
L
1
L
0 . Về mặt cấu trúc ngữ pháp của các qui tắc sinh văn phạm phi ngữ cảnh, và
văn phạm chính qui là đơn giản , có nhiều ứng dụng trong việc thiết kế ngôn ngữ lập
trình và trong nghiên cứu ch-ơng trình dịch

Chú ý: Những văn phạm theo định nghĩa trên, nếu trong tập qui tắc có
thêm qui tắc S đ e, với S là ký hiệu đầu không có mặt ở vế phải của bất cứ qui tắc
nào, ngIời ta cũng xếp vào văn phạm của loại tIơng ứng.

Ta có thể chứng minh

1.7.5 Bổ đề

Nếu
L
là ngôn ngữ loại i

( i = 0,1,2,3) thì
L ẩ
{
e

đ-ợc sinh ra bởi văn phạm G = <ồ, D,S,P> trong đó các
qui tắc của P có dạng r =
a

đ

b
, trong đó a ẻ (ồẩ D)
*
,b ẻ (ồẩ D)
+
. và ẵaẵÊẵbẵ.
Ng Duc Thuan
Lý Thuyết Ngôn ngữ Hình thức & Ôtômat 10 Nguyễn Đức Thuần

Theo bổ đề 1.6.2 ta xây dựng G' = <ồ, D',S',P'> t-ơng đ-ơng với G trong đó S' không
xuất hiện ở vế phải của bất kỳ qui tắc nào, hơn nữa G' cũng loại 1. Bây giờ thêm vào P'
qui tắc S' đe, để đ-ợc G'' cũng loại 1 và: L(G'') = L(G') ẩ {e} = L ẩ {e}.

* Xét
L -
{e}
- Nếu eẽ
L
thì
L -
{e}=
L
. Do đó
L

1
ẩL
2
cũng là ngôn ngữ phi ngữ cảnh (hoặc chính qui).

- Nếu L
1
là ngôn ngữ trên văn phạm phi ngữ cảnh G
1
=<ồ
1
, D
1
, S
1
, P
1
>
- Nếu L
2
là ngôn ngữ trên văn phạm phi ngữ cảnh G
2
=<ồ
2
, D
2
, S
2
, P
2

ẩ
D
2
ẩ
{S}, S, P>
Trong đó : P bao gồm các qui tắc của P
1
và P
2
trừ các qui tắc S
1
đ

e
, S
2
đ

e
, nếu
có thêm vào P các qui tắc S
đ

a
, nếu có S
1
đ

a


- Nếu L
1
là ngôn ngữ trên văn phạm chính qui G
1
=<ồ
1
, D
1
,, S
1
, P
1
>
- Nếu L
2
là ngôn ngữ trên văn phạm chính qui G
2
=<ồ
2
, D
2
, S
2
, P
2
>

Không mất tính tổng quát có thể giả sử : D
1


ồ
2
, D
1
ẩ
D
2
, S
1
, P>
Trong đó : P bao gồm các qui tắc của P
1
và P
2
trừ các qui tắc dạng A
đ
a,
(A
ẻ
D
1

1
, a
ẻ
ồ
1
). Đồng thời thêm vào qui tắc A
đ
aS

- {e}, L
3
là ngôn ngữ chính qui. Khi đó ta còn có:

L
1
L
2
= (L
3
ẩ {e}).L
2
= L
3
L
1
ẩ L
2
là các ngôn ngữ chính qui.

- Tr-ờng hợp L
1
và L
2
chứa
e
. Ta xây dựng văn phạm G nh- sau:
Đặt L
3
= L


Ví dụ 20 : L
1
= { 0
n
/ n 1 } và L
2
= {1
m
/ m 1}

Các ngôn ngữ này lần l-ợt sinh ra bởi các văn phạm sau:

G
1
= <{0}, {S
1
}, S
1
, { S
1
đ 0S
1
, S
1
đ0}>
G
2
= <{0}, {S
2

, S
1
đ0S
2
, S
2
đ 1S
2
, S
2
đ1}>.

1.8.3 Định lý : Nếu L ngôn ngữ chính qui thì L
*
cũng là ngôn ngữ chính qui.

Nếu văn phạm sinh ra L là G=<
ồ
,
D
,, S, P'>
Ta xây dựng văn phạm G=<ồ, D,, S, P>với :
P = P' \ { S
đe
} ẩ {Ađ aS / Ađa
ẻ
P'}
có thể chứng minh L(G) = L*\ {
e
}.