TIỂU LUẬN LÝ THUYẾT TÍNH TOÁN Ôtômát Không đơn định Và ...

Tải bản đầy đủ (.doc) (36 trang)

1. Trang chủ
>>
2. Khoa học tự nhiên
>>
3. Toán học

TIỂU LUẬN LÝ THUYẾT TÍNH TOÁN Ôtômát không đơn định và định lý KLEENE

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (406.34 KB, 36 trang )

Giáo viên hướng dẫn : PGS.TS.Phan Huy Khánh Nhóm học viên : Nguyễn Công Bằng Cao Bá Thành Võ Thị Ngọc Hà Lớp : Khoa học máy tính K12ĐÀ NẴNG, 04/2010Môn Lý Thuyết Tính ToánBỘ GIÁO DỤC ĐÀO TẠOĐẠI HỌC ĐÀ NẴNGTIỂU LUẬN LÝ THUYẾT TÍNH TOÁN - 1 -Môn Lý Thuyết Tính ToánPhần lý thuyếtChương 4: Ôtômát không đơn định và định lý KLEENE4.1. Ôtômat hữu hạn không đơn địnhĐể chứng minh rằng các ngôn ngữ thông thường là giống như những ngôn ngữ tự nhiên mà có thể được thừa nhận bởi một ôtômat hữu hạn, nó là công cụ rất hữu ích để xem xét ngôn ngữ chính quy rất giống với một ôtômat hữu hạn, tuy nhiên, vẫn có một tập hữu hạn các trạng thái và một vài chức năng của trạng thái kế tiếp để lựa chọn, nhưng với các tiêu chuẩn khác. Nó chỉ ra rằng các thiết bị này nhận ra cùng một ngôn ngữ đúng đắn của các ôtômat hữu hạn nhưng thường là đơn giản để xây dựng và giải thích.Ví dụ 4.1. Hình 4-1a hiển thị các ôtômat hữu hạn xây dựng trong ví dụ 3.14, mà nhận ra ngôn ngữ L tương ứng với biểu thức chính quy (11 +110) * 0. Bây giờ nhìn vào biểu đồ trong hình 4-1b. Các lỗi này được các sơ đồ của một ôtômat hữu hạn đưa ra hai lý do rõ ràng khác nhau. Từ một số trạng thái không có quá trình chuyển đổi cho cả hai ký hiệu đầu vào (từ trạng thái q4 không có quá trình chuyển đổi ở tất cả các trạng thái); và từ một trạng thái, q0, có hai mũi tên tương ứng với đầu vào 1.Các cách để giải thích đầu tiên của các tính năng này rất dễ dàng: Do không có quá trình chuyển đổi từ một trạng thái q nghĩa là từ q không có bắt đầu với một dữ kiện đầu vào có thể cung cấp cho kết quả của một trạng thái đang được chấp nhận. Chúng ta có thể tạo ra một quá trình chuyển đổi bằng cách tạo một trạng thái"chết" mà các thiết bị có thể đi từ q trên một đầu vào, có một đặc tính mà mỗi khi thiết bị nhận đầu vào một trạng thái mà nó không bao giờ có thể rời khỏi nó. Tuy nhiên, quá trình chuyển đổi này sẽ không bao giờ được thực thi trong bất cứ trình tự dịch chuyển của các trạng thái đi đến một trạng thái được chấp nhận. Do đó, để nó thoát ra khỏi mà không ảnh hưởng đến bất cứ trạng thái chuyển đổi khác(ngoại trừ việc nó vi phạm các luật), và nó làm cho sơ đồ đơn giản.Lỗi thứ hai trong các quy định cho Ôtômat hữu hạn có vẻ là nghiêm trọng hơn. Nếu như có hai quá trình chuyển đổi từ q0 trên đầu vào 1, sau đó nó không rõ ràng những gì thiết bị này là phải làm trong tình hình đó, và vì vậy rất khó để giải thích những sơ đồ tại một trong những cách chúng ta đã làm trong Chương 3: là một thuật toán cho một ngôn ngữ chấp nhận, hoặc như một máy trừu tượng. (Đối với các thuật toán một hoặc một máy, hành động đó sẽ được thực thi trên ở mỗi bước nên được một cách dễ hiểu và rõ ràng.)- 2 -Môn Lý Thuyết Tính Toán q2 q1 q0 q3 0 1 1 0 q0 s r t u p 1 0 0,1 0 0 1 1 0 1 0,1 q4 1 1 (a) (b) Hình 4-1.Tuy nhiên, có một ý nghĩa trong đó hình 4-1b dường như phản ánh chính xác các cấu trúc của biểu thức thông thường, một cảm giác mà nó là, trên thực tế, dễ dàng nhận dạng như phù hợp với các biểu hiện thường xuyên hơn là ôtômat hữu hạn. Cho bất kỳ một chuỗi x trong L, nó rất dễ dàng để mô tả đường dẫn trong sơ đồ tương ứng với x và từ trạng thái đầu q0 đến trạng thái q4. Bắt đầu tại q0, và cho mỗi lần xuất hiện một trong những chuỗi 11 hoặc 110 trong phần tử của x tương ứng đến (11 + 110) *, nó tạo vòng lặp thích hợp rồi quay về q0; khi gặp phải 0 là kết thúc, đường dẫn dịch chuyển đến trạng thái q4 chấp nhận. Rõ ràng rằng bất kỳ đường dẫn bắt đầu từ q0 và kết thúc tại q4 tương ứng với một số chuỗi dưới dạng biểu thức thông thường.Bây giờ chúng ta có cách tiếp cận theo hướng khác hình 4-1b, mặc dù nó không giống như cách chúng ta giải thích một sơ đồ chuyển tiếp cho một ôtômat hữu hạn. Thay vì yêu cầu cho dù một số đường dẫn tương ứng với một đường dẫn đến một dãy trạng thái được chấp nhận, chúng ta tìm hiểu một vài đường dẫn tương ứng với từng chuỗi. Chúng ta có thể so sánh điều này áp dụng để giải quyết trực tiếp cho một chuỗi x (11110110) tương ứng với biểu thức chính quy của chúng ta, (11 + 110) * 0. có một số cách chúng ta có thể áp dụng kết hợp với chúng, và một số phương pháp tiếp cận sẽ không hoạt động được(ví dụ, kết hợp tiền tố 1111 với - 3 -Môn Lý Thuyết Tính Toán(11 + 110) *), tuy nhiên, nếu có ít nhất một cách kết hợp với chúng, chúng ta kết luận rằng x tương ứng với biểu thức chính quy.Một cách hữu ích của tư duy về tình hình này là giới thiệu ý tưởng đoán. Trong cố gắng để phù hợp với chuỗi 11110110 để biểu thức thông thường (11 + 110) * 0, chúng ta nhìn vào phần tử 1 đầu tiên của chuỗi. Chúng ta có thể đoán rằng cách thích hợp để sử dụng nó như phần tử đầu tiên là 1 trong chuỗi 110; Tuy nhiên, cho đến khi chúng ta kiểm tra chi tiết của chuỗi chúng ta không biết liệu đoán của chúng ta là chính xác. Tương tự, tại các sơ đồ trong hình. 4-1b, khi chúng ta đang ở trạng thái q0 và chúng ta nhận được ký tự đầu vào 1, chúng ta đoán trong đó có nhãn 1 thích hợp theo mũi tên. Đoán sai có nghĩa là chúng ta trả lời "không" cho một chuỗi đó là thực tế trong ngôn ngữ. Đây không phải là một vấn đề nghiêm trọng, bởi vì chúng ta giải thích của biểu đồ là nếu có bất kỳ chuỗi đoán rằng khônễnây dựng một câu trả lời tích cực, chuỗi nên được chấp nhận.Chúng tôi hầu như đã sẵn sàng cho một định nghĩa chính thức của minh hoạ “hình tượng trưng” trừu tượng bằng hình. 4-1b. Thay đổi duy nhất chúng ta sẽ cần phải thực hiện trong định nghĩa của một ôtômat hữu hạn liên quan đến chức năng chuyển đổi. Như chúng ta đã thấy trong ví dụ 4.1, cho một sự kết hợp cụ thể của một trạng thái và ký tự một đầu vào, có thể không có trạng thái đặc biệt nào để mà dịch chuyển, hoặc có thể có một vài. Điều này thừa nhận rằng nếu chúng ta muốn chức năng chuyển đổi δ được định nghĩa trên Q × Σ, như đã trình bày trước đó, giá trị sẽ không phải là một yếu tố của Q nhưng một tập hợp con của Q- có thể tập hợp rỗng, có thể một tập hợp với vài yếu tố. Sự giải thích của chúng ta đó là δ(q, a) miêu tả tập hợp các trạng thái mà có thể được xem là hợp lý, như một kết quả ở trong trạng thái q tại bước ưu tiên và sau đó xử lý ký tự đầu vào a. Điều này có nghĩa rằng tại thời điểm này chúng ta xem hình tượng trưng như là không đơn định: Tại một vài giai đoạn nó sẽ có một chọn lựa cho sự dịch chuyển, và mỗi lần điều này xảy ra nó chọn một di chuyển trong một vài hướng đi không rõ ràng. Ngay sau đó, chúng ta sẽ thấy rằng tính không đơn định thực sự rõ ràng hơn bởi vì chúng ta sẽ phải xây dựng một ôtômat hữu hạn thông thường đó được tái tạo chính xác các hoạt động như máy không đơn định.Định nghĩa 4.1. Một ôtômat hữu hạn không đơn định, được viết tắt là NFA, gồm 5 thành phần M =(Q, Σ, q0, A, δ), mà Q và Σ là các tập hợp hữu hạn không rỗng, q0 ∈ Q, A ⊂ Q, và δ: Q × Σ→ 2QQ là tập hợp các trạng thái, Σ là bảng mẫu tự, q0 là trạng thái đầu, và A là tập hợp các trạng thái được chấp nhận, 2Q có nghĩa là tập hợp của tập hợp con của Q. Cũng giống trong trường hợp các ôtômat hữu hạn, nó hữu ích để mở rộng chức năng dịch chuyển δ từ Q × Σ để mở rộng hơn tập hợp Q × Σ* . Cho một ôtômat hữu hạn không đơn định M, δ*(q, x) là tập hợp các trạng thái của M có thể được xem là hợp lý như kết quả của sự bắt đầu trong trạng thái p và xử lý các ký tự và ở chuỗi x. Công thức đệ quy cho các ôtômat hữu hạn là:- 4 -Môn Lý Thuyết Tính Toánδ*(p, xa) = δ(δ*(p, x), a)Tại p là trạng thái bất kỳ, x là chuỗi bất kỳ trong Σ* , và a là ký tự đơn bất kỳ trong bảng mã tự. Chúng ta sẽ cho một định nghĩa đệ quy như sau: Tuy nhiên, cho chúng ta bắt đầu với phương pháp dể tiếp cận hơn. Trước hết, chúng ta không muốn nói rằng chỉ trạng thái M có thể nhận từ p bằng một kết quả của việc xử lý Λ là p; chỉ khác bây giờ là chúng ta viết δ*(p, Λ)={p}, đúng hơn δ*(p, Λ)=p. Nếu x = a1a2…an, thì nói rằng M có thể nhận trạng thái q sau khi xử lý x điều đó có nghĩa là có các trạng thái p0,p1,p2,…,pn sao cho p0 = p, pn = q, và cho mỗi i > 0, M có thể nhận trạng thái pi từ pi – 1 bằng cách xử lý ai. Một cách đơn giản hơn để nói rằng “M có thể nhận pi từ pi – 1 bằng cách xử lý ai” là chính xác.Pi ∈ δ(pi - 1, ai)Do đó, mô tả đầu tiên của chúng ta về chức năng của δ*như sau.Định nghĩa 4.2a(Định nghĩa không đệ quy của δ* cho một ôtômat hữu hạn không đơn định). Cho một ôtômat hữu hạn không đơn định tuỳ ý M =(Q, Σ, q0, A, δ) và cho bất kỳ p ∈ Q, δ*(p, Λ)={p}. Cho bất kỳ p ∈ Q và cho bất kỳ x = a1a2…an ∈ Σ* , δ*(p, x) là tập hợp tất cả các trạng thái q cho trạng thái nào có ở một dãy của các trạng thái p = p0, p1,…, pn – 1, pn = q được thoả mãn.pi ∈ δ(pi - 1, ai) cho mỗi i với 1 < i < nTheo thứ tự để tồn tại mô tả một cách đệ của δ*, chúng ta ghi chuỗi x bằng yan, tại y = a1a2…an – 1. Nếu q ∈ δ*(p, yan), thì theo định nghĩa của chúng ta có các trạng thái p = p0, p1,…, pn – 1, pn = q sao cho mỗi i > 0, pi ∈ δ(pi - 1, ai). Nếu chúng ta dừng đúng trước bước sau cùng và áp dụng định nghĩa, chúng ta có thể phát biểu rằng pn – 1 ∈ δ*(p, y) và do đó q = pn ∈ δ(r, an) cho một vài r ∈ δ*(p, y). Nó mặc dù dể hiểu mà đối số có thể bị nghịch đảo: Nếu pn ∈ δ(r, an) cho vài r ∈ δ*(p, y), thì chúng ta có thể kết thúc từ định nghĩa mà pn ∈ δ*(p, yan). Kết thúc là công thức đệ quy chúng ta cần:δ*(p, yan) = {q | q ∈ δ(r, an) cho vài r ∈ δ*(p, y)} hoặc, ngắn gọn hơn, δ*(p, yan) = U δ(r, an) r ∈ δ*(p, y) Định nghĩa 4.2b(Định nghĩa đệ quy của δ* cho một Ôtômat hữu hạn không đơn định). Cho M=(Q, Σ, q0, A, δ) là một ôtômat hữu hạn không đơn định. Chức năng δ*: Q × Σ* → 2Q được định nghĩa như sau:1. Cho bất kỳ q ∈ Q, δ*(q, Λ)={q}.2. Cho bất kỳ y ∈ Σ*, a ∈ Σ, và q ∈ Q, δ*(q, ya) = U δ(p, a) p ∈ δ*(q, y) - 5 -Môn Lý Thuyết Tính ToánChúng ta phát biểu rằng một chuỗi x được chấp nhận bởi một ôtômat hữu hạn không đơn định M có nghĩa rằng có một dãy các dịch chuyển M có thể tạo nên, Bắt đầu trong trạng thái đầu và xử lý các ký hiệu của x, ở đó sẽ được chấp nhận ở trạng thái đầu. Trong những từ khác, M chấp nhận x nếu thiết lập các trạng thái trong mà M có thể kết thúc cho kết quả xử lý x chứa tại trạng thái chấp nhận đầu tiên.Định nghĩa 4.3. Cho M = (Q, Σ, q0, A, δ) là một ôtômat hữu hạn không đơn định. Chuỗi x ∈ Σ* được chấp nhận bởi M nếuδ*(q0, x) ∩ A ≠ ø. Ngôn ngữ thừa nhận, hoặc chấp nhận, bởi M thì cho L(M) của tất cả các chuỗi được chấp nhận bởi M. Cho bất kỳ ngôn ngữ nào L ⊂ Σ* , L được thừa nhận bởi M nếu L = L(M).Ví dụ 4.2. Cho M = (Q, Σ, q0, A, δ), tại Q = {q0, q1, q2, q3}, Σ = {0, 1}, A = {q3}, và δ được cho bởi bảng sau:q δ(q, 0) δ(q, 1)q0{q0} {q0 , q1}q1{q2} {q2}q2{q3} {q3}q3ø øKhi đó M được minh hoạ bởi sơ đồ dịch chuyển trong hình 4-2. Cho phép chúng ta dùng để xác định L(M) bằng cách tính δ*(q0, x) cho một vài chuỗi x theo chiều tăng dần. Ta có nhận xét thứ nhất rằng từ định nghĩa không đệ quy của δ* , nó hầu hết là hiển nhiên với δ và δ* chấp nhận cho các chuỗi có độ dài 1(cũng áp dụng cho bài tập 4.2). q0 q1 q2 q3 0,1 1 0,1 0,1 Hình 4-2 Vấn đề đó được phát biểu bởi sự kế thừa ở bảng trước đó δ*(q0, 0) = {q0} và δ*(q0, 1) = {q0 , q1}.- 6 -Môn Lý Thuyết Tính Toán δ*(q0, 11) = U δ(p, 1) (được định nghĩa từ δ* ) p ∈ δ*(q0, 1) = U δ(p, 1) p ∈ {q0, q1 } = δ(q0, 1) ∪ δ(q1, 1) = {q0, q1} ∪ {q2} = {q0, q1, q2} δ*(q0, 01) = U δ(p, 1) p ∈ δ*(q0, 0) = U δ(p, 1) p ∈ {q0 } = δ(q0, 1) = {q0, q1} δ*(q0, 111) = U δ(p, 1) p ∈ δ*(q0, 11) = δ(q0, 1) ∪ δ(q1, 1) ∪ δ(q2, 1) = {q0, q1, q2,q3} δ*(q0, 011) = U δ(p, 1) p ∈ δ*(q0, 01) = δ(q0, 1) ∪ δ(q1, 1) = {q0, q1, q2} - 7 -Môn Lý Thuyết Tính ToánTại điểm này chúng ta thấy rằng 111 được chấp nhận bởi M và 011 thì không. bạn có thể thấy nếu bạn nghiên cứu sơ đồ trong hình 4-2 ở đó δ*(q0, x) chứa q1 nếu và chỉ nếu x kết thúc bằng 1; và do đó ngôn ngữ được thừa nhận bởi M là: {0, 1}*{1}{0, 1}2Ngôn ngữ này được gọi là L3 trong ví dụ 3.15, cho các chuỗi với độ dài tối thiểu bằng 3 chứa một phần tử 1 ở vị trí thứ ba kể từ cuối chuỗi. Được trình bày ở sơ đồ trong hình 4-2 như một mô hình mẫu, bạn có thể dễ dàng xây dựng cho bất kỳ n > 1 một ôtômat hữu hạn không đơn định với n + 1 trạng thái đó thừa nhận Ln. Bởi vì trong ví dụ 3.14 chúng ta đã trình bày rằng bất kỳ ôtômat hữu hạn thường chấp nhận Ln cần ít nhất 2n trạng thái, đơn giản để hiểu rằng một ôtômat hữu hạn không đơn định thừa nhận một ngôn ngữ sẽ có ít trạng thái hơn ôtômat hữu hạn thừa nhận ngôn ngữ. Bây giờ chúng ta muốn biểu diễn, tuy nhiên, mặc dù một ôtômat hữu hạn không đơn định có thể cung cấp dựa trên các khái niệm theo hướng đơn giản của việc thừa nhận cho một ngôn ngữ hơn một ôtômat hữu hạn, các ôtômat hữu hạn không đơn định như là một tập hợp không có tác động mạnh hơn các ôtômat hữu hạn: bất kỳ ngôn ngữ nào cũng được chấp nhận bởi một ôtômat hữu hạn không đơn định ngoài ra cũng được chấp nhận bởi một(có lẽ làm phức tạp hơn) ôtômat hữu hạn. Cho phép chúng ta xây dựng sự chứng minh cho sự kiện này, bằng cách chỉ ra làm thế nào để loại trừ không đơn định từ một ôtômat hữu hạn không đơn định bất kỳ theo thứ tự sao cho vẫn tồn tại một ôtômat hữu hạn thừa nhận cùng ngôn ngữ. Điều này có nghĩa là chúng ta cần đến định nghĩa “các trạng thái ” trong ôtômat hữu hạn như là một hướng đi cho mỗi sự kết hợp của trạng thái và ký hiệu vào, cho kết quả đúng của một trạng thái. Giải pháp đã được thừa nhận bởi định nghĩa của một ôtômat hữu hạn khôngn đơn định: chức năng thay đổi trạng thái tạo nên cặp trạng thái vào đến một tập hợp các trạng thái. Chú ý ít được dùng ở đây. Nó hoàn toàn không đơn định để nói đến một cặp (p, a) ∈ Q × Σ có vài trạng thái tương ứng được chấp nhận; nó ít hợp lý nhưng có thể nói rằng tương ứng với (p, a) có đúng một tập hợp các trạng thái. Nói cách khác, không đơn định là rõ ràng và có lẽ chỉ phát sinh từ ý niệm của chúng ta về một “trạng thái" là gì. Trong chứng minh của định lý 3.4 trong chương cuối cùng, chúng ta coi các trạng thái cặp là các yếu tố của Q. Sau đó, tương ứng với "các trạng thái" S và ký hiệu đầu vào a (để tập hợp của tất cả các cặp (p, a) cho mỗi p ∈ S), có một "trạng thái" đúng mà kết quả: kết hợp của các tập hợp δ(p, a) cho p ∈ S. Một cách đột ngột, không đơn định dường như đã biến mất, và kết quả tính toán của máy mô phỏng thiết bị gốc một cách rõ ràng, được cung cấp mà chúng ta xác định các trạng thái đầu tiên và cuối cùng chính xác. Một tên thích hợp cho kỹ thuật này là việc xây dựng tập hợp con: Các trạng thái trong ôtômat hữu hạn là tập con của trạng thái thiết lập của ôtômat hữu hạn không đơn định.- 8 -Môn Lý Thuyết Tính ToánĐịnh lý 4.1. Cho bất kỳ ôtômat hữu hạn không đơn định M = (Q, Σ, q0, A, δ) chấp nhận ngôn ngữ L ⊂ Σ* , có một ôtômat hữu hạn M1 = (Q1, Σ, q1, A1, δ1) cũng chấp nhận L.Chứng minh: Q1 được định nghĩa như sau:Q1 = 2Q q1 = {q0} cho q ∈ Q1 và a ∈ Σ, δ1(q, a) = U δ(p, a) p ∈ q A1 = {q ∈ Q1 | q ∩ A ≠ ø}Định nghĩa sau đây là một định nghĩa đúng bởi vì một chuỗi x sẽ được chấp nhận bởi M1 nếu, bắt đầu tại q0, tập hợp các trạng thái mà M sẽ kết thúc bằng một kết quả xử lý x chứa yếu tố nhỏ nhất của A.Sự kiện mà M1 chấp nhận cùng ngôn ngữ như M cho phép từ sự kiện mà cho bất kỳ x ∈ Σ*, δ1*(q1, x) = δ*(q0, x) Bây giờ chúng ta bằng cách chứng minh theo quy nạp trên x. Chú ý rằng chức năng δ1* và δ* được định nghĩa theo nhiều cách khác nhau: δ* trong định nghĩa 4.3, từ M là một ôtômat hữu hạn không đơn định, và δ1* trong định nghĩa 3.3, từ M1 là một ôtômat hữu hạn. Nếu x ∈Λ, then δ1*(q1, x) = δ1*(q1, Λ) = q1 (bằng định nghĩa của δ1*) = {q0} (bằng định nghĩa của q1) = δ*(q0, Λ) (bằng định nghĩa của δ*) = δ*(q0, x) Chứng minh quy nạp với giả thuyết rằng x là một chuỗi thoả mãn δ1*(q1, x) = δ*(q0, x), và chúng ta muốn chứng minh rằng cho bất kỳ a ∈ Σ, δ1*(q1, xa) = δ*(q0, xa). δ1*(q1, xa) = δ1(δ1*(q1, x), a) (bằng định nghĩa của δ1*) = δ1(δ*(q0, x), a) (bằng chứng minh quy nạp với giả thuyết ) = U δ(p, a) (bằng định nghĩa của δ1) p ∈ δ*(q0, x) = δ*(q0, xa) (bằng định nghĩa của δ*)- 9 -Môn Lý Thuyết Tính ToánM và M1 thừa nhận cùng ngôn ngữ thì bây giờ dễ dàng nhận thấy. Một chuỗi x được cấp nhận bởi M1 nếu δ1*(q1, x) ∈ A1; bây giờ chúng ta có thể phát biểu rằng điều này đúng nếu và chỉ nếu δ*(q0, x) ∩ A ≠ ø. Trong trường hợp khác, x dược chấp nhận bởi M1 nếu và chỉ nếu x được chập nhận bởi M.Điều quan trọng là thực hiện việc chứng minh của định lý đưa ra một thuật toán(xây dựng tập hợp con) cho sự loại bỏ không đơn định từ một ôtômat hữu hạn không đơn định. Cho chúng ta minh hoạ thuật toán bằng cách trở lại ôtômat hữu hạn không đơn định trong ví dụ 4.2.Ví dụ 4.3. Bảng trong ví dụ 4.2 trình bày chức năng dịch chuyển của ôtômat hữu hạn không đơn định trình bày hình 4-2. Xây dựng tập hợp con có thể trình diễn một ôtômat hữu hạn bằng 16 trạng thái, từ Q có 16 tập hợp con. Tuy nhiên, chúng ta có thể nhận được bởi một vài nếu chúng ta đi theo như phương pháp trong ví dụ 3.16 và chỉ dùng những trạng thái đó có thể chấp nhận được từ trạng thái đầu. Chức năng dịch chuyển trong ôtômat hữu hạn của chúng ta là δ1, và chúng ta bắt đầu tính toán một vài gia strị của nó. Tại mỗi thời điểm một trạng thái mới S xuất hiện trong việc tính toán cảu chúng ta, chúng ta phải thực hiện tính toán bao gồm δ1(S, 0) và δ1(S, 1). δ1 ({q0}, 0) = {q0} δ1 ({q0}, 1) = {q0, q1} δ1 ({q0, q1}, 0) = δ ({q0}, 0) ∪ δ({q1}, 0) = {q0} ∪ {q2} = {q0, q2} δ1 ({q0, q1}, 1) = δ ({q0}, 1) ∪ δ({q1}, 1) = {q0, q1} ∪ {q2} = {q0, q1, q2} δ1 ({q0, q2}, 0) = δ ({q0}, 0) ∪ δ({q2}, 0) = {q0} ∪ {q3} = {q0, q3} δ1 ({q0, q2}, 1) = {q0, q1} ∪ {q3} = {q0, q1, q3}Nó hiện diện trong các tiến trình của việc tính toán, xuất hiện tám trạng thái riêng biệt. Chúng ta đã được thảo luận trong ví dụ 3.14 mà tối thiểu việc này là hiển nhiên. Về việc đó, mặc dù chúng ta sẽ không mong đợi việc xảy ra trong toàn bộ, việc tính toán kết quả trong trường hợp ôtômat hữu hạn với một vài trạng thái hợp lý chấp nhận ngôn ngữ mệnh lệnh. Được trình bày trong hình 4-3.Ví dụ 4.4. Chúng ta bỏ qua phần này bằng cách quay lại ôtômat hữu hạn không đơn định ban đầu để xem xét, một chi tiết trong hình 4-1b. với sự kiện, ôtômat hữu hạn đưa ra với thuật toán của chúng ta là một trong hình 4-1a; cho chúng ta thấy rằng làm thế nào để đạt được nó.Nếu chúng ta bỏ qua việc tính toán theo thứ tự những ưu tiên đơn giản, các trạng thái riêng biệt của ôtômat hữu hạn là tất yếu, theo thứ tự mà chúng xuất hiện, sự xuất hiện là {q0}, {q4} {q1 q2}, ø, {q0, q3}, và {q0, q4}. Bảng quả dịch chuyển được trình bày trang tiếp theo. - 10 -Môn Lý Thuyết Tính Toán q0 q0q1 q0q2 q0q1q2 q0q1q2q3 q0q2q3 q0q1q3 q0q3 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 Hình 4-3: FA tương ứng với NFA ở hình 4-2qδ1(q,0) δ2 (q,1){q0} {q4} {q1,q2}{q4} θ Θ{q1,q2} Θ {q0,q3}θ θ Θ{q0,q3} {q0,q4} {q1,q2}{q0,q4} {q4} {q1,q2}Có thể nhận ra điều này như FA, được thể hiện trong hình 4-1a bằng cách thay thế p cho q4, r cho {q1, q2} s cho Ө, t cho. {q2, q3}, và u cho {q3, q4}. (bạn cũng nên thay thế q0 cho {q0 }).4.2 Ô tô mat hữu hạn không đơn định với dịch chuyển -∧ Trong phần này, chúng tôi thực hiện thêm một bước nữa để khái quát chương trình Ô tô mat hữu hạn bởi các quy tắc đơn giãn, để đơn giản hóa hơn nữa bằng cách đưa các biểu thức Ô tô mat hữu hạn thông thường và tương đương với các biểu thức đã cho. Chúng tôi minh họa cho tổng quát hơn nữa bằng một ví dụ mà gợi ý làm thế nào nó sẽ được sử dụng trong chứng minh. Ví dụ 4.5: Xem xét các biểu thức chính quy 0 * (01) *. Hình 4-4a và 4-4b hiển thị các FA đơn giản tương ứng với hai biểu thức chính quy đang được nối với nhau. - 11 -Môn Lý Thuyết Tính Toán q0 0 (a) q1 q2 q3 1 0 0 0, 1 1 (b) q0 q1 q2 q3 0 0 0 0 0, 1 1 1 (c) 0 q0 q1 q2 q3 0 0 0 0, 1 1 1 ∧(d) Hình 4-4 Hình 4-4c minh hoạ một cách tương đối đơn giản của các kết hợp theo hình thức của một NFA chấp nhận ngôn ngữ L tương ứng với biểu thức 0*(01)*. Trạng thái q0 là một trạng thái thừa nhận với mọi chuỗi 0* trong ngôn ngữ L. Một trong những giải thích của biểu đồ là ở trạng thái q0, thiết bị sẽ đoán nhận như thế nào để giải quyết ký hiệu đầu vào 0. Có ba khả năng: sơ đồ có thể giải quyết ký hiệu đầu vào là 0 tương ứng với chuổi 0* và có thể tiếp tục thêm vào các ký hiệu 0 tương ứng với chuổi 0*; cuối cùng là 0 tương ứng với chuổi 0*; hoặc như là ký hiệu đầu tiên 0 của chuỗi 01. Trong hai trường hợp cuối cùng, bây giờ sơ đồ được chia nhỏ ra sử dụng cho bất kỳ đầu vào tiếp theo để cố gắng kết hợp phần thứ hai trong biểu thức chính quy. Nó không phải là khó khăn để thuyết phục mình rằng NFA này chấp nhận các ngôn ngữ L. Tuy nhiên, trong kết hợp của hai FA đơn giản, một số cấu trúc đã bị che khuất; mủi tên () là cần thiết để kết hợp chúng; và hiển nhiên nó không phải là ngay lập tức mà các ký hiệu là nhãn mũi tên phù hợp với hai biểu thức chính quy. Vì vậy, có lẽ một số nghi ngờ vào thời điểm này: như thế nào?, thậm chí có hay không?, cách tiếp cận này sẽ làm việc trong một tình huống tổng quát hơn. Một cách để giữ sự đơn giản của hai FA riêng lẽ trong quá trình kết hợp chúng là đưa ra các sơ đồ không xác định và ít tự do trong đoán nhận. Chúng ta có thể cho phép nó, trong khi ở trạng thái q0 để đoán rằng nó sẽ không nhận được nhiều đầu vào có thể kết hợp với 0*. Trong việc đoán nhận này nó cam kết chính nó để tiến tới phần thứ hai trong biểu thức chính quy gốc; Nó có thể làm điều này mà không có bất kỳ tham chiếu đến các cấu trúc thực tế của phần thứ hai; đặc biệt, nó có thể làm điều này mà không nhận được bất kỳ tại đầu vào , nhiều thứ giống nhau chỉ - 12 -Môn Lý Thuyết Tính Toánvới chuổi rỗng như đầu vào. Biểu đồ kết quả được hiển thị trong hình 4-4d. Lưu ý rằng mặc dù q0 là một trạng thái thừa nhận cần thiết trong NFA (trong hình 4-4c), nhưng nó không bắt buộc trong hình 4-d, vì nó không thêm đầu vào để sơ đồ có thể di chuyển từ q0 đến một trạng thái chấp nhận. Tóm lại, sơ đồ ở hình 4-4d là tổng quát hơn nhiều so với một NFA là nó được phép thực hiện quá trình dịch chuyển, không chỉ trên các ký hiệu đầu vào từ bảng chữ cái, mà cũng ngày đầu vào null. Định nghĩa 4.4 Một ôtômat hữu hạn không xác định với dịch chuyển -∧ (viết tắt là NFA- ∧ ) là một bộ năm (Q, ∑, q0, A, δ ) mà Q và ∑ là những tập đơn định q0 ∈ Q Như trước, chúng ta cần phải định nghĩa một chức năng mở rộng δ* để đưa ra một định nghĩa chính xác, chấp nhận của một chuỗi bởi một NFA- ∧ . Ý tưởng vẫn là δ* (q,x) là tập hợp của tất cả trạng thái trong đó NFA- ∧ có thể kết thúc đúng như kết quả của trạng thái bắt đầu q và xử lý các ký hiệu trong x. Tuy nhiên, bây giờ có phức tạp khác bởi vì xử lý các ký hiệu trong x là được phép đối với khả năng của dịch chuyển- ∧ , nó xen giữa các quá trình dịch chuyển bình thường. Hình 4-5 minh họa vấn đề này. Chúng ta muốn nói rằng chuỗi 01 được chấp nhận bởi vì 0∧∧1∧ = x và bắt đầu từ q0 đi qua năm đầu vào để đi đến trạng thái chấp nhận. Một lần nữa, chúng tôi bắt đầu với một định nghĩa không đệ quy, đơn giản, phỏng theo định nghĩa 4.2a. q0 r t u f Hình 4-5 Định nghĩa 4.5a ( định nghĩa ….không đệ quy cho một NFA-∧ ): Cho FA - ∧ M = (Q, ∑, q0 , A, δ ) với mọi p, q ∈Q và với mọi chuổi x= a1a2…an, ta nói M dịch chuyển từ p đến q bằng cách dịch chuyển tương ứng với x nếu tồn tại một số nguyên m≥n, và một dãy ký tự b1, b2…bm € ∑ U ∈ {A} thỏa mản b1b2 bm=x và một dãy các trạng thái p = p0, p1,…, pm =q với i € [1 m], pi (pi-1, bi). Cho x ∈ ∑* và p ∈ Q, δ *(p,x) thì tập hợp tất cả các trạng thái q ∈ Q là một sự dịch chuyển liên tục của M theo chuổi x từ p đến q Ví dụ: trong hình 4-5 tương ứng với sự dịch chuển liên tục theo chuổi 01 Từ q0 dến f ; có một sự dịch chuyển từ r đến t theo chuổi ∧ ; và cũng có một sự dich chuyển tư một trạng thái bất kỳ đến chính nó theo chuổi ∧ (chuổi rổng). Để đi đến một đinh nghĩa đệ quy là hơi khó khăn, phần định nghĩa đệ quy vẫn còn liên quan đến định nghĩa …cho một chuổi với một ký hiệu a thêm vào bảng chử cái. Tuy nhiên, nếu chúng ta biểu thị tập tất cả các trạng thái S mà các sơ đồ trước a được xử lý, chúng ta có được các thiết lập mới bằng cách cho phép tất cả các chuyển dịch có thể từ các phần tử của S trên đầu vào a cũng như tất cả các chuyển dich - ∧ tiếp theo. Điều này cho thấy rằng chúng ta cũng muốn sửa đổi một phần cơ bản của các định nghĩa đệ quy, do đó thiết lập …. Không chỉ chứa q mà chứa các trạng thái bất kỳ mà NFA- ∧ có thể đạt được từ q bằng cách dùng dịch chuyển ∧. Cả hai sửa - 13 -0( , , , , )M Q q Aδ= ΣMôn Lý Thuyết Tính Toánđổi có thể được mô tả trong giới hạn kết thúc(∧ -closure) của tập các trạng thái S. điều này chúng ta định nghĩa đệ quy định nghĩa trong 4.6, là tập hợp của tất cả các trạng thái có thể đạt được từ các phần tử của S bằng cách sử dụng các chuyển dịch- ∧ . Định nghĩa 4.6 ( ( ∧ - closure)kết thúc của tập các trạng thái ) Cho M= (Q, ∑ , q0, A, δ ) là một NFA - ∧ và S là một tập con bất kỳ của Q. ∧ - kết thúc (∧ - closure) của S là tập ∧ (S) định nghĩa như sau:1. mọi phần tử của S là một phần tử của ∧ (S)2. cho bất kỳ q ∈ ∧ (S), mổi phần tử của δ (q,∧) là trong ∧ (S)3. không có các phần tử khác của Q trong ∧ (S) Định nghĩa này khác với hầu hết cá định nghĩa đệ quy trước đâylà hữu hạn. Kết quả là, chúng ta có thể chuyển định nghia đệ quy sang thuật toán để tính toán ∧ (S) ( xem bài tập 2.50) Thuật toán để tính ∧ (S) : bắt đầu với T=S, tại mổi bước xem xét tất cả các tập δ (q,∧) , q ∈T, và thêm vào T phần tử bất kỳ không có trong T. dừng lại khi không thay đổi được T. Tập ∧ (S) là tập giá trị cuối cùng của T. -kết thúc ( ∧- closure) của một tập là thành phần thêm vào chúng ta cần phải định nghĩa hàm đệ quy δ * Nếu δ *(q,y) là một tập tất cả các trạng thái cần đạt được từ q, sử dụng các ký hiệu y như là một dịch chuyển-∧, lúc đó: *( , )( , )p q yp aδδ∈U Là tập tất cả các trạng thái mà chúng ta cần đạt được trong nhiều bước bằng cách sử dụng ký hiệu a. ∧ -kết thúc (∧- closure) của tập này gồm vài trạng thái khác mà chúng ta có thể đạt được nếu chúng ta cho phép dịch chuyển tiếp theo trong khi thêm. Định nghĩa 4.5b( định nghĩa đệ quy của δ* cho một NFA- ∧ ): Cho M= (Q, ∑ , q0, A, δ ) là một NFA- ∧ . Hàm dich chuyển mở rộng được định nghĩa như sau:1 cho bất kỳ q ∈ Q, δ*(q,∧)= ∧({q})2. cho bất kỳ q ∈ Q, y ∈ ∑*, và a ∈ ∑ **( , )( , ) ( , )p q yq ya p aδδ δ∈ = ∧   UMột chuổi xđược chấp nhận bởi M nếu δ* (q0, x) ∩ A ≠ Ө Ngôn ngữ chấp nhận M là tập L(M)tất cả các chuổi chấp nhận bởi M. Ví dụ 4.6: Chúng ta xem xét NFA -∧ trong hình 4-6. Đầu tiên là một minh họa về cách để áp dụng các thuật toán để tính toán ∧(S), và sau đó để chứng minh rằng định nghĩa 4.5b có thể tính toán - 14 -Môn Lý Thuyết Tính Toán Giả sử rằng chúng ta lấy S để được tập hợp {s}, sau lần thực hiện thứ nhất T là {s, w}, sau lần thực hiện thứ hai thì T là {s, w, q0} , sau lần thực hiện thứ ba thì T là {s, w, q0 , p, t}; và trong những lần thực hiện tiếp theo nó không thay đổi ∧({S}) cho nên T là {s, w, q0 , p, t}. chúng ta sử dụng định nghĩa đệ quy để tính toán δ*(q0,010) tập này đã được định nghĩa trong sự giới hạn của δ*(q0,01) đó là định nghĩa trong sự giới hạn của δ*(q0,0) Do đó chúng tôi tính toán từ dưới lên, tính δ*(q0,∧), δ*(q0,0) rồi tính δ*(q0,01) và cuối cùng là tính δ*(q0,010) *0 00( , ) ({ }){ , , }q qq p tδ∧ = ∧= q0 r s w t u v p ∧∧∧∧∧1 0 0 0 0 1 1 0 ( )s∧Hình 4-6 NFA- minh họa cho ví dụ 4-6 *0*0( , )0( ,0) ( ,0)( ( ,0) ( ,0) ( ,0))( { } { })({ , }){ , }qqq p tp up up uρ δδ δ ρδ δ δθ∈ ∧ = ∧   = ∧ ∪ ∪= ∧ ∪ ∪= ∧=U- 15 -∧Môn Lý Thuyết Tính Toán *0*0( ,0)0( ,01) ( ,1)( ( ,1) ( ,1))({ }){ }qqq urrρ δδ δ ρδ δ∈ = ∧   =∧ ∪=∧=U *0*0( ,01)0( ,010) ( ,0)( ( ,0))({ }){s,w, , , }qqrrq p tρ δδ δ ρδ∈ =∧   =∧=∧=UBởi vì δ*(q*,010) chứa w và w là một phần tử của A cho nên 010 được chấp nhận. Nhìn vào hình 4-6 bạn có thể chỉ rỏ theo dòng nay, thay vì chuổi ∧010∧ giống như chuổi 010, ta có sơ đồ sau của sự dich chuyển: 0 1 00wq p p r s∧ ∧→ → → → →do đó 010 được chấp nhận. Với ví dụ đơn giản này thì không cần thiết phải tính toán trước để quyết định chuổi có được chấp nhận hay không. Tuy nhiên với định nghĩa đệ quy của ∧(S) Và δ* Thì chúng ta có thể kiểm tra một chuổi có được chấp nhận hay không trên cơ sở của thuật toán. các tính toán phải khả thi và đưa ra được kết quả. Trong mục 4.1 chúng ta đã đưa ra định lý 4.1 nói rằng: NFA không mạnh hơn FA với cùng ngôn ngữ mà chúng chấp nhận. Để tạo ra kết quả tương đương với NFA - ∧, thì NFA- ∧ có khả năng đưa ra bất kỳ NFA- ∧ mà có thể thay thế bằng NFA tương ứng với nó. Định lý 4.2: Nếu L ⊆ ∑* là một ngôn ngữ được chấp nhận bởi NFA- ∧ M= (Q, ∑ , q0, A, δ ) thì có một NFA M= (Q1, ∑ , q1, A1, δ1) chấp nhận ngôn ngữ L. Chứng minh: trong chứng minh của định lý 4.1 chúng tôi bắt đầu với một NFA và loại bỏ tất cả các trường hợp không đơn định bằng cách thay thế trạng thái. ∧ là một ký hiệu không đơn định. Ví dụ: cho các dich chuyển trong M như sau: 0 p q r ∧- 16 -Môn Lý Thuyết Tính ToánLúc đó, bắt đầu từ p ta đưa vào ký tự 0 thì nó cho phép chúng ta hoặc đến q hoặc đến r. M1 là ô tô mat không đơn định, chúng ta có thể loại ra các dịch chuyển mà không làm thay đổi các trạng thái bằng cách thêm vào các dịch chuyển từ p đến r với ký tự vào 0. Đây là cách giải quyết tổng quát. Chúng ta có thể dùng các trạng thái trong tập Q của M1 và các trạng thái đầu giống nhau. Chúng ta phái định nghĩa được hàm dịch chuyển δ1 do đó nếu M cho phép chúng ta di chuyển từ p đến q bằng cách dùng các ký hiệu cùng với các dịch chuyển ∧ thì M1 cho phếp chúng ta di chuyển từ p đến q bằng cách dùng các ký hiệu đó mà không có các dịch chuyển ∧ . Thực ra, chúng ta đã có cách giải quyết mà kết quả là δ* cho NFA- ∧ M( định nghĩa 4.5b) đó là: cho một trạng thái q và một ký hiệu vào a ** *( , )({ })( , ) ( , )( , )( , )p qp qq a q ap ap aδδ δδδ∈ ∧∈∧= ∧ =∧    =∧  UU Nhắc lại, ({ })( , )p qp aδ∈∧U là tập hợp các trạng thái có thể đạt được từ q bằng cách dùng ký hiệu a nhưng cũng có thể sử dụng các dịch chuyển ∧ trước. Kết thúc ∧( ∧- closure) của tập này là tập các trạng thái cá thể đạt được từ q bằng cách dùng ký hiệu a nhưng cho phép sử dụng các dịch chuyển ∧ cả trước và sau. Chính xác chúng ta muốn δ1(q,a) để kết hợp với hàm dịch chuyển không đơn định mà bắt đầu từ các dịch chuyển Cuối cùng, có thay đổi nhỏ mà càn phải chỉ rỏ trong các trạng thái chấp nhận của M1 . Nếu q0 của M là trạng thái không chấp nhận nhưng từ q0 có thể có được trạng thái chấp nhận bằng cách dùng các dịch chuyển ∧, lúc đó q0 phải tạo ra những trạng thái chấp nhận trong M1δ*1(q0,∧) là {q0} bởi vì M1 là một NFA. Tóm lại, chúng ta phải chỉ ra rằng M1 sẽ là NFA, với bất kỳ q∈Q, a ∈ ∑ { }∪=δ=δAqAA)a,q()a,q(01*1Vấn đề của định nghĩa δ1 à chúng ta muốn δ1*(q,x) để có được tập các trạng thái mà M có thể đạt được từ q bằng cách dùng các ký hiệu trong chuổi x cùng với các dịch chuyển ∧. Nói cách khác, chúng ta muốn: * *1( , ) ( , )q x q xδ δ=- 17 -∧Môn Lý Thuyết Tính ToánNói chung nó không chính xác lắm, δ1*(q,∧) có thể khác δ*(q,∧) và đó chính là lý do của định nghĩa A1 ở trên, đó là một trường hợp ngoại lệ nhưng đúng Chứng minh bằng phương pháp quy nạp: tại mổi bước chúng ta kiểm tra. X = a ∈ ∑, trong trường hợp δ1 (q, a) = δ* (q, x) (định nghĩa δ1 ) và δ1 (q, a) = δ1*(q,a) (bởi vì M1 là NFA )(xem ví dụ 4.2 và bài tạp 4.2)) Trong bươc quy nạp chúng ta giả sử rằng ‌‌‌‌‌‌‌‌ |y| ≥ 1và δ1*(q,y) = δ*(q,y) với bất kỳ q ∈ Q chúng ta muốn chỉ ra rằng a ∈ ∑, δ1*(q, ya) = δ* (q, ya) ta có: Chúng ta sẽ đưa ra tập δ*(q,ya) lưu ý rằng ký hiệu này ∧ (∧- closure) là tập kết thúc ∧ (do định nghĩa δ*) và ở mổi tập δ*(q, a) thì ∧ cũng là ký hiệu kết thúc (do định nghĩa δ*). Cuối cùng nó tạo ra một tập hợp ( xem bài tập 4.21). Nói cách khác, tập cuối cùng mà chúng ta đưa ra bằng với tập δ*(q,ya) và ký hiệu kết thúc ∧ Chứng minh quy nạp thành công. Bây giờ thì không phải khó để đưa ra M1 chấp nhận L, mà L được chấp nhận bởi M. Đầu tiên chúng ta xem xét trường hợp ∧({ q0}) ∩ A≠ Ө trong M thì chuổi rỗng được chấp nhận bởi hoặc M hoặc M1, với bất kỳ chuổi x chúng ta đã chỉ ra rằng δ*1(q0, x) = δ*1(q0, x) và chúng ta biết rằng tập các trạng thái của M và M1 là giống nhau. Vì vậy, x được chấp nhận bởi M1 khi và chỉ khi x được chấp nhận bởi M. Trong trường hợp khác, khi tập ∧({ q0}) ∩ A≠ Ө, chúng ta định nghĩa tập A1 là A ∪{q0}. Lúc này ∧được chấp nhận bởi M và M1. Chúng ta cũng chỉ ra δ*1(q0, x) = δ*1(q0, x) với bất kỳ x. Nếu tập này (A1) chứa một trạng thái có trong A thì M và M1 chấp nhận x. Nếu không, x chỉ có thể được chấp nhận bởi hoặc M hoặc M1 nhưng không có cách khác để δ*(q0, x) chứa q0 (q0 có thể chưa trang A1 nhưng không chứa trong A). Tuy nhiên, nó không thể xảy ra cả hai trường hợp. Do định nghĩa δ*(q0, x) , ký hiệu∧ là kết thúc của tập hợp. Nếu δ*(q0, x) chứa q0 thì nó có thể chứa mọi phần tử của tập ∧({ q0}). Vì vậy, khi ∧({ q0}) ∩ A≠ Ө thì nó có thể chứa một phần tử của A. Trong cả hai trường hợp, chúng ta có thể kết luận rằng M và M1 chấp nhận những chuổi giống nhau. Chứng minh thành công. Một cách tổng quát, NFA thì giống như FA và NFA- ∧ thì giống như NFA. Về mặt kỷ thuật thì không hoàn toàn đúng để nói rằng mổi FA là Một NFA bởi ví giá trị của hàm dich chuyển là các trạng thái trong một trường hợp và tập các trạng thái là một trường hợp khác. Tương tự, miền của hàm dịch chuyển của NFA là Q x ∑, miền của hàm dịch chuyển của NFA- ∧ là.Q x (∑∪{A}) Thực ra, chúng ta có thể bỏ qua những kỷ thuật này. Định lý sau đây khẳng định rằng kết quả của định lý 4.1 và 4.2 ràng buộc lẫn nhau.- 18 -∧Môn Lý Thuyết Tính Toán Định lý 4.3 cho bảng chử cái bất kỳ ∑ và một ngôn ngữ L bất kỳ L∈∑* ta có ba phát biểu sau:1. L có thể được chấp nhận bởi một FA.2. L có thể được chấp nhận bởi một NFA.3. L có thể được chấp nhận bởi một NFA -∧ . Chứng minh: theo định lý 4.1 và 4.2 ta có: Phát biểu 3 bao hàm phát biểu 2 Phát biểu 2 bao hàm phát biểu 1Vì vậy, phát biểu 1 bao hàm phát biểu 3 Giả sử L được chấp nhận bởi FA M= (Q, ∑ , q0, A, δ ) chúng ta phải xây dựng một NFA-∧ M= (Q, ∑ , q0, A, δ1 ) chấp nhận L như sau: 1: ( { }) 2QQδ× Σ ∪ ∧ →Được định nghĩa bởi công thức: 11( , )( , ) { ( , )}qq q aδ θδ δ∧ =∧ = Với bất kỳ q ∈Q, a ∈∑ Công thức đầu tiên nói rằng: không có dịch chuyển ∧ trong M1 . Công thức thứ hai nói rằng: các hàm dich chuyển δ và δ1 là đồng nhất. Vì vậy không có NFA, nó có thể xác nhận ngay lập tức M1 chấp nhận L. ngoại trừ trường hợp giá trị là một trạng thái và trường hợp khác giá trị là một tập trạng thái.(xem bài tạp 4.19) Cũng như trong trường hợp của định lý 4.1 và chứng minh của định lý 4.2 đa cung cấp cho chúng ta một thuật khử dịch chuyển từ NFA - . Chúng ta đã làm rả thuật toán qua 2 ví dụ minh họa, chúng ta có thể luyện tập khử ô tô mat không đơn định. Ví dụ 4.7. M là NFA đưa ra trong hình 4-7a, nó chấp nhận ngôn ngữ {0}*{01}*{0}* chúng ta đưa ra dạng bảng giá trị của hàm dịch chuyển và các giá trị δ*(q,0), δ*(q,0) đưa lại cho chúng ta các giá trị của hàm dịch chuyển đối với NFA.qδ(q,∧) δ(q,0) δ(q,1) δ*(q,0) δ*(q,1)A {B} {A} θ {A, B, C, D} θB {D} {C} θ {C, D} θC θ θ {B} θ {B,D}D θ {D} θ {D} θVí dụ δ*(A,0) được tính bằng công thức. - 19 -∧∧Môn Lý Thuyết Tính Toán ∧A B D A ∧0 0 0 1 (a) 0 0 1 0 0 1 0 0 A B D C 0 (b) ABCD A BD BD D θ1 1 1 1 1 0 0 0 0, 1 0 0 (c) Hình 4-7: NFA - , NFA, và FA chấp nhận ngôn ngữ {0}*{01}*{0}* *({ })( ,0) ( , 0)p pA pδ δ∈∧ = ∧  UTrong nhiều ví dụ phức tạp chúng ta có thể tiến hành theo từng bước:- Để tính tập ∧ ({A}) , tìm δ(p,0) với mổi p thuộc tập nay.- Tạo thành một tập, tím ký hiệu kết thúc ∧ của tập kết quả.Trong ví dụ đơn giản này, chúng ta có thể thấy rằng từ A với đâu vào 0 thì M ở A di chuyển đến B ( dùng một ký hiệu 0 và một dịch chuyển ∧),để di chuyển đến C ( dùng một dịch chuyển ∧ và một ký hiệu 0) hoặc để dịch chuyển đến D ( dùng ký hiệu 0 thì hoặc là ngay lập tức đến D hoặc đến D qua hai dịch chuyển ∧). Với hai cột cuối trong bảng trên ta cũng đạt được điều tương tự. Khi M di chuyển từ trạng thái đầu tiên đến D chỉ dùng dịch chuyển A phải chấp nhận trạng thái trong M1, nó được đưa ra trong hình 4-7b. Giá trị của δ1(q, 0), δ1(q, 1) trong bảng là tiện lợi để đưa ra một FA. Ví dụ: (nếu chúng ta biểu diển hàm dịch chuyển của FA là δ2) để tính toán δ2({C,D},0) chúng ta kết hợp các tập trong hàng thứ ba và hàng thứ tư ( tương ứng với trạng thái C và D) của cột δ*(q, 0) trong bảng trên, kết quả là {D}. Kết quả của ví dụ này là tập các trạng thái mà chúng ta điền vào bảng cho NFA. Kết quả ta có được FA như trong hình 4-7c. Ví dụ 4.8: xét NFA- ∧ trong hình 4-8a, chấp nhận ngôn ngữ{0}*({01}*{1}U{1}*{0}). Chúng ta đưa ra hàm dịch chuyển ở dạng bảng, cũng như hàm dịch chuyển cho kết quả NFA- 20 -∧,∧*( ,0)qδMôn Lý Thuyết Tính Toán ∧C B A D 0 0 1 1 1 0 ∧(a) 0 1 1 0, 1 B C A D E 0 0 0 0, 1 0 1 (b) 0 0 0 0 0, 1 0 0,1 0 1 1 A BDE CE ABCD A DE E D B θ1 0 1 1 1 0 1 1 (c) Hình 4-8: NFA- ∧, NFA, FA chấp nhận ngôn ngữ {0}*({01}*{1} ∪ {1}*{0}). qδ (q,∧) δ (q,0) δ(q,1) δ*(q,0) δ*(q,1)A {B, D} {A} θ {A, B, C, D,E} {D, E}B θ {C} {E} {C} {E}C θ θ {B} θ {B }D θ {E} {D} {E} {D}E θ θ θ θ θ Hình 4-8b là NFA, lưu ý rằng trạng thái đầu A không được chấp nhận, vì từ sơ đồ đầu tiên một trạng thái chấp nhận không thể đạt được chỉ với các dịch chuyển ∧.- 21 -Môn Lý Thuyết Tính Toán Không giống như ví dụ 4.7 chúng ta khử không đơn định từ NFA, tập các trạng thái mới được đưa ra băng cách thêm vào các trạng thái. Ví dụ: Tính toán không phức tạp và kết quả được đưa ra trong hình 4.8c 22({ , , , },1) { , } { } { } { }{ , , }({ , , }, 0 ) { } { } { , }A B C D D E E B DB D EB D E C E C Eδ θδ θ= ∪ ∪ ∪ ∪== ∪ ∪ =4.3. Định lý KleeneHai mục đầu tiên của chương này đã cung cấp một số công cụ cho chúng ta dùng để chứng minh định lý 3.1. Để thuận tiện, chúng ta sẽ đi nói rõ hai phần, phần “Nếu” và phần “chỉ nếu”, khi các kết quả tách rời.Định lý 4.4 (Định lý Kleene, phần 1). Nhiều ngôn ngữ thông thường có thể được chấp nhận bởi ôtômat hữu hạn.Chứng minhBởi vì định lý 4.3, có khả năng để biểu diễn rằng mọi ngôn ngữ thông thường có thể được chấp nhận bởi một NFA-Λ. Một tập các ngôn ngữ thông thường trên bảng chữ cái Σ được định nghĩa trong chương 3 ( Định nghĩa 3.1) là tập ngôn ngữ nhỏ nhất mà chứa đựng các ngôn ngữ cơ bản Ø, {Λ}, và mỗi ngôn ngữ {a} (a Є Σ) được đóng dưới các phép tính: phép hợp, phép nối và phép toán Kleene. Việc sử dụng các cấu trúc quy nạp để chứng minh rằng mọi ngôn ngữ thông thường trên Σ được chấp nhận bởi một NFA- Λ. Bởi vậy, chúng ta phải trình bày 3 ngôn ngữ cơ bản có thể chấp nhận bởi một NFA- Λ, và rằng nếu L1 và L2 là các ngôn ngữ có thể chấp nhận và rồi các phép toán hợp, nối và định lý Kleene cũng có thể được chấp nhận a) b) c)Hình 4.9 NFA đối với 3 ngôn ngữ cơ bản thông thườngBây giờ giả sử rằng L1 và L2được đón nhận bởi NFA- Λ , M1 và M2tương ứng, cho mỗi i (1 và 2)Mi = ( Qi, Σ , qi , Ai, δi)- 22 -1( ,0)qδMôn Lý Thuyết Tính ToánBằng cách đổi tên trạng thái, nếu cần thiết, giả sử rằng Q1∩ Q2= Ø. Chúng ta sẽ xây dựng NFA- Λ là Mu, Mc, Mk, cho việc nhận dạng các ngôn ngữ L1 U L2, L1 L2, và L*1 tương ứng. Bởi vì các hình ảnh ở đây cũng hữu dụng, sơ đồ đại cương có mục đích di chuyển các ý chung trong mỗi trường hợp được trình bày ở hình 4-10. trong 3 phần của hình minh họa , cả hai M1 và M2 được trình bày khi có hai trạng thái chấp nhận.Cấu trúc của Mu= ( Qu, Σ , qu , Au, δu), chỉ ra qulà trạng thái mới, không như Q1 hoặc Q2, và :uQ= }{21 uqQQ uA=21AA  (a) (b)(c)Hình minh họa 4-10: NFA- Λ của phép hợp, phép giao và thuật toán KleeneBây giờ chúng ta sẽ định nghĩa δuđể Mu có thể di chuyển từ trạng thái ban đầu của nó đến có hoặc không có q1hoặc q2bởi một Λ chuyển tiếp và rồi di chuyển chính xác đến Mi tương ứng. Thông thường, chúng ta định nghĩa như sau:δu( qu, Λ) = ( q1, q2) δu( qu, a) = Ø với mọi a Є Σvà với mỗi q Є 21QQ U và a Є Σ U{ Λ}, =δ∈∈2Q q if a) (q, 2δ1Q q if a) (q, 1δ a) q, (u- 23 -Môn Lý Thuyết Tính ToánNếu 1L x ∈, thì Mucó thể xử lý x bằng cách di chuyển đến q1trên một chuyển tiếp Λ và thi hành việc di chuyển của M1 để nhận x. Tương tự, nếu 2L x ∈, thì x cũng được chấp nhận bởi Mu. Ngược lại, nếu x được chấp nhận bởi Mu, sự chuyển giao liên tiếp tương ứng với x, bắt đầu với quvà kết thúc với một phần tử của 1A và 2A. Cái đầu tiên của sự chuyển tiếp này phải được một chuyển tiếp Λ từ qu đến q1 hoặc q2, bởi vì không có một tiến trình khác từ qu. Sau đó, bởi vì θ=QQ21, hoặc có tất cả các tiến trình giữa các phần tử của Q1hoặc tất cả giữa của Q2. Theo sau x phải được chấp nhận hoặc M1 hoặc M2.Cấu trúc của Mc= ( Qc, Σ , qc , Ac, δc), trong trường hợp này chúng ta không cần các trạng thái mới. Cho Qc= 21QQ  và qc= q1.Cho Ac= A2(trong hình minh họa 4-10b, chúng ta minh họa vấn đề này bằng việc tạo cho 2f và '2f chấp nhận trạng thái trong Mc nhưng không chấp nhận 1f hoặc '1f). Các trạng thái sẽ bao gồm tất cả M1 và M2, như sự chuyển tiếp Λ từ trạng thái trong A1 đến q2, trong các lệnh khác cho tất cả q không ở trong A1, và ),q(},{cαδΛ∪∑∈α được định nghĩa có thể có )α,q(δ1hoặc )α,q(δ2, phụ thuộc vào việc có hay không có q trong Q1hoặc Q2. Cho q ∈ A1,)α,q(δc=)α,q(δ1, cho ∑∈ a và )Λ,q(δc= )Λ,q(δ1{ }2q∪Trên một chuỗi vào 21xx, nơi iiL x ∈ cho cả hai giá trị của i, Mc có thể xử lý 1x, tiến đến ở trạng thái trong A1, nhảy từ trạng thái này đến q2bởi một chuyển giao Λ, và rồi xử lý 2x theo lối M2, để mà 21xx được chấp nhận. Ngược lại, nếu xđược chấp nhận bởi Mc, sự chuyển giao liên tiếp tương ứng với xđược bắt đầu ở q1 và kết thúc ở nguyên tố ở A2. Một trong số chúng phải được xây dựng từ một phần tử của Q1đến một phần tử của Q2, và theo định nghĩa của δcnày thì chỉ có thể là một chuyển giao Λ từ phần tử của A1đến q2. Bởi vì θ=∩21QQ, tất cả các chuyển giao về trước là ở giữa các phần tử của Q1và tất cả các chuyển giao kéo theo sau là nằm giữa các phần tử của Q2. Theo sau là 2121xx= xΛ x= x, nơi mà 1x được chấp nhận bởi M2, trong các lệnh khác , 21LL x∈.Cấu trúc của Mk= ( Qk, Σ , qk , Ak, δk). Cho Qk= Q1}q{k∪, nơi mà qklà trạng thái mới không ở trong Q1. Trạng thái qksẽ chỉ là phần tử của Ak. Trở lại, tất cả các chuyển tiếp của M1 sẽ vẫn được cho phép trong Mk. Thêm vào đó có một sự chuyển giao Λ từ mỗi phần tử của A1cho đến qk. Đúng hơn}q{=)Λ,q(δ1kk và θ=)a,q(δkk cho ∑∈aCho 1Qq ∈ và ),q(),q( },{1kαδ=αδΛ∪∑∈α trừ phi 1Aq∈ và Λ=αCho 1Aq∈, }q{),q(),q(k1k∪Λδ=ΛδGiả sử *1Lx ∈. Nếu Λ=x, thì làm rõ x được chấp nhận bởi Mk.Cách khác, cho 1≥m, m21x xx=x, nơi mà 1iLx ∈ đối với i. Việc sử dụng một chuyển giao Λ, Mk có thể di chuyển từ kq cho đến 1q đối với mọi i, Mk di chuyển từ 1q đến một phần tử if của A1bởi sự chuyển giao liên tục tương ứng đến ix và đối với mọi i, rồi Mkdi chuyển từ if quay lại kq bởi một chuyển giao Λ. Theo sau x=)ΛxΛ) (ΛxΛ)(ΛxΛ(m21 được chấp nhận bởi Mk. Ngược lại, nếu x được chấp nhận bởi Mk, sự thường xuyên liên tục tương - 24 -Môn Lý Thuyết Tính Toánứng đến x bắt đầu và kết thúc ở kq. Bởi vì chỉ có sự chuyển giao từ kqlà một chuyển giao Λ đến 1q và chỉ các chuyển giao đến kq là chuyển giao Λ từ các phần tử của A1, xđược phân tích theo dạng sau:)ΛxΛ) (ΛxΛ)(ΛxΛ(=xm21Đối với mọi I, sự thường xuyên liên tục tương ứng đến ix từ 1q đến một phần tử của A1. Cho nên *1Lx ∈.Kể từ khi chúng ta xây dựng một NFA- Λ thừa nhận L trong mỗi 3 trường hợp, việc chứng minh đã hoàn tất.Các cấu trúc trong phần chứng minh trong định lý 4.4 cung cấp một giải thuật cho việc xây dựng một NFA- Λ tương ứng đối với biểu thức thông thường. Ví dụ kế tiếp minh họa ứng dụng của nó và sự thật rằng có thể có khả năng đơn giản hơn phụ thuộc vào cách này.Ví dụ 4.9: Cho r là một biểu thức đơn giản (00+1)*(10)*.Chúng ta minh họa các ứng dụng bằng chữ của thuật toán. Ban đầu (hoạt động 0) biểu thức thông thường xuất hiện trong r được trình bày trong minh họa 4-11a. NFA- Λ tương ứng 00 và 10 bây giờ được xây dựng nối vào nhau và được trình bày trong minh họa 4-11b.Kế tiếp, chúng ta định dạng NFA- Λ tương ứng (00+1), như trong minh họa 4-11c. Minh họa 4-11d và 4-11e minh họa NFA- Λ tương ứng (00+1)* và (10)*, theo thứ tự. Cuối cùng kết quả NFA- Λ được thực thi bởi sự kết hợp được trình bày trong hình minh họa 4-11f.Chắc chắn rõ ràng in một vài nơi mà các trang thái và sự chuyển giao nhìn chung việc xây dựng là không thực sự cần thiết trong ví dụ này. 6 phần của hình minh họa 4-12 song song với hình minh họa 4-11 và sự kết hợp chặt chẽ, rõ ràng và đơn giản. Một số trong chúng phải cẩn thận với quá trình đơn giản hóa như sau, như các ví dụ 4.35 đến 4.37. a) b) c) d) e) f)- 25 -

Tài liệu liên quan

• Tài liệu Tiểu luận "Hoàn thiện hạch toán chi phí sản xuất và tính giá thành sản phẩm tại công ty TNHH Tuấn Phương" docx
  • 123
  • 383
  • 2
• Tài liệu TIỂU LUẬN: Điều tra tình hình phát sinh, phát triển và mức độ gây hại của bệnh héo rũ trên cây cà chua, khoai tây vụ Đông Xuân 2001 2002 vùng Đông Anh - Hà Nội pdf
  • 43
  • 956
  • 1
• TIỂU LUẬN:HỌC THUYẾT CHÍNH DANH CỦA KHỔNG TỬ pot
  • 14
  • 3
  • 20
• Tiểu luận: Học thuyết hình thái – kinh tế xã hội và sự vận dụng trong quá trình đổi mới của Việt Nam hiện nay
  • 32
  • 2
  • 8
• Tiểu luận: Công tác kế toán chi phí sản xuất và tính giá thành sản phẩm của doanh nghiệp doc
  • 32
  • 376
  • 1
• TIỂU LUẬN MÔ HÌNH TÍNH TOÁN HƯỚNG DỊCH VỤ
  • 20
  • 425
  • 2
• Tính toán lượng không khí khô và nhiệt cho đồ án sấy
  • 7
  • 402
  • 0
• TIỂU LUẬN LÝ THUYẾT TÍNH TOÁN Ôtômát không đơn định và định lý KLEENE
  • 36
  • 1
  • 0
• Lý thuyết về máy Turning không đơn định, vạn năng và bài tập về kỹ thuật dịch chuyển RASP (TIỂU LUẬN LÝ THUYẾT TÍNH TOÁN)
  • 20
  • 804
  • 0
• TIỂU LUẬN MÔN HỌC TÍNH TOÁN CÁC BÀI TOÁN ĐỊA KỸ THUẬT BẰNG CHƯƠNG TRÌNH PLAXIS
  • 13
  • 787
  • 1

Tài liệu bạn tìm kiếm đã sẵn sàng tải về

(2.31 MB - 36 trang) - TIỂU LUẬN LÝ THUYẾT TÍNH TOÁN Ôtômát không đơn định và định lý KLEENE Tải bản đầy đủ ngay ×