tailieunhanh - Bài giảng môn lý thuyết ôtômát và ngôn ngữ hình thức - Chương 5

Tham khảo bài thuyết trình 'bài giảng môn lý thuyết ôtômát và ngôn ngữ hình thức - chương 5', kỹ thuật - công nghệ, điện - điện tử phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Chương 5 Ngôn ngữ phi ngữ cảnh Văn phạm phi ngữ cảnh Phân tích cú pháp và tính nhập nhằng Văn phạm phi ngữ cảnh và ngôn ngữ lập trình Trang 157 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 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 e Vcòn x e VuT . 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 158 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 V 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 IW w e 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. Trang 159 Lý thuyết Ôtômát NNHT - Khoa Công Nghệ Thông .