Bài giảng Ngôn ngữ hình thức: Chương 5 Máy turing và ôtômát tuyến tính giới nội, cung cấp cho người học những kiến thức như: Ngôn ngữ cảm ngữ cảnh; Ô tô mát tuyến tính giới nội; Sự tương đương giữa ô tô mát tuyến tính giới nội và văn phạm cảm ngữ cảnh. Mời các bạn cùng tham khảo! | MÁY TURING VÀ Ô TÔ MÁT TUYẾN TÍNH GIỚI NỘI Nội dung Máy turing tiền định Ngôn ngữ ngữ cấu đệ quy kể được Ô tô mát tuyến tính giới nội Văn phạm cảm ngữ cảnh Máy turing tiền định Cấu tạo Bộ chữ gồm bộ chữ vào dùng cho xâu vào và kí hiệu trống B Một hoặc một số băng chia thành nhiều ô có đánh số thứ tự vô hạn về một phía hoặc hai phía. Mỗi ô trên băng có thể chứa được một kí hiệu thuộc bộ chữ Một đầu đọc di chuyển trên băng mỗi thời điểm trỏ đến một ô trên băng Một tập hữu hạn các trạng thái trong đó có trạng thái đầu và trạng thái thừa nhận Cấu tạo Một hàm dịch chuyển với mỗi trạng thái hiện tại và kí hiệu đầu đọc đọc được Trạng thái tiếp theo Một kí hiệu mới đè lên kí hiệu vừa đọc được Hướng dịch chuyển của đầu đọc Cấu tạo máy Turing Mô hình máy Turing Máy turing tiền định Nguyên lý hoạt động Ban đầu Xâu được đặt trên băng bắt đầu từ ô đầu tiên mỗi ô một kí hiệu các ô khác chứa kí hiệu trắng Đầu đọc trỏ vào ô đầu tiên trên băng Trạng thái bắt đầu q 0 Nguyên lý hoạt động Hàm dịch chuyển căn cứ vào trạng thái hiện tại và kí hiệu đọc được trên băng để xác định Trạng thái tiếp theo Một kí hiệu được viết lên băng đè lên kí hiệu vừa đọc Hướng dịch chuyển của đầu đọc dịch sang trái hay sang phải một ô Xâu vào được thừa nhận khi quá trình thực hiện đối với xâu đạt đến một trạng thái thưà nhận Định nghĩa máy Turing Định nghĩa Một máy Turing là một bộ 7 M Q q0 B F trong đó Q tập hữu hạn các trạng thái Σ bộ ký hiệu nhập Γ tập hữu hạn các ký hiệu được viết trên băng δ hàm chuyển Q x Γ Q x Γ x L R Ø q0 trạng thái khởi đầu B ký hiệu dùng để chỉ khoảng trống trên băng F Q tập các trạng thái kết thúc Định nghĩa máy Turing Một hình trạng của một máy Turing 1q 2 trong đó được gọi là kí hiệu mút q là trạng thái hiện tại Nội dung trên băng 1 và 2 Định nghĩa máy Turing Sự thực hiện của máy turing 2 trường hợp Sự thực hiện đến một hình trạng không thể đi tiếp. Máy turing cho câu trả lời có xâu w được thừa nhận nếu trạng thái hiện thời là trạng thái thừa nhân ngược lại thì câu trả lời là
