Download miễn phí Đề tài Hai DFA tương đương



MỤC LỤC
(Deterministic Finite Automat – DFA) 1
I.1. Mô tả không hình thức 1
I.2. Mô tả hình thức 2
I.3. DFA xử lý xâu như thế nào 2
I.4. Các cách biểu diễn đơn giản hơn của DFA 4
a. Biểu đồ dịch chuyển 4
b. Bảng dịch chuyển 5
I.5. Hàm dịch chuyển mở rộng 5
I.6. Ngôn ngữ được thừa nhận bởi DFA 7
Chương II. 9
SỰ TƯƠNG ĐƯƠNG CỦA CÁC AUTOMAT DFA 9
II.1. Sự tương đương của các trạng thái 9
II.2. Sự tương đương của các DFA 11
a. Dự vào bảng đánh dấu sự tương đương các trạng thái 11
b. Dựa vào tính đóng dưới phép giao 12
II.3. Cài đặt 15
a. Cài đặt dựa theo trạng thái tương đương 16
 
 


http://s1.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2013-04-10-de_tai_hai_dfa_tuong_duong.dA1cuz2JU2.swf /tai-lieu/de-tai-ung-dung-tren-liketly-5970/
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí

Tóm tắt nội dung tài liệu:

MỤC LỤC
Chương I.
AUTOMAT ĐƠN ĐỊNH
(Deterministic Finite Automat – DFA)
I.1. Mô tả không hình thức
Automat hữu hạn là một cái máy đoán nhận xâu. Nó bao gồm các bộ phận sau:
- 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 bảng chữ Σ được ghi trên một ô
- Một đầu đọc, mỗi thời điểm đọc (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
Hoạt động của Automat được thực hiện như sau: Automat hoạt động theo từng bước. Mỗi bước như sau: tùy theo trạng thái hiện thời của bộ điều khiển và kí hiệu mà đầu đọc đang đọc, mà Automat chuyển sang một trạng thái mới, đồng thời đầu đọc dịch chuyển sang phải một ô.
Quy luật chuyển trạng thái của Automat hữu hạn đơn định được mô tả bởi một hàm, được gọi là hàm dich chuyển như sau:
Trong Q, có một trạng thái đầu, thường kí hiệu qo và một tập hợp các trạng thái cuối / thừa nhận, thường kí hiệu F (F Í Q).
Ta nói Automat thừa nhận xâu vào w nếu sau khi xuất phát từ trạng thái đầu qo và đầu đọc chỉ vào kí hiệu bên trái nhất của xâu w, sau một số bước dịch chuyển hữu hạn, Automat đọc song xâu w và rơi vào một trong các trạng thái cuối thuộc F.
Tập hợp tất cả các xâu đoán nhận bởi Automat hợp thành ngôn ngữ được nhận bởi Automat đó.
I.2. Mô tả hình thức
Định nghĩa: Một Automat hữu hạn đơn định DFA được định nghĩa như là một bộ năm: (Q, Σ, δ, q0, F), trong đó:
. Q là tập hợp hữu hạn các trạng thái.
. Σ là bộ chữ cái nhập hữu hạn.
. δ là hàm chuyển ánh xạ từ Q × Σ → Q, tức là δ(q, a) là một trạng thái được cho bởi phép chuyển từ trạng thái q trên ký hiệu nhập a thì nó chuyển sang trạng thái q’.
. q0 Î Q là trạng thái bắt đầu
. F Í Q là tập các trạng thái kết thúc.
I.3. DFA xử lý xâu như thế nào
Giả sử w = a0a1...an là xâu vào. DFA sẽ bắt đầu với trạng thái q0, nó sẽ thực hiện dịch chuyển δ(q0, a1) giả sử cho q1. DFA bây giờ ở trạng thái q1 và kí hiệu tiếp theo sẽ đọc a2, nó thưc hiện dịch chuyển δ(q1, a2) giả sử cho q2. Nó cứ tiếp tục như thế, cho đến khi đọc an thì sẽ chuyển sang trạng thái qn nào đó, nếu qn thuộc tập F thì DFA thừa nhận xâu vào w, ngược lại thì xâu vào sẽ không được thừa nhận.
Ví dụ: Xây dựng DFA thừa nhận các xâu gồm các kí hiệu 0, 1 và chứa ít nhất một lần xâu 01, nghĩa là chúng ta có thể mô tả ngôn ngữ L này như sau:
L = { x01y / x và y gồm các kí tự 0 và 1 bất kì }
Để xây dựng DFA thừa nhận L, DFA M cần ghi nhớ các khả năng sau:
DFA đã đọc xâu 01, như thế sau đó nó có thể thừa nhận xâu vào.
DFA chưa bao giờ đọc kí tự 0, nhưng nó đã đọc ít nhất kí tự 1, trong trường hợp này nó có thể tiếp tục đọc các kí tự 1 cho đến khi nào đó một kí tự 0 đầu tiên, thì nó có thể sau đó đọc một kí tự 1 đi liền sau.
DFA chưa đọc xâu 01, nhưng ngay trước đó ít nhất một kí tự 0, như thế nó có thể tiếp tục đọc kí tự 0 cho đến khi gặp một kí tự 1 thì có thể chuyển sang thừa nhận xâu vào.
Với nhận xét trên chúng ta dễ dàng thấy mỗi trường hợp trên sẽ ứng với một trạng thái ghi nhớ của DFA. Trường hợp (1) sẽ tương ứng với trạng thái thừa nhận, kí hiệu trạng thái q2, ở trạng thái này, DFA có thể tiếp tục đọc bất kì kí hiệu nào. Như thế δ(q2, 0) = δ(q2, 1) = q2.
Trường hơp (2) sẽ tương ứng với trạng thái đầu q0, khi ở trạng thái này DFA có thể tiếp tục đọc kí tự cho đến khi gặp kí tự 0 thì chuyển sang trạng thái khác. Như thế δ(q0, 1) = q0, δ(q0, 0) = q1.
Trường hợp (3) sẽ tương ứng với trạng thái q1, khi đã đọc trước đó ít nhất một kí tự 0, nhưng chưa bao giờ đọc xâu 01.Ở trạng thái q1 thì DFA có thể tiếp tục đọc kí tự 0 cho đến khi gặp kí tự 1, thì chuyển sang trạng thái thừa nhận q2. Như thế δ(q1, 0) = δ(q1, 1) =q2.
Vậy cuối cùng chúng ta có DFA như sau:
M=({q0, q1, q2}, {0, 1}, δ, q0, {q2})
Với δ được định nghĩa như trên.
Giải thuật mô phỏng hoạt động của một DFA
Mục đích: kiểm tra một chuỗi nhập x có thuộc ngôn ngữ L(M) đoán nhận bởi automata M.
Input: chuỗi nhập x$
Output: câu trả lời ‘YES’ hay ‘NO’
Giải thuật:
q := q0 ;
c := nextchar ; {c là ký hiệu nhập được đọc tiếp theo}
While c $ do
begin
q := δ(q, c);
c := nextchar ;
end
If (q in F) then write("YES") else write("NO");
I.4. Các cách biểu diễn đơn giản hơn của DFA
Cách mô tả DFA bằng bộ năm như trên là tương đối khó hiểu và ít trực quan. Có hai cách mô tả đơn giản hơn một DFA là: biểu đồ dịch chuyển và bản dịch chuyển
a. Biểu đồ dịch chuyển
Mỗi trạng thái trong Q là một nút.
Với mỗi trạng thái q Î Q và mỗi kí hiệu a Î Σ, có δ(q, a) = p Î Q. Như thế, biểu đồ dịch chuyển có một cung đi từ nút p đến q mang nhãn a, nếu có nhiều kí hiệu tạo ta dịch chuyển từ q đến p thì chỉ cần biểu diễn một cung mang nhãn là danh sách các kí hiệu đó.
Có một mũi tên đi vào nút q0 để kí hiệu trạng thaí đầu.
Các trạng thái kết thúc F là các nút được biểu diễn bởi hai vòng tròn.
Các trạng thái không thuộc F là các nút được biểu diễn bởi chỉ một vòng tròn
Ví dụ:
DFA biểu diễn ngôn ngữ trong Ví dụ
b. Bảng dịch chuyển
Bảng dịch chuyển cho một DFA là một quy ước biểu diễn dạng bảng của hàm, mà ở đây là dịch chuyển với hai tham số: các trạng thái và các kí hiệu vào. Trạng thái đầu được đánh dấu bởi dấu à, các trạng thái cuối sẽ được đánh các dấu * .
Bảng dịch chuyển của DFA xây dựng trong Ví dụ
I.5. Hàm dịch chuyển mở rộng
Một cách không hình thức chúng ta có thể nhận thấy rằng, một DFA định nghĩa ngôn ngữ gồm các xâu là kết quả của quá trình dịch chuyển từ trạng thái đầu đến một trong các trạng thái thừa nhận. Để xác định ngôn ngữ được thừa nhận bởi một DFA, chúng ta sẽ định nghĩa hàm dịch chuyển mở rộng. Hàm dịch chuyển mở rộng, kí hiệu là δ* , sẽ nhận tham số là trạng thái q và xâu w và trả về trạng thái p. Nghĩa là DFA đang ở trạng thái q, sau khi xử lý xâu w thì DFA đạt đến trạng thái p.
Định nghĩa: Hàm dịch chuyển mở rộng được định nghĩa đệ quy trên độ dài của xâu như sau:
δ*(q, ε) =q, với mọi trạng thái q, nếu DFA không đọc kí hiệu vào nào sẽ ở lại trạng thái đó.
δ*(q, w)= δ (δ*(q, x), a), với w = x a, x Î Σ* và a Î Σ.
Ví dụ: Xây dựng DFA thừa nhận ngôn ngữ
L = {w / w chỉ chứa các kí hiệu 0, 1 và luôn kết thúc bởi kí hiệu 1}
DFA phải phân biệt hai khả năng:
Khi nó đọc kí hiệu 1, thì ngay sau đó có thể kết thúc.
Khi nó đọc kí hiệu 0 thì ngay sau đó không được kết thúc, mà phải đọc tiếp các kí hiệu khác cho đến khi gặp kí hiệu 1. Như thế, DFA sẽ có ít nhất hai trạng thái tương ứng với hai khả năng trên.
Ta xâu dựng DFA như sau:
M = ({q0, q1}, {0, 1}, δ, q0, {q1})
Trong đó, hàm δ như sau:
DFA cho Ví dụ
Hay chúng ta có thể biểu diễn hàm δ bởi bảng dịch chuyển như sau:
δ
0
1
àq0
q0
q1
* q1
q0
q1
Sử dụng hàm dịch chuyển mở rộng để đoán nhận xâu w = 101101 của ngôn ngữ L.
δ*(q0, ε) = q0
δ*(q0, 1) = δ (δ*(q0, ε), 1) = δ*(q, 1) = q1
δ*(q0, 10) = δ(δ*(q0, 1), 0) = δ (q1, 0) = q0
δ*(q0, 101) = δ(δ*(q0, 10), 1) = δ (q0, 1) = q1
δ*(q0, 1011) = δ(

---