TAILIEUCHUNG - Giáo trình Toán rời rạc: Phần 2 - Đỗ Đức Giáo

Phần 2 giáo trình "Toán rời rạc" sau đây gồm nội dung các chương: Chương 6 - Ôtômat hữu hạn đoán nhận ngôn ngữ chính quy, chương 7 - Ôtômat đẩy xuống đoán nhận ngôn ngữ phi ngữ cảnh, chương 8 - Lôgic toán, chương 9 - Đại số boole. nội dung chi tiết. | Chương 6 ÔTÔMAI Hữu HẠN DOÀN NHẬN BIỂU THỨC CHÍNH QUY 1. ÕTÕMAT HỮU HẠN FINITE AUTOMATA - FA Otômat hữu hạn có thê xem như máy trừu tượng để đoàn nhận ngôn ngử. Chúng ta sẽ thấy rằng lớp ngôn ngữ dược đoản nhận bởi ôtômat hữu hạn là khá đơn giàn đó chính là lốp ngôn ngủ chính quỵ do các vàn phạm chính quy sình ra. . DỊnh nghĩa ôtômat hữu hạn in ỉ nghĩa ĩ Ôlómat hữu hạn lã bộ M - E. Q. 6. q. F . trong đó - là tập hợp hữu bạn khác rỗng các ký hiệu vào. Q- là tập hợp hữu hạn khác rông các trạng thái. q. ẽ Q được gọi là trạng thái ban đau. FcQ được gọi là tập các trạng thãi kết thúc S- dược gọi lã hàm chuyên có dạng 1. Nếu hàm chuyển là ánh xạ ỗ Q X I - Q. khi đó M được gọi là ôtômat đơn định Deterministic Finite Automata viết tắt là DFA . 240 2. Nếu hàm chuyển là ánh xạ ố Q X E 2Q khi đó M được gọi là õtõmat không đơn định Nondeterministic Finite Automata viết tắt NDFA . Ta cỏ thể mô tả các bước làm việc cùa ôtômat hữu hạn M - z. Q. 5. q. F khi cho xảu vào tì X x2 x . x e I như sau Xâu vào tì X x2 . x I xn T qc - . Kln bắt đầu làm việc máy ờ trạng thái đầu q i và đầu đọc đang nhìn vào ô có ký hiệu X Tiẽp theo máy chuyển từ trạng thái q dưới tác động của ký hiệu vào X về trạng thái mối S q .X q e Q và đầu đọc chuyển sang phải 1 ô. tức nhìn vào ô có ký hiệu Xọ. Sau đó ôtômat M lại tiếp tục chuyển từ trạng thai q nhờ hàm chuyển s vể trạng thái mới q - S q . Xí 5 5 q. X . Xz S q. X X2 6 Q. Quá trình đó sẽ tiếp tục cho tới khi đầu đọc nhìn vào ký hiệu x với trạng thái cùa ináy là q I 5 q X X2. X i . Hàm chuyển lại đưa máy từ trạng thái qn I dưỏi tác động cùa X về trạng thái q - õ q . x 1 ô q X X2. X J e Q. Khi đó ôtômat dừng lại. Nếu q 6 F thì ta nói rằng ôtômat đã đoản nhận xâu c . Trong trường hợp ngược lại thì nói rãng ôtôrnat không đoản nhận xâu o. Tập L M tì 0 e E mà ỗ q . tì e F được gọi là ngón ngữ được đoán nhận bởi ôtômat M. Tập trạng thái Q trong quả trình tính toán được coi như là bộ nhớ cùa một ôtômat. Vì Q là hữu hạn nên M được gọi là ôtômat hữu hạn. 241 .

• Toán học
• Toán rời rạc
• Phương pháp quy nạp
• Ôtômat hữu hạn
• Ngôn ngữ chính quy
• Ngôn ngữ phi ngữ cảnh
• Đại số boole
• Bài giảng toán rời rạc
• Giáo trình toán rời rạc
• Tài liệu toán rời rạc
• Học toán rời rạc
• Lý thuyết về toán rời rạc
• Bài tập về toán rời rạc
• Ôn tập toán rời rạc
• Đề thi toán rời rạc