CHƯƠNG 3: VĂN PHẠM PHI NGỮ CẢNH [VPPNC] VÀ VĂN PHẠM CHÍNH QUY [VPCQ]
1
•
Xuất xứ và định nghĩa của VPPNC
2
•
Cây suy dẫn và sự nhập nhằng trong VPPNC
3
•
Văn phạm chính quy
4
•
Giản lược các VPPNC
5
•
Dạng chuẩn Chomsky
6
•
Một số bài toán quyết định đối với các NNPNC
1. XUẤT XỨ VÀ ĐỊNH NGHĨA CỦA VPPNC
1.1. Xuất xứ: từ việc mô tả các ngôn ngữ tự nhiên
Bòvànggặmcỏnon
→ → . . . → . . .
1. XUẤT XỨ VÀ ĐỊNH NGHĨA CỦA VPPNC1.1. Xuất xứ: từ việc mô tả các ngôn ngữ tự nhiên
- Các quy tắc cú pháp như → chính là thuộc dạng các quy tắc trong VPPNC. - Ban đầu các nhà ngôn ngữ học đã đặt hy vọng vào mô hình văn phạm phi ngữ cảnh. Nhưng khi nghiên cứu thêm thì các nhà ngôn ngữ thấy mô hình này còn quá chật hẹp, khó diễn tả hết được sự phong phú và linh hoạt trong các ngôn ngữ tự nhiên.
Nội dung Text: Văn phạm và ngôn ngữ sinh văn phạm
- Văn phạm và ngôn ngữ sinh văn phạm • Định nghĩa ngôn ngữ hình thức • Định nghĩa văn phạm, ngôn ngữ sinh văn phạm và phân loại văn phạm của Chomsky • Một số thuật toán thường gặp trên lớp văn phạm 1/41
- Định nghĩa ngôn ngữ hình thức • Bảng chữ cái • Xâu ký tự • Ngôn ngữ 2/41
- Ngôn ngữ hình thức Bảng chữ cái • Cho ∑ là một tập hữu hạn, khác rỗng các ký hiệu nào đó mà ta gọi là bảng chữ cái. Mỗi phần tử trong ∑ được gọi là một ký tự • Ví dụ ∑={a,b,c,d,….,y} ∑={1,2,3} ; 3/41
- Xâu ký tự • Là một dãy các ký tự trong bảng chữ cái ∑ được viết liền nhau • Độ dài xâu: là số ký tự trong xâu đó • Ví dụ ∑={a,b,c} . s= “baccba” là một xâu trên bảng chữ cái ∑. Xâu s có độ dài bằng 6 • Xâu rỗng: là xâu không có ký tự nào, độ dài bằng 0. Ký hiệu: λ 4/41
- Ngôn ngữ • Mỗi tập từ trên bảng chữ cái ∑ được gọi là ngôn ngữ trên bảng chữ cái đó. • ∑*: là tập tất cả các từ trên bảng chữ cái kể cả xâu rỗng • ∑+ =∑*- {λ} 5/41
- Một số vấn đề cần quan tâm • Với một xâu w ∈ ∑* bất kỳ cho trước, một vấn đề đặt ra là xâu w có thuộc ngôn ngữ L cho trước hay không? [L ∈ ∑* ] • Với một xâu w trong L làm thế nào để sinh w. 6/41
- Văn phạm và ngôn ngữ sinh bởi văn phạm • Định nghĩa văn phạm: – Định nghĩa 1: văn phạm G là một bộ sắp thứ tự gồm 4 thành phần < ∑,∆,I,R >, trong đó: • ∑: Bảng chữ cái, tập các ký hiệu kết thúc. • ∆: tập các chữ cái hỗ trợ, các phần tử [chữ cái hỗ trợ] được gọi là các ký hiệu không kết thúc. » V= [∑U∆]* được gọi là từ điển đầy đủ • I € ∆ được gọi là ký hiệu ban đầu. • R là tập các quy tắc mà mỗi phần tủ của nó có dạng a b, a, b là các từ trên từ điển đầy đủ 7/41
- Văn phạm và ngôn ngữ sinh bởi văn phạm • Định nghĩa văn phạm: – Định nghĩa 2: Cho G= < ∑,∆,I,R > là một văn phạm, một xâu x= αaβ. S = αbβ được gọi là dẫn xuất trực tiếp từ xâu x nếu ta áp dụng quy tắc [luật] a b. Ký hiệu là x╞ s. – Định nghĩa 3: Dãy các xâu D = [w0,w1,….,wk] được gọi là một dẫn xuất của xâu wktừ w0 nếu wi ╞ wi+1 với i=0...k-1. Số k được gọi là độ dài của dẫn xuất. Ký hiệu là w0 |- wk. 8/41
- Ngôn ngữ sinh bởi văn phạm • Định nghĩa: Cho văn phạm G= < ∑,∆,I,R > và D = [w0,w1,….,wk] là một dẫn xuất của xâu wk từ w0 trong văn phạm G. Nếu w0=I và wk ∈ ∑* thì ta gọi xâu wk được sinh bởi văn phạm G. • Ngôn ngữ sinh ra bởi văn phạm G được ký hiệu là L[G] và được định nghĩa như sau: L[G]= {w| w €∑* và I |- w} 9/41
- Ngôn ngữ sinh bởi văn phạm Ví dụ • Cho G= < ∑,∆,I,R > với ∑={a,b} , ∆ = {I}, R= {I aIb, I ab}; L[G] =?. – Chúng ta thấy rằng L[G]={anbn| n€N, n>=1} – Thật vậy dẫn xuất đầy đủ là » D= {I,aIb,…. ,anbn} 10/41
- Văn phạm Ví dụ • Cho G=< ∑,∆,I,R > trong đó ∑={a,b}, ∆={A,B,I}, I là ký hiệu xuất phát và R={I Aba, A BB, B ab,AB b}. 11/41
- Phân loại văn phạm • Nhóm 0: Văn phạm ngữ cấu • Nhóm 1: Văn phạm cảm ngữ cảnh • Nhóm 2: Văn phạm phi ngữ cảnh • Nhóm 3: Văn phạm chính quy 12/41
- Phân loại văn phạm Văn phạm ngữ cấu • Văn phạm G=< ∑,∆,I,R > được gọi là văn phạm ngữ cấu nếu mọi quy tắc r €R đều có dạng r= α β, trong đó α ∈ V+, β ∈ V*. Quy tắc của văn phạm ngữ cấu được gọi là quy tắc ngữ cấu. Ngôn ngữ do văn phạm ngữ cấu[VPNC] sinh ra gọi là ngôn ngữ ngữ cấu [NNNC] . 13/41
- Phân loại văn phạm Văn phạm ngữ cảnh • Văn phạm G=< ∑,∆,I,R > được gọi là văn phạm cảm ngữ cảnh nếu mọi quy tắc r €R đều có dạng r= α β, trong đó α ∈ V+, β ∈ V* và |α|≤|β| . Quy tắc của văn phạm cảm ngữ cảnh được gọi là quy tắc cảm ngữ cảnh. Ngôn ngữ do văn phạm cảm ngữ cảnh[VPCNC] sinh ra gọi là ngôn ngữ cảm ngữ cảnh[NNCNC] . 14/41
- Văn phạm cảm ngữ cảnh Ví dụ • Ví dụ 1: Cho G=< ∑,∆,I,R > trong đó ∑={a,b}, ∆={I}, I là ký hiệu xuất phát và R={I aIb,I II,I ab} là một văn phạm cảm ngữ cảnh. • Ví dụ 2: Cho G=< ∑,∆,I,R > trong đó ∑={a,b,c}, ∆={I,A,B}, I là ký hiệu xuất phát và R={ I abc,I aAbc,Ab Ba,Ac Bbc,bB Bb, aB aaB,aB aa}. Khi đó G là một văn phạm cảm ngữ cảnh. 15/41
- Phân loại văn phạm Văn phạm phi ngữ cảnh • Văn phạm G=< ∑,∆,I,R > được gọi là văn phạm phi ngữ cảnh nếu mọi quy tắc r ∈ R đều có dạng r= A β, trong đó A ∈ ∆,β ∈ V*. Quy tắc của văn phạm phi ngữ cảnh được gọi là quy tắc phi ngữ cảnh. Ngôn ngữ do văn phạm phi ngữ cảnh[VPPNC] sinh ra gọi là ngôn ngữ phi ngữ cảnh[NNPNC] . 16/41
- Văn phạm phi ngữ cảnh Ví dụ • Ví dụ 1: Cho G=< ∑,∆,I,R > trong đó ∑={a,b}, ∆={I}, I là ký hiệu xuất phát và R={I λ,I aIa,I bIb,I aa,I bb} là một văn phạm phi ngữ cảnh. 17/41
- Phân loại văn phạm Văn phạm chính quy • Văn phạm G=< ∑,∆,I,R > được gọi là văn phạm chính quy nếu mọi quy tắc r €R đều có dạng A aB,A a, A ∈ ∆, B ∈ ∆,a ∈ ∑. Quy tắc của văn phạm chính quy được gọi là quy tắc chính quy. Ngôn ngữ do văn phạm chính quy[VPCQ] sinh ra gọi là ngôn ngữ chính quy[NNCQ] . 18/41
- Nhận xét • NNCQ NNPNC NCCNC NNNC • Ngôn ngữ ngữ cấu là tổng quát nhất lớp văn phạm rộng nhất. • Văn phạm chính quy đơn giản hơn cả và có nhiều ứng dụng trong thiết kế các ngôn ngữ lập trình và trong lĩnh vực nghiên cứu về chương trình dịch. 19/41
- Tính chất của văn phạm • Lớp ngôn ngữ sinh ra bởi văn phạm là đóng đối với các phép hợp, giao và phép nhân ngôn ngữ. • Giả sử L1,L2 là hai ngôn ngữ được sinh ra bởi văn phạm G1 =< ∑1,∆1,I1,R1> và G2 =< ∑2,∆2,I2,R2> thì hợp của hai ngôn ngữ L1 và L2 là một ngôn ngữ ký hiệu là L1 ∪ L2 được sinh ra bởi văn phạm sau: 20/41