Máy trạng thái hữu hạn – đèn giao thông, DFA, NFA và ngôn ngữ chính quy

Thuộc chủ đề Giải quyết vấn đề với sự trợ giúp của máy tính (Tin học 10), gắn với mô hình hoá bằng máy trạng thái hữu hạn. Một máy trạng thái có một tập hữu hạn trạng thái, một trạng thái bắt đầu và các chuyển tiếp «trạng thái + ký hiệu → trạng thái mới»; máy Mealy sinh đầu ra trên chuyển tiếp, máy Moore gắn đầu ra với trạng thái. Ôtômat đoán nhận (DFA, NFA) dùng cùng ý tưởng để quyết định một từ có thuộc một ngôn ngữ chính quy hay không. Học sinh chọn đèn giao thông, máy bán nước hoặc cửa quay, rồi bấm Bước tiếp hoặc Chạy để đưa từng sự kiện vào máy và xem trạng thái, đầu ra, bảng theo dõi cùng hình minh hoạ hệ thống thật; phần Sửa máy cho thêm, kéo và nối trạng thái. Ở chế độ Ôtômat đoán nhận, học sinh nhập từ để kiểm tra DFA chia hết cho 3 hoặc NFA kết thúc bằng ab, xem bảng chuyển trạng thái, biểu thức chính quy, ngữ pháp chính quy, liệt kê các từ được chấp nhận và đổi NFA thành DFA. Câu hỏi gợi ý: – Ở mô hình đèn giao thông, chi tiết nào của cột đèn thật đã bị bỏ đi, và vì sao bỏ đi vẫn chấp nhận được? – Từ 110 có được ôtômat chia hết cho 3 chấp nhận không? Hãy lần theo từng trạng thái. – Vì sao NFA nhận từ kết thúc bằng ab có ít chuyển tiếp hơn DFA tương đương nhưng vẫn nhận đúng cùng các từ?