Chủ đề:Lý thuyết tự động

Tủ sách mở Wikibooks

< Khoa học máy tính

Lý thuyết tự động
Các sách trong chủ đề này bàn về lý thuyết máy tự động: việc nghiên cứu các máy trừu tượng và những vấn đề mà chúng có thể giải. Một máy tự động (automaton) là một mô hình toán học cho một máy có trạng thái hữu hạn (FSM). FSM là một máy, mà khi nhận được một số ký tự, sẽ 'nhảy', hoặc chuyển tiếp (transition), qua một chuỗi các trạng thái theo các hàm chuyển tiếp (transition function). Trong các FSM thông dụng, các hàm này báo cho automaton biết nó sẽ đi lên trạng thái nào dựa theo trạng thái và ký tự hiện tại. Tuy nhiên, nói chung, automaton không cần phải có một số lượng hữu hạn các trạng thái, hoặc thậm chí không cần có một số lượng có thể đếm được các trạng thái. Automaton không nhiết thiết phải rõ ràng chấp nhận hoặc không chấp nhận một đầu vào; nó có thể chọn chấp nhận đầu vào đó với xác suất vào khoảng giữa 0 và 1. Lý thuyết máy tự động có vai trò lớn trong thiết kế compiler và parsing.