Trang 157
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Chương 5 Ngôn ngữ phi ngữ cảnh
5.1 Văn phạm phi ngữ cảnh
5.2 Phân tích cú pháp và tính nhập nhằng
5.3 Văn phạm phi ngữ cảnh và ngôn ngữ lập trình
Trang 158
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Văn phạm phi ngữ cảnh

Định nghĩa 5.1

Một văn phạm G = (V, T, S, P) được gọi là phi ngữ cảnh
(context free) nếu mọi luật sinh trong P có dạng
A → x,
trong đó A ∈ V còn x ∈ (V ∪T)*.

Một ngôn ngữ được gọi là phi ngữ cảnh nếu và chỉ nếu có một
VPPNC G sao cho L = L(G).

Nhận xét

Mọi NNCQ đều là PNC, nhưng điều ngược lại thì không. Như
chúng ta sẽ thấy sau này họ NNCQ là một tập con thực sự của
họ NNPNC.
Trang 159
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Các ví dụ về NNPNC

Ví dụ 1



Ví dụ 3

Ngôn ngữ sau là PNC.
L = {a
n
b
m
: n
≠
m}
Trường hợp n > m Trường hợp m > n VP kết quả
S → AS
1
S → S
1
BS → AS
1
| S
1
B
S
1
→ aS
1
b | λ S
1
→ aS
1
b | λ S

lồng nhau, chẳng hạn (( )) hay (( ) ( )), phổ biến trong các ngôn
ngữ lập trình.
Trang 162
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Dẫn xuất trái nhất và phải nhất

Trong VPPNC mà không tuyến tính, một dẫn xuất có thể bao
gồm nhiều dạng câu với nhiều hơn một biến. Như vậy, chúng ta
có một sự lựa chọn thứ tự biến để thay thế.

Xét văn phạm G = ({A, B, S}, {a,b}, S, P) với các luật sinh
1. S → AB,2.A → aaA, 4. B → Bb,
3. A →λ,5.B →λ.
Dễ dàng thấy rằng văn phạm này sinh ra ngôn ngữ
L(G) = {a
2n
b
m
: n ≥ 0, m ≥ 0}.
Bây giờ xét hai dẫn xuất của chuỗi aab
S AB aaAB aaB aaBb aab
S AB ABb aaABb aaAb aab.
1
⇒
2
⇒
3
⇒
4
⇒

derivation) nếu trong mỗi bước biến trái nhất trong dạng câu
được thay thế. Nếu biến phải nhất được thay thế, chúng ta gọi là
dẫn xuất phải nhất (DXPN - rightmost derivation).
Trang 164
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Ví dụ

Xét văn phạm với các luật sinh (được đánh chỉ số bên tay phải)
S → aAB,1
A → bBb,2
B → A | λ, 3, 4
S aAB abBbB abAbB abbBbbB abbbbB abbbb
là một DXTN của chuỗi abbbb. Một DXPN của chuỗi này là
S aAB aA abBb abAb abbBbb abbbb

DXTN và DXPN có lợi điểm là ta chỉ cần trình bày dãy số hiệu
luật sinh được dùng để sinh ra câu đó mà không sợ bị nhầm lẫn.

DXTN của abbbb là: 123244.

DXPN của abbbb là: 142324.
1
⇒
2
⇒
3
⇒
2
⇒
4

B
Trang 166
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Cây dẫn xuất (tt)

Định nghĩa 5.3

Cho G = (V, T, S, P) là một VPPNC. Một cây có thứ tự là một
cây dẫn xuất cho G nếu và chỉ nếu có các tính chất sau.
1.Gốc được gán nhãn là S.
2.Mỗi lá có một nhãn lấy từ tập T ∪ {λ}.
3.Mỗi nốt bên trong (không phải là lá) có một nhãn lấy từ V.
4.Nếu mỗi nốt có nhãn A ∈ V, và các con của nó được gán
nhãn (từ trái sang phải) a
1
, a
2
, ... , a
n
, thì P phải chứa một
luật sinh có dạng
A
→
a
1
a
2
... a
n
5.Một lá được gán nhãn λ thì không có anh chị em, tức là, một

b
λ
A
b B
b
λ
B
CDX cho chuỗi abbbb