Tham khảo sách 'ngôn ngữ hình thức và ôtômat - chương 4', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Ngôn ngữ hình thức và Ôtômat Formal Language Automata . Phan Huy Khánh khanhph@ Chương 4 Ôtômat đẩy xuống 3 Chương 4 Ôtômat đẩy xuống Ôtômat đẩy xuống o Ngôn ngữ phi ngữ cảnh o Quan hệ với các ôtômat đẩy xuống o Tính chất của các ngôn ngữ phi ngữ cảnh Khái niệm về cây phân tích o Định lý bơm và ứng dụng o Các thuật giải cho các ngôn ngữ PNC Ôtômat đẩy xuống đơn định o Nguyên lý o Hình thức hóa o Các ngôn ngữ PNC đơn định o Tính chất của các ngôn ngữ PNC đơn định 2 65 Mô tả ôtômat đẩy xuống ôđx Một ôđx không đơn định NSA Non-deterministic Stack Automaton hay NPA Non-deterministic Pushdown Automaton có một số phần tử tương tự ôhh o Một băng vào chứa câu sẽ được đoán nhận ở mút trái nhất o Một đầu đọc đọc lần lượt các ký tự của câu trên băng o Một tập hợp các trạng thái trong đó có một trạng thái đầu và một số trạng thái cuôi trạng thai đạt được o Một quan hệ chuyển tiếp làm thay đổi trạng thái với mỗi ký tự đọc được rên băng Ngoài ra NSA còn có o Một danh sách đẩy xuống Stack Pushdown List DSĐX có thể chứa không hạn che các ký tự nào đó ơ Một đầu ghi để có thể ghi lên DSĐX Hoạt động của ôđx Hoạt động đoán nhận Ôđx không đơn định như sau o Tương tự một ôhh không đđ câu vào weZ được đặt ở mút trái trên băng vào o Lúc đầu đầu đọc ở vị trí w 1 DSĐX rỗng và ôđx đang ở trạng thái đầu q0 o Đầu đọc đọc lần lượt từng ký tự của w trên băng o Ôđx nhìn một phần câu trên đỉnh DSĐX Top để thay thế Pop-Push bằng cách ghi đè lên một dãy ký tự o Ôđx di chuyển đầu đọc qua phải và thay đổi trạng thái o Ôhh dừng khi mọi ký tự của w đã được đọc hết và thừa nhận câu hoặc hóc giữa chừng 3 65 4 65 Minh hoạ hoạt động của ôđx Câu vào trên băng w anbn Sau trên đĩnh DSĐX là p Trước trên đĩnh DSĐX là a 5 65 Định nghĩa hình thức ôđx Một NSA là một bộ 7 M Q z r A Z q0 A trong đó o Q là tập hợp hữu hạn các trạng thái o z là bảng chữ vào hữu hạn Input Alphabet o r là bộ chữ đẩy xuống hữu hạn Stack Alphabet ơ Z e r là ký tự đầu của DSĐX Initial Stack Symbol o q0 e Q là trạng thái đầu ơ F
