Bước ñầu tìm hiểu một số nội dung về ñại số tổ hợp trên các từ
1LỜI CẢM ƠN

Trong suốt thời gian thực hiện khóa luận tốt nghiệp ngoài sự nỗ lực của
bản thân, tôi còn nhận ñược sự giúp ñỡ, chỉ bảo tận tình của các thầy giáo, cô
giáo trong Khoa Toán – Công nghệ, Trường ðại học Hùng Vương.
ðặc biệt tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo Th.S Hà Ngọc Phú
-Giảng viên bộ môn Toán ứng dụng - Khoa Toán – Công nghệ - Trường ðại học
Hùng Vương. Thầy ñã dành nhiều thời gian quý báu tận tình hướng dẫn tôi trong
suốt quá trình thực hiện khóa luận tốt nghiệp, ñồng thời thầy còn là người giúp
tôi lĩnh hội ñược những kiến thức chuyên môn và rèn luyện cho tôi tác phong
nghiên cứu khoa học.
Qua ñây, tôi xin gửi lời cảm ơn chân thành và sâu sắc tới các thầy giáo, cô
giáo trong Khoa Toán – Công nghệ, tới gia ñình, bạn bè là những người luôn sát
cánh bên tôi, ñã nhiệt tình giúp ñỡ, chia sẻ, ñộng viên tôi trong suốt quá trình
học tập cũng như khi tôi thực hiện và hoàn chỉnh khóa luận này.
Mặc dù ñã rất cố gắng xong khóa luận không khỏi có những thiếu sót. Vì
vậy, tôi rất mong nhận ñược sự góp ý của các thầy giáo, cô giáo và các bạn ñể
khóa luận ñược hoàn thiện hơn.
Tôi xin chân thành cảm ơn!
Việt trì, tháng 05 năm 2012
Sinh viên
Hoàng Thị Hồng Hải

Bước ñầu tìm hiểu một số nội dung về ñại số tổ hợp trên các từ
2

MỤC LỤC

BÀI TẬP CHƯƠNG III 62

KẾT LUẬN 63

TÀI LIỆU THAM KHẢO 64Bước ñầu tìm hiểu một số nội dung về ñại số tổ hợp trên các từ
3

MỞ ðẦU
1. Lý do chọn ñề tài
Tổ hợp là một nhánh của toán học liên quan ñến việc nghiên cứu cấu trúc
rời rạc hữu hạn hay ñếm ñược của một tập hợp. Vấn ñề tổ hợp phát sinh trong
nhiều lĩnh vực của toán học thuần túy ñặc biệt là trong ñại số, lý thuyết xác
suất, cấu trúc liên kết và hình học. Tổ hợp cũng có nhiều ứng dụng trong tối ưu
hóa, khoa học máy tính, lý thuyết ergodic và vật lý thống kê. Toán học tổ hợp
liên quan ñến cả khía cạnh giải quyết vấn ñề lẫn xây dựng cơ sở lý thuyết, trong
ñó “ðại số tổ hợp trên các từ” là một lĩnh vực khá mới mẻ, phát triển ñộc lập
trong một số ngành của toán học như lý thuyết số, lý thuyết nhóm và xác suất…
“Tổ hợp trên từ” xuất hiện thường xuyên trong các vấn ñề của khoa học máy
tính lý thuyết, lý thuyết thiết bị tự ñộng, ñộng lực biểu tượng và ngôn ngữ hình
thức. Cách ñây khoảng 30 năm, các vấn ñề về lý thuyết “Tổ hợp trên từ” vẫn
chưa ñược nghiên cứu một cách kỹ càng hoặc thậm chí còn chưa ñược biết tới.
Nội dung thống nhất của lý thuyết này chính thức xuất hiện lần ñầu tiên trong
cuốn “Tổ hợp trên từ” của Lothaire vào năm 1983, kể từ ñó lĩnh vực này ngày
càng phát triển nhanh chóng. “Tổ hợp trên từ” ñã nghiên cứu các vấn ñề xung
quanh một chuỗi ký tự rút ra từ một bảng chữ cái cố ñịnh, ñây là một kết quả
ñáng ngạc nhiên trong toán học và ngày càng có nhiều ứng dụng rộng rãi trong
các ngành khoa học khác, ñặc biệt là tin học. Các khái niệm về từ, ngôn ngữ,

hợp, ñưa ra các khái niệm, tính chất cơ bản của ñối tượng ñược nghiên cứu
- Phương pháp tổng kết kinh nghiệm: Tổng kết và hệ thống hóa các kiến
thức về vấn ñề nghiên cứu một cách khoa học, ñầy ñủ và chính xác.
- Phương pháp lấy ý kiến chuyên gia: Lấy ý kiến giảng viên trực tiếp
hướng dẫn và các giảng viên khác ñể hoàn thiện về mặt nội dung cũng như hình
thức của khoá luận.
5. ðối tượng và phạm vi nghiên cứu
ðối tượng chính mà khóa luận nghiên cứu là những vấn ñề chung nhất về
ñại số tổ hợp trên các từ mà cụ thể là: Văn phạm và ngôn ngữ hình thức,
Automata, và từ Sturmian.
6. Ý nghĩa khoa học và thực tiễn
Ý nghĩa khoa học: Khóa luận là tài liệu tham khảo phần nào trợ giúp cho
sinh viên chuyên ngành toán muốn bước ñầu tìm hiểu về ñại số tổ hợp trên từ.
Ý nghĩa thực tiễn: ðề tài giúp tôi bước ñầu làm quen với việc nghiên cứu
khoa học, ñồng thời, giúp tôi hiểu những kiến thức cơ bản nhất về ñại số tổ hợp
trên các từ.
7. Bố cục của khóa luận
Ngoài các phần mở ñầu, kết luận và tài liệu tham khảo, nội dung của khóa
luận bao gồm 3 chương:
Chương I: Văn phạm và ngôn ngữ hình thức
1.1. Nửa nhóm
1.2. Khái niệm ngôn ngữ
Bước ñầu tìm hiểu một số nội dung về ñại số tổ hợp trên các từ
5

1.3. Văn phạm và ngôn ngữ sinh bởi văn phạm
1.4. Một số tính chất của ngôn ngữ
Bài tập chương I
Chương II: Automata hữu hạn và ngôn ngữ chính quy
2.1. Automata hữu hạn

thỏa mãn :
( ) ( ) ( ) ,
f uv f u f v u v X
= ∀ ∈

ñược gọi là một cấu xạ.
1.1.4. ðịnh nghĩa : Cho (X, .) là một nửa nhóm,
X
ε
∈
ñược gọi là phần tử
trung lập của X nếu
:
x X x x x
ε ε
∀ ∈ = =
.
Ví dụ 3 : 0 là phần tử trung lập của nửa nhóm (
ℕ
,+)
1.1.5. ðịnh nghĩa : Một nửa nhóm tồn tại phần tử trung lập ñược gọi là vị
nhóm. Phần tử trung lập ñó ñược gọi là phần tử ñơn vị của vị nhóm.
1.1.6. ðịnh nghĩa : X và Y là hai tập con của nửa nhóm S. Tích của X và Y là
một tập hợp :
{ , }
XY xy x X y Y
= ∈ ∈

Khi ñ
ó, t

nhóm v
ớ
i ph
ầ
n t
ử

ñơ
n v
ị

ε
thì
*
{ }
X X
ε
+
= ∪
c
ũ
ng là m
ộ
t v
ị

nhóm v
ớ
i ph
ầ

p các
t
ừ
, t
ứ
c là t
ậ
p các xâu h
ữ
u h
ạ
n các ph
ầ
n t
ử
c
ủ
a m
ộ
t b
ộ
ch
ữ
cái c
ơ
s
ở
nào
ñ
ó.

ữ
ng ngôn ng
ữ
vô ngh
ĩ
a mà ta
có th
ể
ngh
ĩ

ñế
n. V
ề
m
ặ
t truy
ề
n th
ố
ng, lý thuy
ế
t ngôn ng
ữ
hình th
ứ
c liên quan
Bước ñầu tìm hiểu một số nội dung về ñại số tổ hợp trên các từ
7


Từ không có chữ nào gọi là từ rỗng (xâu rỗng) và ñược ký hiệu là
ε
.
Hai từ
1 2

n
a a a
α
=
và
1 2

m
b b b
β
=
là bằng nhau, kí hiệu
α β
=
, nếu n = m và
1,2, ,
i i
a b i n
= ∀ =
.
Tập mọi từ (tương ứng từ khác rỗng) trên bảng chữ cái
∑
ñược ký hiệu là
*

α α
∈∑ ∈ ∑
, việc ñặt
α
và
'
α
cạnh nhau ñể có từ mới
' ( ')
αα
∈ ∑∪∑
ñược gọi là phép ghép
α
với
'
α
. Từ rỗng là phần tử ñơn vị ñối
với phép ghép:
ωε εω ω ω
= = ∀ ∈∑
. Vì phép ghép có tính kết hợp, nghĩa là với
mọi từ
, ,
α β γ
ta có
( ) ( )
αβ γ α βγ
=
, nên ký hiệu
n

={a, b, c,…, z}.
Bước ñầu tìm hiểu một số nội dung về ñại số tổ hợp trên các từ
8

Trên bảng chữ cái
∑
={a, b, c,…, z}, nếu
α
là từ daiso và
β
là từ tohop thì
αβ

là từ daisotohop.
1.2.3. ðịnh nghĩa: ðộ dài của một từ
ω
, kí hiệu là
ω
hay d(
ω
), là số các chữ
cái có mặt trong
ω
. Theo ñịnh nghĩa,
0
ε
=

Hàm ñộ dài có một số tính chất của lôgarit. Với mọi từ
α

R
ω
là
2 1

R
n
a a a
ω
=
.
ω
ñượ
c g
ọ
i là
từ không ñảo
n
ế
u
ω
=
R
ω

T
ừ

α


(t
ươ
ng
ứ
ng
v
ε
=
) thì
α

ñượ
c g
ọ
i là
từ
con ñầu
hay
tiền tố
(t
ươ
ng
ứ
ng
từ con cuối
hay
hậu tố
) c
ủ
a

nguyên nh
ỏ
nh
ấ
t sao cho
, 1,2,
i i p
a a i n p
+
= ∀ = −
. Khi
ñ
ó
ω

ñượ
c g
ọ
i là
từ
có chu kì
. N
ế
u t
ồ
n t
ạ
i hai nhân t
ử
u, v c

ω
.
Tập các từ con của từ
ω
ñược ký hiệu là
( )
F
ω
, tập các từ con có ñộ dài n của
ω
ñược ký hiệu là
( )
n
F
ω

1.2.4. Mệnh ñề: Nếu
∑
là bảng chữ cái thì
*
∑
là tập vô hạn ñếm ñược.
Chứng minh:
Do mỗi số tự nhiên n ñều tồn tại một từ trên
*
∑
có ñộ dài n nên
*
∑
là một

0 1

j j jh
b b b
β
=
và
( ) ( )
f f
α β
=
.
Bước ñầu tìm hiểu một số nội dung về ñại số tổ hợp trên các từ
9

Khi ñó
1
0 1 1
1
0 1 1
( 1) . ( 1) . ( 1).
( 1) . ( 1) . ( 1).
k k
k k
h h
h h
n i n i n i i
n j n j n j j
−
−

là một ngôn ngữ trên
∑
, gọi là ngôn ngữ rỗng; tập
{
}
ε
cũng là một ngôn ngữ trên
∑
, ñây là ngôn
ngữ chỉ chứa từ rỗng và
*
∑
là ngôn ngữ gồm tất cả các từ trên
∑
.
Ví dụ 7: L
1
={
ε
, a, b, ab, aab, aabb, abbb}
L
2
={a
n
b
n

n N
∈
}

ấ
u x
ạ

ñượ
c
ñị
nh ngh
ĩ
a d
ướ
i
ñ
ây.
1.2.6. ðịnh nghĩa: Cho hai ngôn ngữ
1
L
trên bảng
1
∑
và
2
L
trên bảng
2
∑
.
Ghép hay tích của hai ngôn ngữ
1
L

3
ta luôn có:
(L
1
L
2
) L
3
= L
1
(L
2
L
3
)
Ngoài ra, với mọi ngôn ngữ L, ta có:
; { } { }
L L L L L
ε ε
∅ = ∅ = ∅ = =

và phép ghép có tính chất phân phối ñối với phép hợp, nghĩa là
Bước ñầu tìm hiểu một số nội dung về ñại số tổ hợp trên các từ
10

L
1
(L
2
∪

Vì phép ghép ngôn ngữ có tính chất kết hợp nên kí hiệu L
n
ñược dùng cho mọi
ngôn ngữ L và mọi số tự nhiên n theo nghĩa quen thuộc như sau:
1
{ } 0
1
. 1
n
n
khi n
L L khi n
L L khi n
ε
−

=

= =


>


Lặp hay bao ñóng ghép của ngôn ngữ L, kí hiệu là L
*
, ñược ñịnh nghĩa là hợp
của mọi lũy thừa của L:
*
0

{
}
{
}
{
}
{ } { }
{ } { } { }
1 2 3
2 3 1 2 3
1 2 1 3 1 2 1 3
0,01 , 01,10 , 0
010,100 ; ( ) 0,01,010,100
0,01,10 ; 0,01 ;( )( ) 00,001,010,0101,100,101
0
L L L
L L L L L
L L L L L L L L
= = =
= ∪ =
∪ = ∪ = ∪ ∪ =
Do ñó
1 2 3 1 2 1 3
( ) ( )( )
L L L L L L L
∪ ≠ ∪ ∪
tức là phép hợp không có tính chất phân
phối ñối với phép ghép.
{ } { } { }
2 3 1 2 3

, tức là phép giao không có tính chất phân
phối ñối với phép ghép.
2) Xét ngôn ngữ L={0, 1} trên bảng chữ cái
{0,1}
∑ =
:
Ta có:
{
}
2
00,01,10,11
L =
- Tập hợp tất cả các xâu nhị phân có ñộ dài bằng 2.
Bước ñầu tìm hiểu một số nội dung về ñại số tổ hợp trên các từ
11

{
}
3
000,001,010,011,100,101,110,111
L =
- Tập hợp tất cả các xâu nhị phân có
ñộ dài bằng 3.
Tương tự:
n
L
là tập hợp tất cả các xâu nhị phân có ñộ dài bằng n.
Vậy
*
L

ðố
i v
ớ
i ngôn ng
ữ
L trên
∑
,
{
}
( ) ( )
f L f L
α α
= ∈
là ngôn ng
ữ
trên
'
∑
. Theo
ñ
i
ề
u ki
ệ
n (1),
ñể
xác
ñị
nh c

a
∑
.
C
ấ
u x
ạ
f g
ọ
i là
không xóa
( t
ươ
ng
ứ
ng
chữ-thành-chữ
) n
ế
u
( )
f a
ε
≠
(t
ươ
ng
ứ
ng
( ) '

3 7 25
( ) , ( ) , ( )
f a d f y f f z y
= = =

Dễ dàng thấy rằng các cấu xạ
i
f
có tính chất giao hoán:
,
i j j i
f f f f i j N
= ∀ ∈
 
và
26 0
1
i i
f f f i
−
= ∀ ≥


1.3. Văn phạm và ngôn ngữ sinh bởi văn phạm
Ta có thể hình dung một văn phạm như một “thiết bị tự ñộng” mà nó có
khả năng sinh ra một tập hợp các từ trên một bảng chữ cái cho trước. Mỗi từ
ñược sinh ra sau một số hữu hạn bước thực hiện các quy tắc của văn phạm.
Việc xác ñịnh một ngôn ngữ trên bảng chữ cái cho trước có thể ñược thực
hiện bằng một trong các cách thức sau:
Cách 1: ðối với mỗi từ thuộc ngôn ngữ ñã cho, ta có thể chọn một quy

, gọi là bảng chữ không kết thúc hay từ
ñiển cơ bản, mỗi phần tử của nó ñược gọi là một kí hiệu không kết thúc hay kí
hiệu cơ bản.
c)
S
∈∆
ñược gọi là kí hiệu ñầu.
d) P là tập hợp các cặp thứ tự
,
α β
< >
, trong ñó
*
, ( )
α β
∈ ∑∪∆
và trong
α

ch
ứ
a ít nh
ấ
t m
ộ
t kí hi
ệ
u không k
ế
t thúc, P

α β
→
,
α

ñượ
c g
ọ
i là
vế trái
và
β

ñ
u
ợ
c g
ọ
i là
vế phải
c
ủ
a quy t
ắ
c này.
Ví dụ 10: Các bộ bốn sau là các văn phạm:
1
2
{0,1},{ }, ,{ 0 1, }
{ , },{ , }, ,{ , , }

, hay ngắn gọn là
η ω
−
(nếu
không sợ nhầm lẫn), nếu tồn tại quy tắc
P
α β
→ ∈
và
*
, ( )
δ γ
∈ ∑∪∆
sao cho
,
η γαδ ω γβδ
= =
.
ðiều này có nghĩa là nếu
η
nhận vế trái
α
của quy tắc
α β
→
như là từ con thì
ta thay
α
bằng
β

k
ω ω ω
∈ ∑∪∆
sao cho
Bước ñầu tìm hiểu một số nội dung về ñại số tổ hợp trên các từ
13

0
,
k
ω η ω ω
= =
và
1
,
i i
G
ω ω
−
v
ớ
i i=1, 2, …,k. Khi
ñ
ó dãy
0 1
, , ,
k
ω ω ω

ñượ

bởi văn phạm G nếu tồn tại suy dẫn
S G
ω
. Ngôn ngữ sinh bởi văn phạm G
ñược kí hiệu là L(G), là tập hợp xác ñịnh bởi:
*
( ) { }
L G S G
ω ω
= ∈∑
.
Hai văn phạm G
1
và G
2
ñược gọi là tương ñương nếu L(G
1
) = L(G
2
).
Ví dụ 11:
1) Xét văn phạm
1
{0,1},{ }, ,{ 0 1, }
G S S S S S
ε
=< → → >
. Từ 0
4
1

n
≥
) quy tắc 2, sau ñó sử dụng quy tắc 3 ñể kết
thúc, ta có:
1
.
n n n n
S Ab a Ab b a b
+
− = −

Do ñó
1
2
( ) { 0}.
n n
L G a b n
+
= ≥

3) Xét văn phạm
3
{ , , },{ , , , }, ,{ , , , , , , }
G a b c S A B C S S ABC A aA B bB C cC A a B b C c
=< → → → → → → → >

Sử dụng quy tắc 1, rồi m – 1 lần quy tắc 2 (m>0), n-1 lần quy tắc 3 (n>0), k-1 lần
quy tắc 4 (k>0) (có thể xen kẽ). Sau ñó, ñể kết thúc ta sử dụng quy tắc 5, 6, 7 ta
có:
.

}
1
n n
a b n
≥

Hay G
1
và G
2
là tương ñương nhau.
Chẳng hạn như trong G
1
ta có thể viết hai quy tắc ñó dưới dạng
.
S aSb ab
→

2) Cho 2 vă
n ph
ạ
m
3 3 4 4
,{ }, , , ,{ }, ,
G S S P G S S P
=< ∑ > =< ∑ >
, trong
ñ
ó
{0,1,2,3,4,5,6,7,8,9}

ủ
a G
3
, r
ồ
i 1 quy
t
ắ
c trong nhóm 9 quy t
ắ
c c
ủ
a nó, ta có:
1 2 1 1 2 1 1 1

k k k
S Si Si i Si i i i i i
− −
− − − −
. Trong
ñ
ó
1 2 1
, , , 0, 1.
k k
i i i i
−
≥ ≥

Do

s
ố
khác
1}
n
≥
. Vì v
ậ
y G
3
và G
4
không t
ươ
ng
ñươ
ng
nhau.
1.3.5. Bổ ñề: Cho văn phạm
, , ,
G S P
=< ∑ ∆ >
. Khi ñó nếu tồn tại trong P quy
tắc chứa kí hiệu ñầu S ở vế phải thì tồn tại văn phạm G’ tương ñương với G mà
các quy tắc của nó không chứa ký hiệu ñầu ở vế phải.
Chứng minh: Lấy
' ( )
S
∉ ∑∪∆
, xét văn phạm

): Gi
ả
s
ử
dãy d
ẫ
n xu
ấ
t c
ủ
a
ω
là
1

S G G G G
α ω ω
.
Vì
S G
α
nên ta có
,
S P
α
→ ∈
do
ñ
ó
' ',

s
ử
dãy d
ẫ
n xu
ấ
t c
ủ
a
ω
là
' ' '
S G G
α ω
.
Vì
' '
S G
α
nên ta có
' ',
S P
α
→ ∈
do
ñ
ó t
ồ
n t
ạ

c
ủ
a P. V
ậ
y ta có
S G
ω
hay
( )
L G
ω
∈
.
1.3.6. ðịnh nghĩa : Văn phạm
, , ,
G S P
=< ∑ ∆ >
mà không có một ràng buộc nào
trên các quy tắc của nó ñược gọi là văn phạm tổng quát hay văn phạm nhóm 0.
Như vậy, G là văn phạm nhóm 0 khi và chỉ khi các quy tắc của nó có dạng
Bước ñầu tìm hiểu một số nội dung về ñại số tổ hợp trên các từ
15

A
α β ω
→
, trong ñó
(
)
*

Ví dụ 13 : Cho văn phạm
{ , , },{ , , , }, ,
G a b c S A B C S P
=< >
trong ñó
{ , , , , , , }
P S aSAC S abC CA BA BA BC BC AC bA bb C c
= → → → → → → →

Khi ñó văn phạm G là văn phạm cảm ngữ cảnh.
Sử dụng n-1 lần quy tắc 1 (n>0), rồi quy tắc 2, kế ñến sử dụng liên tiếp quy tắc 3,
4, 5 (ñể ñổi chỗ A và C), sau ñó sử dụng n-1 lần quy tắc 6 và n lần quy tắc 7, ta
có :
1
1 1 1
( ) ( )
n
n n n n n n n n n
S a S AC a bC AC a bA C a b c
−
− − −
= − = =

Từ ñó suy ra L(G)=
{
}
1
n n n
a b c n
≥

nào cũng ñược xếp vào lớp văn phạm nhóm 2.
Ví dụ 14:
1) Cho văn phạm
1
{ , },{ , }, ,
G a b S A S P
=< >

Trong ñó:
{ , , , }
P S Sa S Aa A aAb A ab
= → → → →
. Khi ñó G
1
là văn phạm phi
ngữ cảnh.
Sử dụng (m-1) lần quy tắc 1 (m
≥
1), rồi quy tắc 2, sau ñó sử dụng (n-1) lần quy
tắc 3 (n
≥
1), cuối cùng là quy tắc 4 ta có:
1
1 1 1
n
m m n m n n m
S Sa Aaa a Ab a a b a
−
− − −
= − = −

2
' {0,1},{ , '}, ', '
G S S S P
=< >

Trong ñó:
' { , 0 1, 1 0, , ' , ' 0 1, ' 1 0, ' }
P S SS S S S S S S SS S S S S S
ε ε
= → → → → → → → →

Ở ñây G
2
’ cũng không là phi ngữ cảnh. Tuy nhiên, văn phạm G
2
’’ sau là phi ngữ
cảnh và tương ñương với G
2
’, nên cũng tương ñương với văn phạm G
2

2
'' {0,1},{ , '}, ', ''
G S S S P
=< >
.
Trong ñó
'' { , 0 1, 1 0, 01, 10,
' , ' 0 1, ' 1 0, ' 01, ' 10, }
P S SS S S S S S S

∑
≠
ñược gọi là văn phạm chính quy
hay là văn phạm nhóm 3.
Các văn phạm mà quy tắc của chúng có dạng trên, ñồng thời chứa thêm quy tắc
S
ε
→
, miễn sao các kí hiệu ñầu S không xuất hiện ở bất kì vế phải của bất kì
quy tắc nào cũng ñược xếp vào lớp các văn phạm nhóm 3.
Ví dụ 15:
1) Cho văn phạm:
1
{1},{ , , }, ,{ , 1 , 1 , 1 , 1}
G S A B S S S A S B B A A
ε
=< → → → → → >

Khi ñó, G
1
là văn phạm chính quy và
2
1
( ) {1 0}
n
L G n
= ≥
.
Thật vậy, sử dụng quy tắc 1 ta có
2

cuối cùng là quy tắc 4, ta có:
0 0 0 0
S A A
ω ω
− = −

1.3.10. ðịnh nghĩa: Từ các ñịnh nghĩa trên, ta thấy lớp văn phạm tổng quát là
Bước ñầu tìm hiểu một số nội dung về ñại số tổ hợp trên các từ
17

rộng nhất, nó chứa ñựng các văn phạm cảm ngữ cảnh, lớp văn phạm cảm ngữ
cảnh chứa các văn phạm phi ngữ cảnh và lớp văn phạm phi ngữ cảnh chứa các
văn phạm chính quy. Hệ thống các lớp văn phạm này gọi là sự phân cấp
Chomsky.
Ngôn ngữ hình thức ñược gọi là ngôn ngữ tổng quát (tương ứng cảm ngữ
cảnh, phi ngữ cảnh, chính quy) nếu tồn tại văn phạm tổng quát (tương ứng cảm
ngữ cảnh, phi ngữ cảnh, chính quy) sinh ra nó. Vì vậy, ñối với các lớp ngôn ngữ
ta có bao hàm thức:
{ngôn ngữ chính quy}
⊂
{ngôn ngữ phi ngữ cảnh}
⊂
{ngôn ngữ cảm ngữ
cảnh}
⊂
{ngôn ngữ tổng quát}.
Ta cũng thấy, về mặt cấu trúc ngữ pháp thì các quy tắc của các văn phạm
phi ngữ cảnh và văn phạm chính quy là ñơn giản hơn cả và chúng 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 về chương trình
dịch…Vì vậy, trong các phần tiếp theo, chúng ta sẽ dành thêm sự quan tâm tới

1 1 1 1 1 1 2 2 2 1 1 1
2
3
4
,{ , , , }, ,{ , , , , }
,{ }, ,{ , }
,{ , }, ,{ , , , , }
,{ }, ,{ }
n n n n n n
G S A A S S a A A a A A a A A a
G S S S aS S a a
G S A S S S a S aA A aA A a a
G S S S aS a
ε
− − − − −
=< ∑ → → → → >
=< ∑ → → ∈∑ >
=< ∑ → → → → → ∈∑ >
=< ∑ → ∈∑ >

Là các văn phạm chính quy (Riêng ñối với G
4
, nó làm việc không bao giờ dừng,
tức là không có
*
,
ω ω ε
∈∑ ≠
mà G
4

ọ
i là
ả
nh g
ươ
ng c
ủ
a
ω
và nh
ư
ta
ñ
ã bi
ế
t, nó nh
ậ
n
ñượ
c b
ằ
ng cách
vi
ế
t
ω
theo h
ướ
ng ng
ượ

n gi
ả
n h
ơ
n r
ấ
t nhi
ề
u. Th
ậ
t v
ậ
y, L
5
sinh b
ở
i v
ă
n ph
ạ
m phi ng
ữ
c
ả
nh sau:
5
{ , },{ , }, ,{ , , , , , }
G a b S A S S S A A aAa A bAb A aa A bb
ε
=< → → → → → → >

6
{ , , , , ,
, , , , , ,
, , , , }
P S ABC AB aAD AB bAE Da aD Db bD
Ea aE Eb bE DC BaC EC BbC aB Ba bB Bb
aAB a bAB b aC a bC b S
ε
= → → → → →
→ → → → → →
→ → → → →

và b
ằ
ng vi
ệ
c s
ử
d
ụ
ng các quy t
ắ
c trên v
ớ
i ph
ươ
ng pháp quy n
ạ
p ta có
ñượ

=<
∑
∆ >
là văn phạm ngữ cảnh ( tương ứng
phi ngữ cảnh, chính quy). Theo bổ ñề 1.2.6 tồn tại
' , { '}, ', '
G S S P
=< ∑ ∆ ∪ >

tương ñương với G và S’ không xuất hiện ở bất kì quy tắc nào trong P’.
Khi ñó văn phạm:
'' , { '}, ', ' { ' }
G S S P S
ε
=< ∑ ∆ ∪ ∪ → >
cùng loại với G’ và
L(G’’)=L(G’)
∪
{ }
ε
=L(G)
∪
{ }
ε
=L
∪
{ }
ε
.
b)

}=L{
ε
}\{
ε
}.
1.4. Một số tính chất của ngôn ngữ
1.4.1. ðịnh nghĩa: Giả sử L
1
và L
2
là hai ngôn ngữ bất kì ñược sinh bởi văn
phạm và

là một phép toán nào ñó trên lớp các ngôn ngữ. Nếu L
1


L
2
là ngôn
ngữ cũng sinh bởi một văn phạm thì ta nói lớp ngôn ngữ ñó do văn phạm sinh ra
ñóng ñối với phép toán

.
1.4.2. ðịnh lý: Lớp ngôn ngữ sinh ra bởi văn phạm là ñóng ñối với phép hợp.
Chứng minh: Giả sử L
1
, L
2
là ngôn ngữ ñược sinh bởi văn phạm G

1 2 2 2 1 1
( ) ( )
∆ ∩ ∑ ∪∆ = ∆ ∩ ∑ ∪∆ = ∅
.
Lấy
1 1 2 2
S
∉∑ ∪∆ ∪ ∑ ∪∆
.
Xét văn phạm
1 2 1 2
, { }, ,
G S S P
=< ∑ ∪∑ ∆ ∪ ∆ ∪ >
, trong ñó:
Bước ñầu tìm hiểu một số nội dung về ñại số tổ hợp trên các từ
19

1 1 2 2 1 1
( \{ }) ( \{ }) (
P P S P S S S P
ε ε ε ε
= → ∪ → ∪ → → ∈
hoặc
2 2
S P
ε
→ ∈ ∪

1 2

S P
ε
→ ∈
, nên có
1 1
S P
ε
→ ∈
hoặc
2 2
S P
ε
→ ∈
.
Do ñó
1 2
L L
ω ε
= ∈ ∪
.
ω ε
≠
: Tồn tại suy dẫn
S G
ω
và giả sử suy dẫn này là

S G G G G
α β ω
.

ẫ
n xu
ấ
t
, , ,
α β ω
là
ở
trong G
1
, nên ta có
1 1 1 1
S G G G
β ω
, t
ứ
c là
1
( )
L G
ω
∈
. N
ế
u
2
S
α
=
thì dãy d

b)
1 1
: :
L L
ω ω ε
∈ ∪ =
T
ồ
n t
ạ
i
1 1
S P
ε
→ ∈
ho
ặ
c
2 2
S P
ε
→ ∈
, nên có
S P
ε
→ ∈
.
Do
ñ
ó

ng
2
L
ω
∈
0 thì ta có suy d
ẫ
n
1 1
S G
ω
(t
ươ
ng
ứ
ng
2 2
S G
ω
) v
ớ
i các quy t
ắ
c
ñượ
c s
ử
d
ụ
ng thu

S G S G
ω
).
Do
ñ
ó
( )
L G
ω
∈
.
Vì v
ậ
y,
1 2
( )
L G L L
= ∪
.
T
ậ
p quy t
ắ
c P c
ủ
a v
ă
n ph
ạ
m G

.
1.4.3. Hệ quả : Nếu L
1
hoặc L
2
là hai ngôn ngữ chính quy (tương ứng phi ngữ
cảnh, cảm ngữ cảnh) thì
1 2
L L
∪
cũng là ngôn ngữ chính quy (tương ứng phi ngữ
cảnh, cảm ngữ cảnh).
Ví dụ 17 : Cho hai ngôn ngữ
2
1
{ 0}
n n
L a cb n
= ≥
và
2
2
{ 0}
n n
L a cb n
= ≥
trên bảng
chữ cái
{ , , }
a b c

2
1 1 1 1
( )
n n n n n n
S G A S B G a c bb a cb
=

Tương tự, trong G
2
ta có
2
2 2
n n
S G a cb
. Từ ñó văn phạm G và G’ :
1 2
1 2
,{ , , , , , , }, , ;
' ,{ , , , , , , }, , '
G S A B S C D S S P
G S A B S C D S S P
=<
∑
>
=<
∑
>

Trong ñó :
1 1 1 2 2 2

cb
2n
, a
2n
cb
n
n
≥
0}.
1.4.4. ðịnh lý : Lớp ngôn ngữ sinh ra bởi văn phạm là ñóng ñối với phép ghép.
Chứng minh : Giả sử L
1
, L
2
là ngôn ngữ ñược sinh bởi văn phạm G
1
, G
2
hay
L
1
= L(G
1
), L
2
= L(G
2
)
Ta chứng minh tồn tại văn phạm G sao cho L(G) = L
1

1 1 2 2 1 2 2 2 1 1
( \ { }) ( \{ }) { } { }
P P S P S S S S P S S S P
ε ε ε ε
= → ∪ → ∪ → → ∈ ∪ → → ∈ ∪
1 1
{
S S P
ε ε
→ → ∈
và
2 2
S P
ε
→ ∈ ∪
1 2
{ }
S S S
→

(
Ở

ñ
ây ta hi
ể
u r
ằ
ng n
ế

ế
ph
ả
i c
ủ
a b
ấ
t kì m
ộ
t quy t
ắ
c nào trong P
1
(t
ươ
ng
ứ
ng P
2
).
V
ớ
i v
ă
n ph
ạ
m G này, d
ễ
dàng có
ñượ

ph
ạ
m chính quy G’ sao cho L(G’)=L
1
L
2

a)
1
L
ε
∉
và
2
L
ε
∉
(t
ứ
c là
1 1
S P
ε
→ ∉
và
2 2
S P
ε
→ ∉
:

ðặ
t L
1
’ = L
1
\{
ε
} thì theo b
ổ

ñề
1.2.12, ta xây d
ự
ng
ñượ
c
v
ă
n ph
ạ
m chính quy G
1
’ sao cho L(G
1
’) = L
1
’. Khi
ñ
ó theo a), ta có v
ă

1
L
ε
∉
và
2
L
ε
∈
, tương tự như trường hợp b)
d)
1
L
ε
∈
và
2
L
ε
∈
: ðặt L
1
’ = L
1
\{
ε
} và L
2
’ = L
2

= ≥
và
2
{ 1}
n
L c n
= ≥
. Dễ dàng có
ñược L
1
=L(G
1
) và L
2
=L(G
2
), trong ñó
1 1 1 1 1 1
2 2 2 2 2 2
{ , },{ }, ,{ , } ,
{ },{ }, ,{ , }
G a b S S S aS b S ab
G c S S S cS S c
=< → → >
=< → → >

Từ ñó nhận ñược văn phạm phi ngữ cảnh G :
1 2 1 1 1 2 2 2 1 2
{ , , },{ , , }, ,{ , ,{ , , }
G a b c S S S S S aS b S ab S cS S c S S S

4
= L(G
4
), trong ñó G
3
và G
4
là hai văn phạm chính quy:
1 1 1 1 1
4 2 2 2 2 2
{ , },{ , }, ,{ , , , } ,
{ , },{ }, ,{ , }
G a b S A S S b S bA A aA A a
G a b S S S bS S a
=< → → → → >
=< → → >

T
ừ ñó ta nhận ñược văn phạm chính quy G’ :
1 2 1
1 1 2 2
' { , },{ , , }, , '} ,
' { , , , }
G a b S S S S P
P S bA A aA S bS S a
=< >
= → → → →

Thỏa mãn L(G’) = L
3

Khi ñ
ó G’ là v
ă
n ph
ạ
m chính quy. Ta ch
ứ
ng minh L(G’)=L\
{ }
ε
.
a)
( ') :
L G
ω
∈
Ta có
S G
ω
v
ớ
i
ω ε
≠
vì
'
S P
ε
→ ∉
. Không m

a
ω ω
=
. Nh
ư
v
ậ
y t
ồ
n t
ạ
i các quy t
ắ
c
1 1 2 2 1 1
, , ,
n n
A a S A a S A a S
− −
→ → →
trong P’ và do
ñ
ó t
ồ
n t
ạ
i các quy t
ắ
c
1 1 2 2 1 1

n
S
ω
=

không s
ử
d
ụ
ng m
ộ
t quy t
ắ
c nào khác ngoài quy t
ắ
c c
ủ
a P, nên
( )
n
L G
ω
∈
.
V
ậ
y
*
n
n


trong
ñ
ó
1
\{ },1
L i n
ω ε
∈ ≤ ≤
. Nh
ư
v
ậ
y trong G có các suy d
ẫ
n
' '
i i i i i
S A a
ω ω ω
= − =
và cu
ố
i các suy d
ẫ
n này có s
ử
d
ụ
ng các quy t

Hay
( ')
L G
ω
∈
.
Cu
ố
i cùng, theo b
ổ

ñề
1.2.12, L(G) chính quy, kéo theo L(G)
{ }
ε
∪
c
ũ
ng chính
quy.
1.4.7. Mệnh ñề : Mọi ngôn ngữ hữu hạn ñều là ngôn ngữ chính quy.
Chứng minh : Ngôn ngữ hữu hạn là hợp hữu hạn của các ngôn ngữ một từ, từ ví
dụ 13 (ngôn ngữ một từ là ngôn ngữ chính quy) và từ hệ quả 1.3.3 (hợp hữu hạn
của các ngôn ngữ chính quy là chính quy), ta có ngôn ngữ hữu hạn là chính quy.
Ví dụ 19 : Cho ngôn ngữ chính quy L={0, 01, 011, 0111}. Khi ñó L sinh bởi văn
phạm chính quy G=<{0,1}, {S, A, B, C}, S, P>.
Trong ñó
{ 0, 0 , 1, 1 , 1, 1 , 1}
P S S A A A B B B C C
= → → → → → → →


BÀI TẬP CHƯƠNG I
1. Tìm các ngôn ngữ L
1
, L
2
, L
3
sao cho :
a)
* * *
1 2 1 2
( )
L L L L
≠

b)
* * *
1 2 1 2
( )
L L L L
∩ ≠ ∩

c)
* * *
1 2 1 2
( )
L L L L
∪ ≠ ∪


1 2 1 2
( ) ( )
L L L L
= ∪

3. Hãy xác ñịnh xem các văn phạm dưới ñây sinh ra ngôn ngữ nào ?
a) G=<{0,1}, {S, A}, S,
{ 0 , 1 , }
S A A S S
ε
→ → →
>.
b) G=<{a, b}, {S}, S,
{ , }
S SaS S b
→ →
>.
c) G=<{a, b, c}, {S}, S,
{ , , , }
S aca S bcb S aSa S bSb
→ → → →
>.
d) G=<{0, 1, 2,…, 9}, {S,A}, S,
{ , 01 2 3 4 5 6 7 9}
S SA A A
→ → >
.
4. Hãy thành lập các văn phạm sinh ra các ngôn ngữ dưới ñây:
a)
*

5. Hãy xây dựng các văn phạm chính quy sinh ra các ngôn ngữ sau ñây trên bảng
chữ cái
{0,1}
∑ =
;
a)
*
{0 1 }
L
ω ω
= ∈∑

b)
*
{L
ω
= ∈∑
trong
ω
chứa ñúng một chữ số 1}.
c)
*
{L
ω
= ∈∑
trong
ω
chứa ñúng một chữ số 0}.
d)
*


∪
{1100}
*
.
d)
{ 0, 0, 0}
m n k
L a b c n m k
= ≥ ≥ ≥

8. Chứng minh rằng lớp ngôn ngữ sinh bởi văn phạm là ñóng ñối với phép giao.