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ọngtrong các cơ sở toán học của tin học. Ngôn ngữ hình thức được sử dụng trongviệ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ácngô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áncả 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ênngà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ậplớn này, chúng em xin trình bày vấn đề về: hiệu và giao của hai DFA. Chúng emchia đề tài ra làm 3 phần chính : 1.Tìm hiểu về DFA2.Tìm hiểu về giao và hiệu của 2 DFA3.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ómcù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à thamkhả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óptừ 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 ĐỊNHDFA
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áivà 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ệunhập [input symbols] được chọn từ một bộ chữ cái Σ nào đó. Mỗi ký hiệu nhậpcó đú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ạngthái chấp nhận. Một đồ thị có hướng, gọi là sơ đồ chuyển [transition diagram] tương ứngvớ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 achuyển từ trạng thái q đến trạng thái p trong sơ đồ chuyển. DFA chấp nhận mộtchuỗ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 xdẫ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ạngthái khởi đầu q0 được chỉ bằng mũi tên có nhãn "Start". Chỉ có duy nhất mộttrạ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òngtrò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