cơ chế otomat

Định nghĩa ôtômát

Ngoài các văn phạm, người ta còn sử dụng một phương tiện khác để xác định ngôn ngữ là ôtômát. Ôtômát, dịch nghĩa là máy tự động, được hiểu là các “máy” trừu tượng có cơ cấu và hoạt động rất đơn giản nhưng có khả năng đoán nhận ngôn ngữ. Với một chuỗi bất kỳ, sau một số bước làm việc, ôtômát sẽ cho câu trả lời chuỗi đó có thuộc ngôn ngữ hay không. Để có được quá trình tự động như vậy, con người thường phải lập trình sẵn cho nó một “lộ trình” thực hiện, và các máy chỉ cần hoạt động theo đúng lộ trình này. Một trong số những máy tự động này điển hình mạnh nhất có thể nói chính là máy tính số ngày nay. Tuy hoạt động theo kiểu “máy”, song thực chất mỗi bước làm việc của ôtômát là một sự thay thế ký hiệu, nghĩa là một bước dẫn xuất như đã nói ở trên.

Nói chung, một mô hình ôtômát thường bao gồm những thành phần chủ yếu như sau :

Hình 2.1 - Mô hình chung cho một ôtômát

Chuỗi nhập cần xác định sẽ được lưu trữ trên băng input. Tại mỗi thời điểm, ứng với trạng thái hiện thời, đọc vào một ký tự nhập trên băng input, có thể kết hợp với việc xem xét ký hiệu tương ứng trong Bộ nhớ, Bộ điều khiển của ôtômát sẽ quyết định bước chuyển đến trạng thái kế tiếp.

Các loại ôtômát tương ứng với từng lớp văn phạm sẽ được giới thiệu lần lượt trong những chương tiếp theo.

Phân loại các ôtômát

Dựa theo hoạt động của ôtômát, thông thường người ta chia ôtômát thành hai dạng sau:

Ôtômát đơn định (Deterministic Automata) : Là một ôtômát mà tại mỗi bước di chuyển chỉ được xác định duy nhất bởi cấu hình hiện tại. Sự duy nhất này thể hiện tính đơn định, nghĩa là hàm chuyển của ôtômát dạng này luôn là đơn trị.

Ôtômát không đơn định (Non - deterministic Automata) : Là một ôtômát mà tại mỗi bước di chuyển, nó có một vài khả năng để chọn lựa. Sự chọn lựa này thể hiện tính không đơn định, nghĩa là hàm chuyển của ôtômát dạng này là đa trị.