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: