Bài giảng Lý thuyết tính toán: Bài 6 - Phạm Xuân Cường

Chia sẻ: Bạch Khinh Dạ Lưu | Ngày: | Loại File: PDF | Số trang:30

Thêm vào BST

Báo xấu

22
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Lý thuyết tính toán: Bài 6 - Phạm Xuân Cường cung cấp cho học viên các kiến thức về văn phạm phi ngữ cảnh; khái niệm văn phạm phi ngữ cảnh; định nghĩa hình thức; văn phạm nhập nhằng; dạng chuẩn tắc Chomsky; cây dẫn xuất;... Mời các bạn cùng tham khảo chi tiết nội dung bài giảng!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Lý thuyết tính toán: Bài 6 - Phạm Xuân Cường

LÝ THUYẾT TÍNH TOÁN BÀI 6: VĂN PHẠM PHI NGỮ CẢNH Phạm Xuân Cường Khoa Công nghệ thông tin cuongpx@tlu.edu.vn
Nội dung bài giảng 1. Khái niệm 2. Định nghĩa hình thức 3. Văn phạm nhập nhằng 4. Dạng chuẩn tắc Chomsky 1
Khái niệm
Khái niệm • Văn phạm phi ngữ cảnh = Context-free Grammar (CFG) • CFG: Là một phương pháp mạnh hơn để mô tả ngôn ngữ • Ứng dụng: - Bộ biên dịch trong các ngôn ngữ lập trình - Bộ phân tích trong các trình biên dịch và thông dịch • Ví du: E→E+T|T T→T×F|F F → (E) | a 2
Khái niệm Một văn phạm gồm có: • Tập các quy tắc thay thế ≡ các sản xuất • Mỗi quy tắc là một dòng bao gồm 1 ký hiệu và 1 xâu được ngăn cách bởi dấu mũi tên • Ký hiệu ≡ biến ≡ Các ký hiệu in hoa • Ký hiệu kết thúc ≡ Các ký hiệu in thường, số hoặc ký tự đặc biệt • Biến ban đầu thường xuất hiện bên trái của quy tắc trên cùng 3
Ví dụ E→E+T|T T→T×F|F F → (E) | a • Dẫn xuất E⇒E+T⇒T+T⇒F+T⇒a+T ⇒ a + F ⇒ a + (E) ⇒ a + (T) ⇒ a + (T × F) ⇒ a + (F × F) ⇒ a + (a × F) = a + (a × a) Cũng có thể viết: ∗ E=⇒ a + (a × a) ∗ ∗ E=⇒ a + (E) ⇒ a + (T) ⇒ = a + (a × a) 4
Ví dụ • Dẫn xuất trái nhất: Luôn lựa chọn dẫn xuất ở bên trái . . . ⇒ F + T ⇒ a + T ⇒ . . . a + (a × a) • Dẫn xuất phải nhất: Luôn lựa chọn dẫn xuất ở bên phải . . . ⇒ F + T ⇒ F + F ⇒ . . . a + (a × a) 5
Cây dẫn xuất E E + T T F F ( E ) a T T x F F a a 6
Định nghĩa hình thức
Định nghĩa hình thức CFG: G = (V,Σ,R,S) Trong đó: • V là tập hữu hạn gồm các biến • Σ là tập hữu hạn các ký hiệu kết thúc Σ 6 ∩ V • R tập các quy tắc • S biến bắt đầu 7
Định nghĩa hình thức Định nghĩa 1 ∗ Ngôn ngữ của văn phạm là {w|w ∈ Σ* và S = ⇒ w} Định nghĩa 2 Một ngôn ngữ phi ngữ cảnh (CFL) là ngôn ngữ được tạo ra bởi một văn phạm phi ngữ cảnh (CFG) 8
Ví dụ CFL • S → (S)|SS|ε A = {ε, (),()(),(()()), . . . } • Ngôn ngữ B = {0n 1n | n ≥ 0} S→ε S → 0S1 9
Ví dụ Cho CFG sau: a+a*a E→E+E → Mỗi cây dẫn xuất đều có duy →E×E nhất một cây dẫn xuất trái nhất → (E) và duy nhất một cây dẫn xuất →a phải nhất E E E * E E + E E + E a a E * E a a a a 10
Văn phạm nhập nhằng
Ngôn ngữ nhập nhằng Chuỗi nhập nhằng: • Có nhiều hơn 2 cây dẫn xuất ⇔ Có nhiều cách để tạo ra chuỗi đó Văn phạm nhập nhằng: • Một văn phạm là nhập nhằng nếu một vài chuỗi có thể được sinh ra bởi nhiều cách 11
Ví dụ Văn phạm không nhập nhằng: Văn phạm nhập nhằng: E→E+T E→E+E →T →E×E T→T×F → (E) →F →a F → (E) →a 12
Ngôn ngữ chính quy và CFG Định lý 1 Mọi ngôn ngữ chính quy đều là phi ngữ cảnh Chứng minh Ý TƯỞNG: Cho một DFA, xây dựng một văn phạm có thể tạo ra cùng 1 ngôn ngữ với DFA • Chuyển các trạng thái thành các biến • Chuyển trạng thái bắt đầu thành biến bắt đầu • Chuyển các cạnh thành các quy tắc • Thêm 1 quy tắc ε cho mỗi trạng thái kết thúc 13
Ví dụ 2 A → 1B B A → 3C 1 3 B → 2B B → 3D start A D 4 C → 1D 3 1 D → 4D C D→ε 14
Tập hợp ngôn ngữ 15
Dạng chuẩn tắc Chomsky