Chia sẻ miễn phí cho các bạn tài liệu:
Ngày nay, các ngôn ngữ là một phần không thể thiếu trong công việc của mối người làm tin học. Để có thể hiểu sâu sắc về các ngôn ngữ lập trình ( giải thuật và cú pháp ) thì không thể không ngiên cứu về các ngôn ngữ hình thức, về các văn phạm và các Automat. Cũng chính vì vậy Ngôn Ngữ Hình Thức được đưa vào làm môn học cho tất cả các sinh viên công nghệ thông tin.
Trong đề tài này, chúng em xin trình bày về Automat hữu hạn đơn định tối thiểu.
Với mục đích nghiên cứu, tìm hiểu, bài tập lớn còn có nhiều thiếu sót, cũng như nhiều phần còn chưa được đề cập đầy đủ. Vì vậy, nhóm chúng em rất mong được sự góp ý của thầy giáo.
Trong bài tập này của chúng em gồm có các phần sau:
• Khái niệm DFA
• Cách xác định các trạng thái tương đương
• Xây dựng DFA tối thiểu từ DFA ban đầu
• Xây dựng thuật giải tối thiểu hóa DFA
CHƯƠNG I – AUTOMAT HỮU HẠN ĐƠN ĐỊNH
1.1. Khái Niệm
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 đầu vào. Mỗi ký hiệu nhập được chọn từ một bộ chữ cái, 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 automat 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 Automat hữu hạn đơn định M được biểu diễn như sau:
M = (Q, ∑, δ, q0, F).
Trong đó:
Q là tập hữu hạn các trạng thái
∑ là tập hữu hạn các kí tự đầu vào gọi là bảng ký tự
q0 € Q là trạng thái bắt đầu
F là tập hợp con của Q gọi là tập trạng thái kết thúc (trạng thái đoán nhận).
δ là hàm chuyển đổi trạng thái: Q x ∑ → Q.
Một automat hữu hạn là một máy đoán nhận xâu. Gồm có 3 bộ phận:
• Một băng vào được chia thành ô, dùng để ghi xâu vào, mỗi ký hiệu của xâu vào thuộc một bảng chữ ∑ được ghi trên một ô.
• Một đầu đọc, mỗi thời điểm trỏ đến một ô trên băng vào.
• Một bộ điều khiển Q, gồm một số hữu hạn các trạng thái, tại mỗi thời điểm nó có một trạng thái.
Các trạng thái của 1 DFA miêu tả hình trạng bên trong của máy và thường biểu thị bằng qo, q1, q2, …, qn. Thanh ghi của máy, cũng được gọi là điều khiển hữu hạn, một trong các trạng thái là giá trị của nó. Tại thời điểm bắt đầu tính toán, giá trị của thanh ghi là q0, trạng thái bắt đầu của DFA.
Đầu vào là một dãy hữu hạn liên tiếp của các thành phần trong bảng chữ ∑. Băng chứa đầu vào đến khi được tính toán . Băng được chia làm các ô, mỗi ô chứa giá trị của một ký tự của bảng chữ. Do không có giới hạn về độ dài của xâu đầu vào nên băng cũng không phải giới hạn về độ dài.
Đầu đọc của băng đọc theo từng ô của xâu vào. Bộ phận chính của máy là đầu đọc băng và thanh ghi. Vị trí của đầu đọc băng là ký tự của băng vào được. Trạng thái hiện tại của automat được chỉ bởi giá trị của thanh ghi. Trong automat hữu hạn đơn định thì việc dịch chuyển trạng thái được quyết định dựa vào ký tự đầu đọc đang chỉ và trạng thái hiện thời của thanh ghi. Và chỉ có một trạng thái mới được chuyển đến khi đầu đọc đọc một ký tự và thanh ghi đang chỉ một trạng thái nào đó. Không có nhiều hơn một chuyển đổi hình trạng khi xử lí với một trạng thái của thanh ghi và một ký tự đầu vào.
Cụ thể một tính toán (hay chuyển đổi) của 1 Automat gồm sự thi hành của 1 cấu trúc tuần tự các bước: Đọc ký tự vào (ký tự đầu đọc đang chỉ), xem xét trạng thái hiện thời của máy và sau đó quyết định chuyển trạng thái cùng với dịch chuyển đầu đọc sang phải một ô để đọc kí tự tiếp theo.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
Ngày nay, các ngôn ngữ là một phần không thể thiếu trong công việc của mối người làm tin học. Để có thể hiểu sâu sắc về các ngôn ngữ lập trình ( giải thuật và cú pháp ) thì không thể không ngiên cứu về các ngôn ngữ hình thức, về các văn phạm và các Automat. Cũng chính vì vậy Ngôn Ngữ Hình Thức được đưa vào làm môn học cho tất cả các sinh viên công nghệ thông tin.
Trong đề tài này, chúng em xin trình bày về Automat hữu hạn đơn định tối thiểu.
Với mục đích nghiên cứu, tìm hiểu, bài tập lớn còn có nhiều thiếu sót, cũng như nhiều phần còn chưa được đề cập đầy đủ. Vì vậy, nhóm chúng em rất mong được sự góp ý của thầy giáo.
Trong bài tập này của chúng em gồm có các phần sau:
• Khái niệm DFA
• Cách xác định các trạng thái tương đương
• Xây dựng DFA tối thiểu từ DFA ban đầu
• Xây dựng thuật giải tối thiểu hóa DFA
CHƯƠNG I – AUTOMAT HỮU HẠN ĐƠN ĐỊNH
1.1. Khái Niệm
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 đầu vào. Mỗi ký hiệu nhập được chọn từ một bộ chữ cái, 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 automat 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 Automat hữu hạn đơn định M được biểu diễn như sau:
M = (Q, ∑, δ, q0, F).
Trong đó:
Q là tập hữu hạn các trạng thái
∑ là tập hữu hạn các kí tự đầu vào gọi là bảng ký tự
q0 € Q là trạng thái bắt đầu
F là tập hợp con của Q gọi là tập trạng thái kết thúc (trạng thái đoán nhận).
δ là hàm chuyển đổi trạng thái: Q x ∑ → Q.
Một automat hữu hạn là một máy đoán nhận xâu. Gồm có 3 bộ phận:
• Một băng vào được chia thành ô, dùng để ghi xâu vào, mỗi ký hiệu của xâu vào thuộc một bảng chữ ∑ được ghi trên một ô.
• Một đầu đọc, mỗi thời điểm trỏ đến một ô trên băng vào.
• Một bộ điều khiển Q, gồm một số hữu hạn các trạng thái, tại mỗi thời điểm nó có một trạng thái.
Các trạng thái của 1 DFA miêu tả hình trạng bên trong của máy và thường biểu thị bằng qo, q1, q2, …, qn. Thanh ghi của máy, cũng được gọi là điều khiển hữu hạn, một trong các trạng thái là giá trị của nó. Tại thời điểm bắt đầu tính toán, giá trị của thanh ghi là q0, trạng thái bắt đầu của DFA.
Đầu vào là một dãy hữu hạn liên tiếp của các thành phần trong bảng chữ ∑. Băng chứa đầu vào đến khi được tính toán . Băng được chia làm các ô, mỗi ô chứa giá trị của một ký tự của bảng chữ. Do không có giới hạn về độ dài của xâu đầu vào nên băng cũng không phải giới hạn về độ dài.
Đầu đọc của băng đọc theo từng ô của xâu vào. Bộ phận chính của máy là đầu đọc băng và thanh ghi. Vị trí của đầu đọc băng là ký tự của băng vào được. Trạng thái hiện tại của automat được chỉ bởi giá trị của thanh ghi. Trong automat hữu hạn đơn định thì việc dịch chuyển trạng thái được quyết định dựa vào ký tự đầu đọc đang chỉ và trạng thái hiện thời của thanh ghi. Và chỉ có một trạng thái mới được chuyển đến khi đầu đọc đọc một ký tự và thanh ghi đang chỉ một trạng thái nào đó. Không có nhiều hơn một chuyển đổi hình trạng khi xử lí với một trạng thái của thanh ghi và một ký tự đầu vào.
Cụ thể một tính toán (hay chuyển đổi) của 1 Automat gồm sự thi hành của 1 cấu trúc tuần tự các bước: Đọc ký tự vào (ký tự đầu đọc đang chỉ), xem xét trạng thái hiện thời của máy và sau đó quyết định chuyển trạng thái cùng với dịch chuyển đầu đọc sang phải một ô để đọc kí tự tiếp theo.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links
Tags: automat hữu hạn đơn định