ducvinh_tbvn
New Member
Chia sẻ miễn phí cho các bạn tài liệu: Viết chương trình thực hiện giao của 2 DFA và hiệu 2 DFA
2
Phần I: Giới thiệu về môn học Automat và DFA
1.1.Giới thiệu về Automat
Vào những năm 1930 Alain Turing đã nghiên cứu các máy trừu tượng có
khả năng thực hiện các tính toán như máy tính ngày nay.Các máy trừu tượng
gọi là máy turing.Vào những năm 1940 – 1950 các máy trừu tượng đơn giản
hơn mà chúng ta gọi là otomat hữu hạn đã được nghiên cứu bởi các nhà
khoa học.
Otomat là mô hình hữu ích cho nhiều phần mềm quan trọng :
Phần mềm thiết kế và kiểm tra các mạch điện tử số
Bộ phân tích từ vựng của 1 CT dịch
Dịch từ ngôn ngữ bậc cao sang ngôn ngữ bậc thấp
Dịch từ ngôn ngữ này sang ngôn ngữ khác
Tìm kiếm trong văn bản
1.2. Automat hữu hạn đơn định - DFA (Deterministic Finite Automata)
Một ôtômát hữu hạn đơn định (DFA) - gọi tắt là FA -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à q
0
, 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 3.1. Trạng thái khởi đầu q
0
được chỉ bằng mũi tên có nhãn "Start". Chỉ có duy nhất một
Một ôtômát hữu hạn đơn định (DFA) - gọi tắt là FA -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
Dành riêng cho anh em Ketnooi, bác nào cần download miễn phí bản đầy đủ thì trả lời topic này, Nhóm Mods sẽ gửi tài liệu cho bạn qua hòm tin nhắn nhé.
- Bạn nào có tài liệu gì hay thì up lên đây chia sẻ cùng anh em.
- Ai cần tài liệu gì mà không tìm thấy ở forum, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
2
Phần I: Giới thiệu về môn học Automat và DFA
1.1.Giới thiệu về Automat
Vào những năm 1930 Alain Turing đã nghiên cứu các máy trừu tượng có
khả năng thực hiện các tính toán như máy tính ngày nay.Các máy trừu tượng
gọi là máy turing.Vào những năm 1940 – 1950 các máy trừu tượng đơn giản
hơn mà chúng ta gọi là otomat hữu hạn đã được nghiên cứu bởi các nhà
khoa học.
Otomat là mô hình hữu ích cho nhiều phần mềm quan trọng :
Phần mềm thiết kế và kiểm tra các mạch điện tử số
Bộ phân tích từ vựng của 1 CT dịch
Dịch từ ngôn ngữ bậc cao sang ngôn ngữ bậc thấp
Dịch từ ngôn ngữ này sang ngôn ngữ khác
Tìm kiếm trong văn bản
1.2. Automat hữu hạn đơn định - DFA (Deterministic Finite Automata)
Một ôtômát hữu hạn đơn định (DFA) - gọi tắt là FA -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à q
0
, 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 3.1. Trạng thái khởi đầu q
0
được chỉ bằng mũi tên có nhãn "Start". Chỉ có duy nhất một
Một ôtômát hữu hạn đơn định (DFA) - gọi tắt là FA -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
Dành riêng cho anh em Ketnooi, bác nào cần download miễn phí bản đầy đủ thì trả lời topic này, Nhóm Mods sẽ gửi tài liệu cho bạn qua hòm tin nhắn nhé.
- Bạn nào có tài liệu gì hay thì up lên đây chia sẻ cùng anh em.
- Ai cần tài liệu gì mà không tìm thấy ở forum, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
