HỌC VIỆN KỸ THUẬT QUÂN SỰ KHOA CÔNG NGHỆ THÔNG TIN ========== BÀI TẬP LỚN: AUTOMAT VÀ NGÔN NGỮ HÌNH THỨC ĐỀ TÀI: GIAO VÀ HIỆU CỦA 2 DFA Nhóm thực hiện đề tài: Đơn vị : Lớp Tin học 44 Giáo viên hướng dẫn: Hà Nội : 07/2011 1 MỤC LỤC ĐẶT VẤN ĐỀ Lý thuyết ngôn ngữ hình thức và automata đóng một vai trò rất quan trọng trong các cơ sở toán học của tin học. Ngôn ngữ hình thức được sử dụng trong việc xây dựng các ngôn ngữ lập trình, lý thuyết về các chương trình dịch. Các ngôn ngữ hình thức tạo thành một công cụ mô tả đối với các mô hình tính toán cả cho dạng thông tin vào-ra lẫn kiểu thao tác. Lý thuyết ngôn ngữ hình thức, chính vì thực chất của nó là một lĩnh vực khoa học liên ngành; nhu cầu mô tả hình thức văn phạm được phát sinh trong nhiều ngành khoa học khác nhau từ ngôn ngữ học đến sinh vật học. Như chúng ta đã biết, ngôn ngữ hình thức và chương trình dịch là những bộ môn phát triển sớm nhất so với các ngành khác trong khoa học máy tính, khối lượng kiến thức trong các bộ môn này rất đồ sộ. Ở nước ta hiện nay, đã có nhiều trường đại học cũng đã bắt đầu giảng dạy môn học này cho các sinh viên ngành Công nghệ thông tin. Để hiểu rõ hơn về ngôn ngữ hình thức và automata, trong nội dung bài tập lớn này, chúng em xin trình bày vấn đề về: hiệu và giao của hai DFA. Chúng em chia đề tài ra làm 3 phần chính : 1. Tìm hiểu về DFA 2. Tìm hiểu về giao và hiệu của 2 DFA 3. Chương trình minh họa. Trong suốt quá trình làm, với sự cố gắng của từng thành viên trong nhóm cùng với các ý kiến đóng góp của bạn bè, sự hướng dẫn của thầy giáo và tham khảo các tài liệu khác, chúng em đã hoàn thành được nội dung đề ra. Tuy nhiên, do kỹ năng và kiến thức còn có hạn nên nội dung chương trình không thể tránh 2 khỏi những sai sót. Chúng em hy vọng sẽ nhận được nhiều những sự đóng góp từ phía thầy và bạn bè để chương trình này được hoàn thiện hơn! Chúng em xin chân thành cảm ơn! PHẦN 1: AUTOMAT HỮU HẠN ĐƠN ĐỊNH DFA 1. Giới thiệu Một ôtômát hữu hạn đơn định (DFA) gồm một tập hữu hạn các trạng thái và một tập các phép chuyển từ trạng thái này tới trạng thái khác trên các ký hiệu nhập (input symbols) được chọn từ một bộ chữ cái Σ nào đó. Mỗi ký hiệu nhập có đúng một phép chuyển khỏi mỗi trạng thái (có thể chuyển trở về chính nó). Một trạng thái, thường ký hiệu là q0, gọi là trạng thái bắt đầu (trạng thái ôtômát bắt đầu). Một số trạng thái được thiết kế như là các trạng thái kết thúc hay trạng thái chấp nhận. Một đồ thị có hướng, gọi là sơ đồ chuyển (transition diagram) tương ứng với một DFA như sau: các đỉnh của đồ thị là các trạng thái của DFA; nếu có một đường chuyển từ trạng thái q đến trạng thái p trên input a thì có một cung nhãn a chuyển từ trạng thái q đến trạng thái p trong sơ đồ chuyển. DFA chấp nhận một chuỗi x nếu như tồn tại dãy các phép chuyển tương ứng trên mỗi ký hiệu của x dẫn từ trạng thái bắt đầu đến một trong những trạng thái kết thúc. Chẳng hạn, sơ đồ chuyển của một DFA được mô tả trong hình 1. Trạng thái khởi đầu q0 được chỉ bằng mũi tên có nhãn "Start". Chỉ có duy nhất một trạng thái kết thúc, cũng là q0 trong trường hợp này, được chỉ ra bằng hai vòng tròn. Ôtômát này chấp nhận tất cả các chuỗi số 0 và số 1 với số số 0 và số số 1 là số chẵn. 3