Ngôn ngữ phi ngữ cảnh

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ăn phạm G = ({S}, {a, b}, S, P), có các luật sinh

S → aSa | bSb | λ,

là PNC. Một dẫn xuất điển hình trong văn phạm này là

S ⇒ aSa ⇒ aaSaa ⇒ aabSbaa ⇒ aabbaa

Dễ thấy

L(G) = {wwR: w ∈ {a, b}*}

„ Văn phạm trong ví dụ trên không những là PNC mà còn là

tuyến tính. Các VPCQ và tuyến tính rõ ràng là PNC, nhưng một

VPPNC không nhất thiết là tuyến tính.