- Ngôn ngữ không phi ngữ cảnh. - PDA: Là một mô hình tính toán, giống với NFA ngoại trừ một thành phần mở rộng được gọi là ngăn xếp. - Ngăn xếp: Là một cấu trúc dữ liệu hoạt động theo cơ chế LIFO. - PDA ⇔ CFG về sức mạnh → Thêm công cụ hữu ích khi đoán nhận một ngôn ngữ phi ngữ cảnh. - a là ký tự vào. - b là ký tự nằm ở đỉnh ngăn xếp, ký tự này sẽ được lấy ra (pop). - c là ký tự được đẩy (push) vào trong ngăn xếp. - a,b,c đều có thể nhận ký tự ε. - Nếu b = ε→ ngăn xếp đang rỗng hoặc chưa được đọc - Nếu c = ε→ không có gì được đẩy vào ngăn xếp. - Xét ngôn ngữ A = {0 n 1 n | n ≥ 0}. - Bộ chữ ngăn xếp. - Ký tự $ dùng để xác định đáy của ngăn xếp. - Tồn tại 1 đường đi từ trạng thái bắt đầu đến trạng thái chấp thuận trong bộ điều khiển trạng thái. - Đến cuối xâu sẽ đọc hết các ký tự và không còn ký tự nào trong ngăn xếp. - Lấy b từ ngăn xếp ra. - Không lấy gì từ ngăn xếp ra. - Q: Tập trạng thái (hữu hạn). - Σ ε : Bộ chữ đầu vào, tập hữu hạn các ký tự - Γ: Bộ chữ của ngăn xếp, tập hữu hạn các ký tự - δ: Hàm dịch chuyển. - q 0 : Trạng thái bắt đầu (q 0 ∈ Q). - F: Là tập các trạng thái kết thúc (F ⊆ Q). - Nhắc lại: Một ngôn ngữ phi ngữ cảnh là ngôn ngữ được biểu diễn bởi một CFG nào đó. - Một ngôn ngữ là phi ngữ cảnh nếu và chỉ nếu có một PDA nào đó đoán nhận nó. - Ta phát biểu nó thành từng bổ đề sau. - Bổ đề 1.1. - Nếu một ngôn ngữ là phi ngữ cảnh, thì tồn tại một PDA đoán nhận nó. - Bổ đề 1.2. - Nếu một PDA đoán nhận một ngôn ngữ nào đó, thì ngôn ngữ đó là phi ngữ cảnh. - Chứng minh bổ đề 1.1. - Ý TƯỞNG: Xây dựng PDA P = (Q,Σ, Γ, δ, q 0 , F) đoán nhận cùng ngôn ngữ với CFG. - Quy tắc xây dựng. - Đặt ký hiệu đánh dấu $ và biến ban đầu vào trong ngăn xếp 2. - a Nếu đỉnh của ngăn xếp là 1 ký hiệu biến A → Chọn một quy tắc ứng với A và thay thế bởi phần bên phải của quy tắc đó b Nếu đỉnh của ngăn xếp là 1 ký hiệu kết thúc a → Đọc ký hiệu. - c Nếu đỉnh của ngăn xếp là ký hiệu. - chuyển vào trạng thái chấp thuận. - Chú ý: Để đưa nhiều ký hiệu vào ngăn xếp ta cần thêm 1 số bước trung gian. - Biểu đồ trạng thái. - Biểu đồ trạng thái của PDA P sẽ có dạng sau:. - Chứng minh bổ đề 1.2. - Có duy nhất 1 trạng thái chấp thuận q accept. - Nó làm rỗng ngăn xếp trước khi chấp thuận. - Không thực hiện push và pop các ký hiệu vào ngăn xếp cùng 1 lúc. - PDA có duy nhất 1 trạng thái chấp thuận q accept. - Quy tắc xây dựng CFG. - Mọi ngôn ngữ phi ngữ cảnh đều có 1 giá trị đặc biệt được gọi là độ dài dẫn xuất. - Có một cách chứng minh ngôn ngữ không phi ngữ cảnh tương tự ngôn ngữ không phi ngữ cảnh. - Bổ đề Bơm. - Bổ đề Bơm (Pumping Lemma) cho ngôn ngữ phi ngữ cảnh Nếu A là một ngôn ngữ phi ngữ cảnh, thì tồn tại một số p sao cho nếu s là một xâu bất kỳ thuộc A có độ dài ít nhất là p, thì s có thể được chia ra làm 5 phần s=uvxyz thỏa mãn các điều kiện sau:. - Sử dụng bổ đề Bơm để chứng minh một ngôn ngữ A là không phi ngữ cảnh. - Giả sử A là phi ngữ cảnh. - của bổ đề Bơm. - Mâu thuẫn, do đó kết luận A không phải là phi ngữ cảnh. - Sử dụng bổ đề Bơm để chứng tỏ rằng B = {a n b n c n |n ≥ 0} là không phi ngữ cảnh. - Giả sử B là ngôn ngữ phi ngữ cảnh (CFL. - Xét các trường hợp có thể chia s thành 5 đoạn uvxyz - v và y chỉ chứa 1 loại ký tự. - v và y chứa nhiều ký tự. - Có các mâu thuẫn nên giả thiết là sai → B là ngôn ngữ không phi ngữ cảnh
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt