DFA là gì?

DFA đề cập đến ôtômát hữu hạn đơn định (deterministic finite automata). Đơn định (deterministic) đề cập đến tính duy nhất của phép tính. Trong DFA, máy (machine) chỉ chuyển sang một trạng thái cho một ký tự đầu vào (input) cụ thể. Trong DFA, chỉ có một đường dẫn cho đầu vào cụ thể từ trạng thái (state ) hiện tại sang trạng thái tiếp theo. DFA không chấp nhận di chuyển rỗng (null move), tức là DFA không thể thay đổi trạng thái mà không có bất kỳ ký tự đầu vào (input) nào. DFA có thể chứa nhiều trạng thái kết thúc (final state)..

DFA là một tập hợp 5 bộ (tuple) giống như NFA: Q: tập hợp hữu hạn các trạng thái (state), ∑: tập hợp hữu hạn của ký hiệu (symbol) đầu vào (input), q0: trạng thái bắt đầu (initial state), F: trạng thái kết thúc (final state), δ: hàm chuyển (transition function). Trong đó hàm chuyển có thể được định nghĩa là: δ: Q x ∑ → Q.