Chương 8
TÍNH CHẤT CỦA NGÔN NGỮ PHI NGỮ CẢNH
Họ ngôn ngữ phi ngữ cảnh ở vò trí trung tâm trong ngôn ngữ hình thức.
Ngôn ngữ này bao gồm nhiều họ ngôn ngữ quan trọng. Ta chỉ xét đến ngôn ngữ
phi ngữ cảnh đơn đònh và ngôn ngữ phi ngữ cảnh chính qui.
8.1 HAI BỔ ĐỀ BƠM (Pumping)
Bổ đề bơm đã cho trong chương 4 là một công cụ hữu hiệu để biết
được ngôn ngữ nào đó có là ngôn ngữ chính qui hay không. Tương tự bổ đề
cũng được biết đến cho những họ ngôn ngữ khác. Trong chương này ta bàn đến
hai kết qủa Một, là cho ngôn ngữ phi ngữ cảnh trong tổng quát . Hai, một loại
ngôn ngữ phi ngữ cảnh đã được giới hạn.
Bổ đề Bơm cho ngôn ngữ phi ngữ cảnh
Đònh lý 8.1 Cho L là một ngôn ngữ phi ngữ cảnh vô hạn, thì tồn tại một số
nguyên dương m sao cho bất kỳ một chuỗi w ∈ L với |w| ≥ m có thể được
phân rã thành
w = uvxyz (8.1)
với |vxy| ≤ m (8.2)
và |vy| ≥ 1 (8.3)
sao cho
uv
i
xy
i
z ∈ L (8.4)
với mọi i = 0,1,2,3, . . .

Chứng minh
Xem xét ngôn ngữ L – {λ} và văn phạm G không có luật sinh λ và đơn vò

A vAy
2
và A x
là có thể. Điều này chỉ ra những dẫn xuất
S uxy
1
và S uv
i
xy
i
2
y
1
, i = 1,2 . . . (8.6)
là có thể.
Cuối cùng, dạng câu (8.5) phải giảm đến chuỗi tận w, vì vậy ta có
y
2
y
y
1
z
với y, z ∈ T*. Do thế w = uvxyz và (8.6) suy ra rằng uv
i
xy
i
z ở trong L
bởi vì |vy
2
| ≥ 1, thỏa (8.3). Để thỏa (8.2). Ta lấy A để mà A x không có

hạn bởi (8.2) . Vì vậy L là không phi ngữ cảnh.
116
Ví dụ 8.2
Xem xét ngôn ngữ
L = {ww : w ∈ {a, b}*}
Ngôn ngữ này thì gần giống như ngôn ngữ phi ngữ cảnh trong ví dụ 5.1.
Nhưng nó không phi ngữ cảnh
Xem xét chuỗi a
m
b
m
a
m
b
m
Hình 8.1
Dễ thấy, đối phương không có thể chọn vxy, ta luôn có mâu thuẫn với
bổ đề bơm. Cách chọn như hình 8.1, ta chọn i = 0, được chuỗi có dạng.
a
k
b
j
a
m
b
m
, k
<
m hay j
<

số cách chọn. Xem hình 8.2. Bơm i lần, ta được một chuỗi mới có
117

a . . . a b . . . b a . . . a b . . . b

m
2
+ (i – 1)k1 ký tự a và m + (i –1)k2 kí tự b.
Nếu đối phương chọn k1 ≠ 0, k2 ≠ 0, ta chọn i = 0.
Ta có
( m - k2)
2
≤ ( m – 1)
2
= m
2
– 2m + 1

<
m
2
– k1
Kết qủa là không ở trong L
Nếu đối phương chọn k1 = 0, k2 ≠ 0 hay k1 ≠ 0, k2 = 0, thì, một lần nữa với
i = 0, chuỗi được bơm không có trong L. Ta kết luận L không phi ngữ cảnh.

Hình 8.2
Bổ đề pumping cho ngôn ngữ tuyến tính
Trước đây chúng ta đã phân biệt giữa văn phạm phi ngữ cảnh tuyến tính và
không tuyến tính. Bây giờ chúng ta thực hiện sự phân biệt tương tự giữa những

kỳ chuỗi w ∈ L với {w{≥ m có thể được phân rã w = uvxyz với
{uvyz{ ≤ m (8.7)
{vy{ ≥ 1 (8.8)
sao cho
uv
i
xy
i
z
∈
L (8.9)
với mọi i = 0,1,2 . . .
Chú ý : Kết luận của đònh lí này khác đònh lí 8.1 chỉ ở (8.7). Chuỗi v và y được
bơm phải nằm bên trong m kí hiệu của bên trái và cuối bên phải của w tương
ứng. Chuỗi x ở giữa có chiều dài tùy ý.
Chứng minh
Bởi vì, ngôn ngữ là tuyến tính, thì tồn tại một văn phạm tuyến tính G sinh
ra nó. Dùng lý luận như đònh lý 8.1. Ta cũng cần G không chứa luật sinh λ hay
đơn vò. G tuyến tính nên ta phải có u, v, y
1
, y
2

∈
T* . Coi A là một biến đầu tiên,
mà cuối cùng được lặp lại. Trong dẫn xuất riêng phần
S uAz
Có thể có ít nhất | V| bước ( vì không có biến chưa được lặp lại), vì vậy u và z
có thể bò giới hạn.
Tương tự trong

1. Chứng tỏ ngôn ngữ L là phi ngữ cảnh
L = { a
n
: n là số nguyên tố }
2. Chỉ ra rằng ngôn ngữ trên ∑ = {a, b} là không phi ngữ cảnh
a) L = {a
n
b
j
: n ≤ j
2
}
b) L = { a
n
b
j
: n ≥ (j - 1)
3
}
c) L = {a
n
b
j
c
k
: k = jn }
3. Xác đònh ngôn ngữ L là phi ngữ cảnh hay không
a) L = {a
n
ww

Đònh lý 8.3

Họ ngôn ngữ phi ngữ cảnh thì đóng dưới phép hội, kết nối và bao đóng –sao

Chứng minh
Coi L1 và L2 là hai ngôn ngữ phi ngữ cảnh sinh bởi văn phạm
G1 = (V1, T1, S1, P1) và G2 = ( V2, T2, S2, P2) tương ứng, giả sử rằng V1 và V2 rời
nhau.
Coi ngôn ngữ L(G3) sinh bởi văn phạm
G3 = ( V1 ∪ V2 ∪ {S3}, T1 ∪ T2, S3, P3 }
mà S3 ∉ V1 ∪ V2. Luật sinh của G3 là tất cả các luật sinh của G1 và G2
P3 = P1
∪
P2 ∪ {S3 -> S1 | S2}
Hiển nhiên G3 là văn phạm phi ngữ cảnh, nên L(G3) phi ngữ cảnh,
dễ thấy
L(G3) = L1 ∪ L2
Giả sử w ∈ L1
thì S3 => S1 w
là một dẫn xuất có thể trong văn phạm G3. Một lý luận tương tự.
Ta có, w thuộc L2, cũng vậy, nếu w thuộc L(G3) thì
hoặc S3 => S1 hoặc S3 => S2 (8.10)
Vì dạng câu dược dẫn từ S1 , có biến trong V
1
, và V
1
và V
2
rời nhau nên dẫn xuất
S1 w

L2 = {a
n
b
m
c
m
: n ≥ 0, m ≥ 0 }
có một số cách để chỉ ra L1 và L2 là phi ngữ cảnh.
Ví dụ chẳng hạn, một văn phạm cho L1 là
S -> S1S2
S1 -> aS1b | λ
S2 -> cS2|λ
Theo cách chọn, ta chú ý rằng L1 là kết nối của hai ngôn ngữ phi ngữ
cảnh, vì thế nó là phi ngữ cảnh theo đònh lý 8.3. Nhưng
122

L1 ∩ L2 = { a
n
b
n
c
n

: n ≥ 0}
Là không phi ngữ cảnh. Vì vậy họ ngôn ngữ phi ngữ cảnh không đóng dưới phép
giao.
Phần thứ hai của đònh lý, theo đònh lý 8.3 và xem biểu thức

Nếu họ ngôn ngữ phi ngữ cảnh là đóng dưới phép lấy phần bù, thì vế phải của
biểu thức trên phải là ngôn ngữ phi ngữ cảnh cho L1 và L2 bất kỳ. Nhưng ngược lại

(( q
k
, p
l
), x) ∈ ((qi, pj), a, b)
nếu và chỉ nếu
(q
k
, x) ∈
δ
1(q
i
, a, b)
và
δ
2 (p
j
, a) = p
l
123
Ta cũng cần rằng, nếu a = λ thì p
j
= p
l
. Phát biểu , trạng thái của được
đánh nhãn là cặp ( qi, pj), biểu thò cho những trạng thái tương ứng của
M1 và M2 sau khi đọc một số ký hiệu nhập. Dùng qui nạp ta được

((q0, p0), w, z)


n
: n ≥ 0 } ∩ L1

Mà L1 là ngôn ngữ chính qui gồm những chuỗi trong L(a*b*) trừ chuỗi
a
100
b
100
. Do vậy L là phi ngữ cảnh.
Ví dụ 8.8
Chỉ ra rằng ngôn ngữ
L = { w ∈ {a, b, c} : n
a
(w) = n
b
(w) = n
c
(w) }
là không phi ngữ cảnh
Bổ đề bơm có thể sử dụng cho ví dụ này, nhưng ta có thể lý luận ngắn
hơn, bằng cách dùng tính đóng dưới phép giao chính qui. Giả sử rằng L là
phi ngữ cảnh, khi đó
L ∩ L( a* b* c*) = {a
n
b
n
c
n
: n ≥ 0}
cũng là phi ngữ cảnh, nhưng điều này không đúng. Ta kết luận

A z
nhưng, khi đó
S => uAv => ux
n
Ay
n
v => ux
n
zy
n
v
là có thể với mọi n, vì vậy L là vô hạn.
125
BÀI TẬP

1. Cho L trong đònh lý 8.4. chứng tỏ L là tuyến tính
2. Chứng tỏ rằng L là phi ngữ cảnh
a) L = { a
n
b
n
: n ≥ 0 , n không chia hết cho 5}
b) L = { w ∈ {a, b}* : n
a
(w) = n
b
(w), w không chứa chuỗi con aab }
126