CHƯƠNG I:

NHẬP MÔN VỀ VĂN PHẠM
VÀ NGÔN NGỮ HÌNH THỨC1.1. KHÁI NIỆM NGÔN NGỮ.

1.1.1. Mở đầu:

Từ ngàn xưa con người muốn giao tiếp với nhau phải dùng ngôn ngữ. Ngôn
ngữ để con người có thể giao tiếp với nhau được gọi là ngôn ngữ tự nhiên, chẳng
hạn như tiếng Anh, tiếng Nga, tiếng Việt là các ngôn ngữ tự nhiên. Con người
muốn giao tiếp với máy tính tất nhiên cũng thông qua ngôn ngữ. Con người muốn
máy tính thực hiện công việc, phải viết các yêu cầu đưa cho máy bằng ngôn ngữ
máy hiểu được. Việ
c viết các yêu cầu ta gọi là lập trình. Ngôn ngữ dùng để lập
trình được gọi là ngôn ngữ lập trình.
Cả ngôn ngữ lập trình lẫn ngôn ngữ tự nhiên đều có thể xem như những tập
các từ, tức là 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 đó. Khái
niệm ngôn ngữ được đưa vào trong mục này rất tổng quát. Chắc chắn bao hàm cả
ngôn ngữ lập trình lẫ
n tự nhiên, và cả mọi 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 đến các đặc tả
cú pháp của ngôn ngữ nhiều hơn là đến những vấn đề ngữ nghĩa. Một đặc tả về cú
pháp của một ngôn ngữ có hữu hạn từ, ít nhất về nguyên tắc, có thể được cho
bằng cách liệt kê các từ. Điều đ
ó không thể áp dụng đối với các ngôn ngữ có vô
hạn từ. Nhiệm vụ chính của lý thuyết ngôn ngữ hình thức là nghiên cứu các cách
đặc tả hữu hạn của các ngôn ngữ vô hạn.
Lý thuyết cơ sở của tính toán cũng như của nhiều ngành khác nhau của nó,

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

(t.ư. Σ
+
). Các tập Σ
*
và Σ
+
là vô hạn với bất kỳ Σ nào (thật ra, Σ
*
và Σ
+
là vô hạn
đếm được như Mệnh đề 1.1.5 dưới đây). Về mặt đại số, Σ
*
là một vị nhóm tự do
với đơn vị là từ rỗng ε sinh bởi Σ và Σ
+
là một nửa nhóm tự do sinh bởi Σ.
Đối với các từ α∈Σ

n
ωω
ω
ε
ω

Thí dụ 2:
ε, 0, 01, 101, 1010, 110011 là các từ trên bảng chữ cái V = {0,1}.
beautiful là một từ trên bảng chữ cái Σ = {a, b, c, …, z}.
Trên bảng chữ cái W = {if, then, else, a, b, c, d, e, f, +, −, ∗, /, =, ≠}, nếu α
là từ if a+b=c then c∗d=e và β là từ else c/d=f thì αβ là từ:
if a + b = c then c ∗ d = e else c / d = f.
1.1.4. Định nghĩa:
Độ dài của một từ ω, ký hiệu |ω| hay d(ω), là số các chữ có
mặt trong ω. Theo định nghĩa, |ε|=0.
Hàm độ dài có một số tính chất hình thức của lôgarit: với mọi từ α, β và
mọi số tự nhiên n,
|αβ| = |α| + |β|, |α
n
| = n|α|.
Đảo của một từ có được bằng cách viết các chữ cái theo thứ tự ngược lại;
nếu ω=a
1
a
2
…a
n
là một từ trên bảng chữ Σ thì đảo ω
R
của nó là từ trên bảng chữ Σ:

2
, …, a
n
}. Xét ánh xạ f từ Σ
*
vào tập hợp
N
các số
tự nhiên xác định bởi:
f(ε) = 0, f(a
i
) = i, f(αa
i
) = (n+1)f(α)+i, ∀α∈Σ
*
.
Với α =
,
β
= và f(
α
) = f(
β
). Khi đó,
k
iii
aaa ...
10 h
jjj
bbb ...

u
với 1
≤
u
≤
k hay
α
=
β
. Vì vậy, f là một đơn ánh. Từ đó suy ra
Σ
*
là một đếm
được.
1.1.6. Định nghĩa:
Mỗi tập con của
Σ
*
được gọi là một ngôn ngữ hình thức hay
ngắn gọn hơn là một ngôn ngữ trên
Σ
. Đặc biệt, tập
∅
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
Σ

là
ngôn ngữ vô hạn. Mỗi từ thuộc ngôn ngữ L
2
có số chữ cái a bằng số chữ cái b với
a và b không xen kẻ, a nằm ở phía trái và b ở phía phải của nó.
Các họ ngôn ngữ cụ thể thường được đặc trưng một cách tiện lợi qua các
phép toán xác định trên ngôn ngữ, họ đó gồm các ngôn ngữ nhận được bằng việc
tổ hợp từ một số ngôn ngữ cho trước bởi một số phép toán nào đó. Vì ngôn ngữ là
tập hợp nên ta có các phép toán Boole như
là phép giao, phép hợp, phép hiệu,
phép lấy bù. Chẳng hạn, với L
1
và L
2
là hai ngôn ngữ trên bảng chữ
Σ
thì ta có các
ngôn ngữ mới sau cũng trên bảng chữ
Σ
: L
1
∪
L
2
, L
1
∩
L
2
, L

Σ
2
,
ký hiệu L
1
L
2
, đuợc xác định bởi:
L
1
L
2
= {
αβ
|
α∈
L
1
và
β∈
L
2
}.
Dễ dàng thấy rằng phép ghép có tính kết hợp, nghĩa là với mọi ngôn ngữ
L
1
, L
2
và L
3

(L
2
∪
L
3
) = L
1
L
2
∪
L
1
L
3
, (L
2
∪
L
3
)L
1
= L
2
L
1
∪
L
3
L
1

U
∞
=0n
n
L

Lặp không-
ε
hay
bao đóng ghép không-
ε
của
L
, ký hiệu
L
+
, được định
nghĩa là hợp của mọi luỹ thừa dương của
L
:
L
+
= .
U
∞
=1n
n
L
Thí dụ 5:
1) Xét các ngôn ngữ trên bảng chữ


∪
L
3
= {0, 01}, (L
1

∪
L
2
)(L
1

∪
L
3
) = {00, 001, 010, 0101, 100, 1010}. Do đó
L
1

∪
(L
2
L
3
)
≠
(L
1


1
L
2
= {001, 010, 0101, 0110}, L
1
L
3
= {00,
010}, (L
1
L
2
)
∩
(L
1
L
3
) = {010}. Do đó L
1
(L
2

∩
L
3
)
≠
(L
1

L
3
= {0}, (L
1

∩
L
2
)(L
1

∩
L
3
) =
{010}. Do đó L
1

∩
(L
2
L
3
)
≠
(L
1

∩
L

2n
| n
≥
1}, L
2
= {a
5n+3
| n
≥
0}.
Khi đó, ta có L
1
= {a
2
}
+
, L
2
= {a
5
}
*
{a
3
}.

7
Một phép toán có tầm quan trọng cốt yếu trong lý thuyết ngôn ngữ là phép
cấu xạ, như được định nghĩa dưới đây.
1.1.8. Định nghĩa:

. Đố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ấu xạ f, chỉ cần liệt kê mọi từ f(a)
trên
Σ
’ với a chạy trên mọi chữ cái của
Σ
.
Cấu xạ f gọi là
không xoá
(t.ư.
chữ - thành - chữ
) nếu f(a)
≠ε
(t.ư. f(a)
∈

Σ
’)
với mỗi a
∈

i
thường được đề cập đến như
cách mã hoá
Caesar
. Chẳng hạn,
f
25
(IBM) = HAL, f
3
(HELP) = KHOS.
Dễ dàng thấy rằng các cấu xạ f
i
có tính giao hoán:
f
i
o f
j
= f
j
o f
i
với mọi i, j.
Ngoài ra, f
26-i
o f
i
= f
0
với mọi i
≥

đương nhau. Vì vậy, ở đây ta quan tâm đến cách thứ nhất, tức là ta xét văn phạm
như là một “thiết bị tự động” sinh ra các từ. Vì lẽ đó mà người ta còn gọi các
“thiết bị tự động” đó là văn phạm sinh.
Việc sinh ra các từ có thể được thực hiện bằng nhiều cách khác nhau. Các
từ có thể được sinh ra bởi các văn phạm, bởi các Ôtômat, bởi các máy hình thức
như máy Turing, …Ở đây ta đề cập đến cách của CHOMSKY đưa ra vào những
năm 1956-1957.
1.2.2. Định nghĩa:

Văn phạm
G là một bộ sắp thứ tự gồm 4 thành phần:
G = <
Σ
,
∆
, S, P >,
trong đó:
a)
Σ
là một bảng chữ, gọi là
bảng chữ 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 kết thúc
hay
ký hiệu cơ bản
;
b)

>, trong đó
α
,
β

∈
(
Σ

∪

∆
)
*
và trong
α
chứa ít
nhất một ký hiệu không kết thúc; P được gọi là
tập các quy tắc thay thế
, <
α
,
β
>
được gọi là một
quy tắc
hay
sản suất
và thường được viết cho thuận tiện là
α→β

→
ABC, A
→
aA, B
→
bB, C
→
cC, A
→
a,
B
→
b, C
→
c}>
G
4
= <
Σ
,
∆
, S, P>, trong đó
Σ
={tôi, anh, chị, ăn, uống, cơm, phở, sữa, café},
∆
={<câu>, <chủngữ>, <vịngữ>, <độngtừ1>, <độngtừ2>, <danhtừ1>,<danhtừ2>},
S=<câu>,
P={<câu>
→
<chủngữ><vịngữ>, <chủngữ>