ÔTÔMÁT TUYẾN TÍNH GIỚI NỘI VÀ VĂN PHẠM CẢM NGỮ CẢNH Nội dung chính : Trong chương này, chúng ta xét thêm một loại ôtômát, không mạnh bằng máy Turing, được gọi là ôtômát tuyến tính giới nội (Linear Bounded Automata – LBA). Đồng thời cũng xét thêm lớp văn phạm tương ứng với nó, là lớp văn phạm L1 hay còn gọi là văn phạm cảm ngữ cảnh, lớp văn phạm nằm giữa lớp văn phạm L0 và văn phạm phi ngữ cảnh L2. Từ đó ta hoàn thành sự phân cấp các ngôn ngữ thành 4 cấp, gọi. | Chương VIII ổtômát tuyến tính giới nội và văn phạm cảm ngữ cảnh Chương VIII ÔTÔMÁT TUYẾN TÍNH GIỚI NỘI VÀ VĂN PHẠM CẢM NGỮ CẢNH Nội dung chính Trong chương này chúng ta xét thêm một loại ôtômát không mạnh bằng máy Turing được gọi là ôtômát tuyến tính giới nội Linear Bounded Automata - LBA . Đồng thời cũng xét thêm lớp văn phạm tương ứng với nó là lớp văn phạm L1 hay còn gọi là văn phạm cảm ngữ cảnh lớp văn phạm nằm giữa lớp văn phạm L0 và văn phạm phi ngữ cảnh L2. Từ đó ta hoàn thành sự phân cấp các ngôn ngữ thành 4 cấp gọi là sự phân cấp Chomsky. Mục tiêu cần đạt Cuối chương sinh viên cần phải nắm vững Khái niệm LBA định nghĩa và các thành phần. Sự tương đương giữa LBA và văn phạm cảm ngữ cảnh. Mối tương quan giữa các lớp ngôn ngữ. Kiến thức cơ bản Để tiếp thu tốt nội dung của chương này sinh viên cần hiểu rõ các dạng ôtômát đã được giới thiệu trong các chương trước đặc biệt là mô hình máy Turing nắm vững cơ cấu các lớp văn phạm. Tài liệu tham khảo 1 Nguyễn Văn Ba - Giáo trình ngôn ngữ hình thức - Trường Đại học Bách khoa Hà nội - 1994. 2 A. C. Fleck - Context Sensitive Languages http fleck PartIIIxpar 3 Linear Bounder Automata http lewis texts theory automata I. ÔTÔMÁT TUYẾN TÍNH GIỚI NỘI LBA 133 Chương VIII ổtômát tuyến tính giới nội và văn phạm cảm ngữ cảnh Ta gọi Ôtômát tuyến tính giới nội Linear Bounded Automata - LBA là một máy Turing không đơn định và không có khả năng nới rộng vùng làm việc ra khỏi mút trái và mút phải của chuỗi nhập. Nó phải thỏa hai điều kiện sau 1 Bộ chữ cái nhập của nó có chứa thêm hai ký hiệu đặc biệt ợ và dùng làm ký hiệu đánh dấu mút trái và mút phải. 2 LBA không thực hiện phép chuyển sang trái L từ ợ và không thực hiện phép chuyển sang phải R từ và cũng không viết các ký hiệu khác lên ợ và . LBA đơn giản là một máy Turing nhưng thay vì sử dụng một băng không giới hạn cho việc tính toán nó bị hạn chế chỉ trong phạm vi băng chứa chuỗi nhập x với hai ô chứa các ký hiệu đánh dấu cận đầu mút.
