NFA là gì?

NFA là viết tắt của non-deterministic finite automata nghĩa là ôtômát hữu hạn không đơn định.Trong NFA máy (machine) có thể là nhiều trạng thái tiếp theo cho mỗi ký hiệu (symbol) đầu vào cụ thể. Nó có thể chấp nhận di chuyển null (null move).

NFA là một tập hợp 5 bộ (tuple) giống như DFA: 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 ∑ →2^Q.