Luận văn Quản lý dự án phần mềm trên Web

Automat hữu hạn là một cái máy đoán nhận xâu. Nó bao gồm các bộ phận sau: - Một băng vào được chia thành ô, dùng để ghi xâu vào, mỗi kí hiệu của xâu vào thuộc bảng chữ Σ được ghi trên một ô - Một đầu đọc, mỗi thời điểm đọc (trỏ) đến một ô trên băng vào - Một bộ điều khiển Q, gồm một số hữu hạn các trạng thái, tại mỗi thời điểm nó có một trạng thái Hoạt động của Automat được thực hiện như sau: Automat hoạt động theo từng bước. Mỗi bước như sau: tùy theo trạng thái hiện thời của bộ điều khiển và kí hiệu mà đầu đọc đang đọc, mà Automat chuyển sang một trạng thái mới, đồng thời đầu đọc dịch chuyển sang phải một ô. Quy luật chuyển trạng thái của Automat hữu hạn đơn định được mô tả bởi một hàm, được gọi là hàm dich chuyển như sau: Trong Q, có một trạng thái đầu, thường kí hiệu qo và một tập hợp các trạng thái cuối / thừa nhận, thường kí hiệu F (F  Q). Ta nói Automat thừa nhận xâu vào w nếu sau khi xuất phát từ trạng thái đầu qo và đầu đọc chỉ vào kí hiệu bên trái nhất của xâu w, sau một số bước dịch chuyển hữu hạn, Automat đọc song xâu w và rơi vào một trong các trạng thái cuối thuộc F. Tập hợp tất cả các xâu đoán nhận bởi Automat hợp thành ngôn ngữ được nhận bởi Automat đó.