Tài liệu Về otomat hữu hạn và ngôn ngữ chính quy

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN Nguyễn Thị Huyền VỀ OTOMAT HỮU HẠN VÀ NGÔN NGỮ CHÍNH QUY KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Hà Nội – Năm 2016 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN Nguyễn Thị Huyền VỀ OTOMAT HỮU HẠN VÀ NGÔN NGỮ CHÍNH QUY Chuyên ngành: Toán ứng dụng KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: TSKH. Kiều Văn Hưng Hà Nội – Năm 2016 Lời cảm ơn Để hoàn thành khóa luận tốt nghiệp này, em xin bày tỏ lòng biết ơn chân thành tới các thầy giáo và cô giáo trong Khoa Toán – Trường Đại học Sư phạm Hà Nội 2, đã tận tình giúp đỡ chỉ bảo trong suốt thời gian em theo học tại khoa và trong thời gian làm khóa luận. Đặc biệt em xin bày tỏ lòng biết ơn sâu sắc tới TS. Kiều Văn Hưng – người thầy đã trực tiếp hướng dẫn em, luôn tận tâm chỉ bảo và định hướng cho em trong suốt quá trình làm khóa luận để em có được kết quả như ngày hôm nay. Mặc dù đã có rất nhiều cố gắng, song thời gian và kinh nghiệm bản thân còn nhiều hạn chế nên khóa luận không thể tránh khỏi những thiếu sót rất mong được sự đóng góp ý kiến của các thầy cô giáo, các bạn sinh viên và bạn đọc. Em xin chân thành cảm ơn! Hà Nội, ngày 02 tháng 05 năm 2016 Sinh viên Nguyễn Thị Huyền i Lời cam đoan Khóa luận này là kết quả nghiên cứu của bản thân em dưới sự hướng dẫn tận tình của thầy giáo TS. Kiều Văn Hưng. Trong khi nghiên cứu hoàn thành đề tài nghiên cứu này em đã tham khảo một số tài liệu đã ghi trong phần tài liệu tham khảo. Em xin khẳng định kết quả của đề tài "Về otomat hữu hạn và ngôn ngữ chính quy" là kết quả của việc nghiên cứu, học tập và nỗ lực của bản thân, không có sự trùng lặp với kết quả của các đề tài khác. Nếu sai em xin chịu hoàn toàn trách nhiệm. Hà Nội, 02 tháng 05 năm 2015 Sinh viên Nguyễn Thị Huyền ii Mục lục Lời mở đầu ii Danh mục các kí hiệu và chữ viết tắt iv 1 Otomat hữu hạn 1 1.1 Otomat hữu hạn đơn định . . . . . . . . . . . . . . . . . 1.1.1 Otomat hữu hạn đơn định . . . . . . . . . . . . . 1.1.2 Biểu diễn Otomat hữu hạn đơn định . . . . . . 1.1.3 Ngôn ngữ được đoán nhận bởi otomat đơn định 1.2 Otomat hữu hạn không đơn định . . . . . . . . . . . . . 1.2.1 Otomat hữu hạn không đơn định . . . . . . . . . 1.2.2 Biểu diễn otomat hữu hạn không đơn định 1.2.3 Ngôn ngữ được đoán nhận bởi otomat hữu hạn không đơn định 1.2.4 . . . 1 1 2 6 9 9 11 . . . . . . . . . . . . . . . . . . 12 Đơn định hóa các otomat . . . . . . . . . . . . . 14 1.3 Sự tương đương giữa otomat hữu hạn đơn định và otomat hữu hạn không đơn định . . . . . . . . . . . . . . . . . . 2 Ngôn ngữ chính quy và biểu thức chính quy i 17 19 NGUYỄN THỊ HUYỀN Khóa luận tốt nghiệp Đại học 2.1 Ngôn ngữ chính quy và biểu thức chính quy . . . . . . . 19 2.2 23 Sự liên hệ giữa otomat hữu hạn và ngôn ngữ chính quy 3 Bài tập 31 Tài liệu tham khảo 41 ii NGUYỄN THỊ HUYỀN Khóa luận tốt nghiệp Đại học Lời mở đầu Ngôn ngữ là một phương tiện để giao tiếp, sự giao tiếp có thể hiểu là giao tiếp giữa con người với nhau, giao tiếp giữa người với máy hay giao tiếp giữa máy với máy. Nếu như ngôn ngữ mà con người có thể giao tiếp với nhau được gọi là ngôn ngữ tự nhiên, thì ngôn ngữ mà chúng ta vẫn thường sử dụng để giao tiếp với máy, hay giữa máy với máy được gọi là ngôn ngữ hình thức. Con người muốn máy tính thực hiện công việc phải viết các yêu cầu đưa cho máy bằng ngôn ngữ máy hiểu được. Việc viết các yêu cầu như thế gọi là lập trình. Ngôn ngữ dùng để lập trình được gọi là ngôn ngữ lập trình. Các ngôn ngữ lập trình đều là ngôn ngữ hình thức. Trong đó, otomat và ngôn ngữ hình thức là một nội dung khá mới mẻ giúp chúng ta hiểu sâu hơn về cấu trúc ngôn ngữ lập trình, đặc biệt nội dung otomat hữu hạn và ngôn ngữ chính quy là một nội dung khá hay đối với em. Xuất phát từ sự yêu thích đối với chuyên ngành Toán Ứng dụng và lòng đam mê nghiên cứu khoa học, em đã chọn để tài Về otomat hữu hạn và ngôn ngữ chính quy để làm nội dung nghiên cứu khóa luận tốt nghiệp. Otomat hữu hạn là một mô hì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ữ được đoán nhận bởi otomat hữu hạn khá đơn giản , đó chính là lớp ngôn ngữ chính quy do văn phạm chính quy sinh ra. Khóa luận gồm ba chương. iii NGUYỄN THỊ HUYỀN Khóa luận tốt nghiệp Đại học Chương 1 "Otomat hữu hạn" trình bày về một mô hình máy trừu tượng để đoán nhận ngôn ngữ, đó chính là các otomat hữu hạn. Chương 2 "Ngôn ngữ chính quy và biểu thức chính quy" sẽ định nghĩa các ngôn ngữ chính quy trực tiếp từ các khái niệm về ngôn ngữ. Đồng thời với các ngôn ngữ chính quy, chúng ta đưa ra khái niệm về biểu thức chính quy là công cụ để biểu diễn các ngôn ngữ chính quy. Chương 3 "Bài tập " đưa ra 8 bài tập minh họa cho các nội dung kiến thức được đưa ra trong Chương 1 và Chương 2. Tác giả khóa luận chân thành cảm ơn TS Kiều Văn Hưng đã tận tình hướng dẫn tác giả đọc các tài liệu và tập dượt nghiên cứu. Tác giả chân thành cảm ơn các thầy cô giáo Khoa Toán trường Đại học Sư phạm Hà Nội 2, đặc biệt là tổ Ứng dụng, đã tạo điều kiện thuận lợi cho tác giả trong quá trình học Đại học và thực hiện bản khóa luận này. Hà Nội, ngày 02/05/2016 Tác giả khóa luận NGUYỄN THỊ HUYỀN iv NGUYỄN THỊ HUYỀN Khóa luận tốt nghiệp Đại học Danh mục các kí hiệu và chữ viết tắt R tập số thực Rn không gian Euclid n chiều ∅ tập rỗng x∈M x thuộc tập M x∈ /M x không thuộc tập M ∀ x ∈ M với mọi x thuộc tập M ∃x tồn tại x M ∩N giao của hai tập hợp M và N M ∪N hợp của hai tập hợp M và N M \N hiệu của hai tập hợp M và N M ⊂N M là một tập con thực sự của N M ⊆N M là một tập con của N v Chương 1 Otomat hữu hạn 1.1 1.1.1 Otomat hữu hạn đơn định Otomat hữu hạn đơn định Định nghĩa 1.1 Một otomat hữu hạn đơn định hay một DFA ( Deteministic Finite Automata) là một bộ năm A =< Q, X , δ, q0, F > trong đó + Q là một tập hữu hạn khác rỗng, được gọi là tập các trạng thái; P + là một bảng chữ cái, được gọi là bảng chữ vào; P +δ : D → Q , là một ánh xạ từ D vào Q, trong đó D ⊆ Q × , được gọi là hàm chuyển trạng thái (hay hàm chuyển); +q0 ∈ Q , được gọi là trạng thái khởi đầu; +F ⊆ Q , được gọi là tập các trạng thái kết thúc. P Trong trường hợp D = Q × , ta nói A là otomat đầy đủ. Sau này ta sẽ thấy rằng mọi otomat hữu hạn đều đưa được về otomat hữu hạn đầy 1 NGUYỄN THỊ HUYỀN Khóa luận tốt nghiệp Đại học đủ tương đương. Khi bắt đầu làm việc, otomat ở trạng thái khởi đầu q0 và đầu đọc đang nhìn vào ô có kí hiệu a1 . Tiếp theo otomat chuyển từ trạng thái q0 dưới tác động của kí hiệu vào a1 về trạng thái mới δ(q0, a1 ) = q1 ∈ Q và đầu đọc chuyển sang phải một ô, tức là nhìn vào ô có kí hiệu a2 . Sau đó otomat A có thể lại tiếp tục chuyển từ trạng thái q1 nhờ hàm chuyển δ về trạng thái mới q2 = δ(q1 , a2) ∈ Q . Quá trình đó sẽ tiếp tục cho tới khi gặp một trong các tình huống sau : - Otomat A đọc hết sâu vào ω và δ(qn−1, an ) = qn ∈ F , ta nói rằng A đoán nhận xâu ω - Hoặc otomat A đọc hết sâu vào ω và δ(qn−1, an ) = qn ∈ / F , ta nói A không đoán nhận sâu ω . - Hoặc khi otomat A đọc đến aj , (j ≤ n) và hàm δ(qj−1, aj ) không xác định, ta cũng nói A không đoán nhận xâu ω . Hình 1.1: Mô tả quá trình đoán nhận xâu ω của otomat A 1.1.2 Biểu diễn Otomat hữu hạn đơn định Ánh xạ chuyển là một bộ phận quan trọng của một otomat hữu hạn đơn định. Nó có thể cho dưới dạng bảng chuyển hoặc dưới dạng đồ thị. 1, Phương pháp cho bảng chuyển P Cho otomat A =< Q, , δ, q0, F > và Q = {q0, q1, ..., qm} là tập trạng 2 NGUYỄN THỊ HUYỀN Khóa luận tốt nghiệp Đại học thái, và bảng chữ cái P = {a0 , a1 , ..., am} , khi đó ánh xạ chuyển có thể cho bởi bảng sau ; trong đó dòng i, cột j của bảng là ô trống nếu (qi, aj ) ∈ / D , tức là δ(qi , aj ) không xác định. Hình 1.2: Bảng chuyển trạng thái của otomat A Khi cho bảng chuyển trạng thái, và chỉ rõ tập trạng thái kết thúc F, ta sẽ xác định được otomat A. 2, Phương pháp cho bằng đồ thị chuyển P Cho otomat A =< Q, , δ, q0, F > . Ánh xạ chuyển δ có thể cho bằng một đa đồ thị có hướng, có khuyên G sau đây, được gọi là đồ thị chuyển của otomat A. Tập đỉnh của G được dán nhãn bởi các phần tử thuộc P Q, còn các cung được gán nhãn bởi các phần tử thuộc , tức là nếu P a ∈ và từ trạng thái q chuyển sang trạng thái p theo công thức δ(q, a) = p thì sẽ có một cung từ đỉnh q tới đỉnh p được gán nhãn a. Đỉnh vào của đồ thị chuyển là đỉnh ứng với trạng thái ban đầu q0 . Các đỉnh sẽ được khoanh bởi các vòng tròn, tại đỉnh q0 có một mũi tên đi vào, riêng đỉnh với trạng thái kết thúc được phân biệt bởi các vòng tròn đậm hoặc hình vuông ... Nói chung với việc cho đồ thị chuyển là hoàn toàn xác định được otomat 3 NGUYỄN THỊ HUYỀN Khóa luận tốt nghiệp Đại học A. Ví dụ 1.1 Cho hai otomat hữu hạn đơn định : 1/. A1 =< {q0 , q1, q2} , {a, b,} , δ, q0, {q2} > trong đó δ(q0 , a) = q0 , δ(q0, b) = q0 , δ(q1, a) = q0 , δ(q1, b) = q2 , δ(q2, a) = q2 , δ(q2 , b) = q2 . Ta có bảng chuyển trạng thái và đồ thị chuyển trạng thái của otomat A1 như sau : Hình 1.3: Bảng chuyển trạng thái của A1 Hình 1.4: Đồ thị chuyển trạng thái của A1 Dãy trạng thái của otomat A1 trong quá trình đoán nhận xâu vào α = ababbab là : 4 NGUYỄN THỊ HUYỀN Khóa luận tốt nghiệp Đại học Hình 1.5: Quá trình đoán nhận xâu α = ababbab của A1 Như vậy , xâu α được đoán nhận bởi otomat A1 . 2, A2 =< {q0, q1, q2, q3} , {0, 1} , q0, {q0 } > , trong đó δ(q0 , 0) = q2 , δ(q0 , 1) = q1 , δ(q1, 0) = q3 , δ(q1, 1) = q0 , δ(q2, 0) = q0 , δ(q2 , 1) = q3 , δ(q3, 0) = q1 , δ(q3 , 1) = q2 . Ta có bảng chuyển trạng thái của otomat A2 như sau : . Hình 1.6: Bảng chuyển trạng thái của A2 Đồ thị chuyển trạng thái của otomat A2 như sau : Hình 1.7: Đồ thị chuyển trạng thái của A2 Như vậy otomat A2 không chấp nhận xâu β . 5 NGUYỄN THỊ HUYỀN Khóa luận tốt nghiệp Đại học 1.1.3 Ngôn ngữ được đoán nhận bởi otomat đơn định Để mô tả hình thức quá trình đoán nhận một từ, người ta đưa vào ánh P ∗ xạ mở rộng δ1 từ D ⊆ Q × vào Q như trong định nghĩa sau : P Định nghĩa 1.2 Cho otomat hữu hạn đơn định A =< Q, , δ, q0, F >, P mở rộng δ1 của δ là một ánh xạ từ D ⊆ Q × vào Q được xác định như sau : 1/. δ1 (q, ε) = q, ∀q ∈ Q . 2/. δ1 (q, ωa) = δ(δ1(q, ω), a), ∀a ∈ P ∗ sao cho δ1 (q, ω) được xác định. Chú ý : Do δ1 (q, a) = δ(δ1(q, εa)) = δ(δ1 (q, ε), a) = δ(q, a) . Ta có thể đồng nhất δ1 với δ . Nếu không cần phân biệt, từ đây về sau ta viết P δ thay cho δ1 , và được hiểu là ánh xạ δ trên miền Q × là ánh xạ P ∗ . δ1 trên miền Q × P Định nghĩa 1.3 Cho otomat hữu hạn đơn định A =< Q, , δ, q0, F >, P ∗ , và một xâu ω ∈ . Ta nói : + ω được đoán nhận bởi A nếu δ(q0, ω) ∈ F ; + Ngôn ngữ được đoán nhận bởi otomat A và kí hiệu là T(A), là tập từ: T (A) = ( ω∈ ∗ X |δ (q0 , ω) ∈ F Lưu ý rằng trong đồ thị chuyển của A, ω ∈ P∗ ) được đoán nhận bởi A khi và chỉ khi ω là xâu của các nhãn ứng với một đường đi từ đỉnh q0 đến một trong các đỉnh kết thúc. Cụ thể, nếu ω = a1 a2 ....an thì đường đi là (qn−1, qi) có nhãn ai với 1 ≤ i ≤ k và qk ∈ F . Như vậy T(A) là tập hợp tất cả các xâu ghi trên các đường đi từ q0 đến các đỉnh kết thúc 6 NGUYỄN THỊ HUYỀN Khóa luận tốt nghiệp Đại học P Định nghĩa 1.4 Hai otomat hữu hạn A =< Q, , δ, q0, F > và A1 =< P Q1, 1,δ1, q01 , F1 > được gọi là tương đương nếu T (A) = T (A1) . Ví dụ 1.2 Cho otomat hữu hạn : A3 =< {q0 , q1, q2, q3, q4} , {0, 1} , δ, q0, {q1 , q2, q4} > với δ(q0 , 0) = q0 , δ(q0, 1) = q1 , δ(q1, 1) = q3 , δ(q1 , 1) = q2 , δ(q2 , 0) = q2 , δ(q2, 1) = q2 , δ(q3, 1) = q3 , δ(q4 , 0) = q2 , δ(q4, 1) = q3 . Đồ thị chuyển A3 là : Hình 1.8: Đồ thị chuyển trạng thái của A3 Trước hết ta nhận thấy rằng không có đường đi từ q0 đến đỉnh kết thúc q4 , tức là sẽ không có từ nào được đoán nhận từ A3 với đỉnh kết thúc q4 . Ngoài ra cũng không có một đường đi nào từ q0 đến đỉnh một đỉnh kết thúc mà đi qua q3 . Như vậy, ta có thể bỏ qua đỉnh q3 và q4 mà không ảnh hưởng đến việc đoán nhận các từ của otomat A3 . Do đó otomat A3 tương đương với otomat A4 như sau : A4 =< {q0 , q1, q2} , {0, 1} , δ, q0, {q1, q2} > trong đó δ(q0 , 0) = q0 , δ(q0 , 1) = q1 , δ(q1 , 1) = q2 , δ(q2, 1) = q2 . Đồ thị chuyển của A4 được cho trong hình 1.9 7 NGUYỄN THỊ HUYỀN Khóa luận tốt nghiệp Đại học Hình 1.9: Đồ thị chuyển trạng thái của A4 Các đường đi từ q0 đến đỉnh kết thúc q1 ứng với các xâu 0n 1 , n ≥ 0 . Các đường đi từ q0 đến đỉnh kết thúc q2 ứng với các xâu 0n11 ω , n ≥ 0 , ω ∈ {0, 1}∗ .Vậy ngôn ngữ được đoán nhận bởi các otomat trên là : T (A3) = T (A4) = {0n1, 0n11ω/n ≥ 0, ω ∈ {0, 1}∗ } Bổ đề 1.1 P Cho otomat hữu hạn đơn định A =< Q, , δ, q0, F > . Khi đó ∀ω1 , ω2 ∈ P∗ , ∀q ∈ Q sao cho δ(q1 , ω1ω2) xác định, ta có : δ(q1 , ω1ω2) = δ(δ(q1 , ω1), ω2) Chứng minh : Ta chứng minh đẳng thức trên bằng quy nạp theo độ dài của ω2 . + Khi |ω2 | = 1 hay ω2 = a, a ∈ Đẳng thức (1) đúng. P , ta có δ(q1 , ω1a) = δ(δ(q1, ω1), a) . + Giả sử đẳng thức (1) đúng với mọi ω2 có độ dài |ω2 | ≤ n . Ta cần chứng minh nó cũng đúng với ω2 có độ dài |ω2 | = n + 1 . P P . Ta có δ(q, ω1ω2 ) = Đặt ω2 = ω21 a , với ω21 ∈ ∗ , |ω21| = n , a ∈ δ(q, ω1ω21 a) = δ(δ(q, ω1ω2 1 ), a) = δ(δ(δ(q, ω1), ω21 ), a) = δ(δ(q, ω1), ω21a) = δ(δ(q, ω1), ω2). 8 NGUYỄN THỊ HUYỀN Khóa luận tốt nghiệp Đại học Do đó đẳng thức (1) đúng với ω2 có độ dài n+1. Bổ đề được chứng minh. Chú ý : Với otomat hữu hạn đơn định A =< Q, P , δ, q0, F > bất kì, ta luôn có thể xây dựng một otomat hữu hạn đơn định đầy đủ A1 tương đương với A. 1.2 1.2.1 Otomat hữu hạn không đơn định Otomat hữu hạn không đơn định Định nghĩa 2.1 Một otomat hữu hạn không đơn định ( Nondeterministic Finite Automata - NFA) là một bộ năm A =< Q, X , δ, q0, F >, trong đó P + Q, , q0, F như trong định nghĩa 1.1 P + δ : Q× → 2Q , ở đây 2Q , (hay P(Q) , là kí hiệu tập hợp các tập con của Q ), gọi là ánh xạ chuyển. Ở đây, ánh xạ δ là một hàm đa trị ( hàm không đơn định), vì vậy otomat A trong định nghĩa trên được gọi là không đơn định . P Trong trường hợp δ(q, a) xác định với ∀q ∈ Q, ∀a ∈ , ta nói otomat A là đầy đủ. Nếu δ(q, a) = {p1 , p2, ..., pk } thì ta nói rằng otomat A ở trạng thái q gặp kí hiệu a thì có thể chuyển đến một trong các trạng thái p1 , p2, ..., pk . Nếu δ(q, a) = {p} thì ở trạng thái q gặp kí hiệu a, otomat A chỉ chuyển 9 NGUYỄN THỊ HUYỀN Khóa luận tốt nghiệp Đại học đến một trạng thái duy nhất p. Nếu δ(q, a) = ∅ thì ở trạng thái q gặp kí hiệu a, otomat A không thể chuyển đến trạng thái nào, cũng tương tự như với otomat hữu hạn đơn định. Như vậy, ta thấy rằng một otomat hữu hạn đơn định là một trường hợp đặc biệt của một otomat hữu hạn không đơn định. Hoạt động của otomat hữu hạn không đơn định A =< Q, P , δ, q0, F > khi cho vào xâu ω = a1 a2 ...an có thể được mô tả như sau : Khi bắt đầu làm việc, otomat ở trạng thái đầu q0 và đầu đọc đang nhìn vào ô có kí hiệu a1 . Từ trạng thái q0 , dưới tác động của kí hiệu vào a1 , δ(q0, a1 ) = {p1, p2,...,pk } , otomat xác định các trạng thái có thể tiếp theo là p1 , p2, ..., pk và đầu đọc chuyển sang phải một ô, tức là nhìn vào ô có kí hiệu a2 . Tiếp tục với mỗi qi (i ≤ 1 ≤ k) và kí hiệu tiếp theo là a2 , các trạng thái tiếp theo có thể đến được là δ(p1, a2 ) ∪ ... ∪ δ(pk , a2 ) . Quá trình đó sẽ được tiếp tục cho tới khi gặp một trong các tình huống sau : + Trong trường hợp tập trạng thái tiếp theo sau khi đọc aj nào đó là rỗng hoặc sau khi đọc kí hiệu an là Q1 mà Q1 ∩ F = ∅ , ta nói rằng A không đoán nhận xâu ω . + Trong trường hợp tập trạng thái tiếp theo sau khi đọc kí hiệu an là Q1 mà Q1 ∩ F 6= ∅ , ta nói rằng otomat A đoán nhận xâu ω . 10 NGUYỄN THỊ HUYỀN Khóa luận tốt nghiệp Đại học 1.2.2 Biểu diễn otomat hữu hạn không đơn định Một otomat hữu hạn không đơn định có thể biểu diễn dưới dạng bảng chuyển hoặc đồ thị chuyển như trong trường hợp otomat hữu hạn đơn định. Nếu δ(q, a) = {p1 , p2, ..., pk } thì trong đồ thị chuyển có k cung từ q sang p1, p2, ..., pk được ghi cùng một nhãn a. Quá trình đoán nhận một xâu vào ω của một otomat hữu hạn không đơn định A có thể biểu diễn bằng một cây có gốc mà gốc là trạng thái đầu q0 . Trong cây này, nếu có một đường đi qua một dãy các trạng thái ứng với xâu vào ω từ q0 đến một lá chứa trạng thái kết thúc thì xâu vào này được đoán nhận bởi otomat A. Ngược lại nếu không có một lá nào trong cây chứa trạng thái kết thúc thì ω không được đoán nhận bởi A. Ví dụ 1.3 Cho otomat hữu hạn không đơn định : A =< {q0 , q1, q2, q3, q4} , {0, 1} , δ, q0, {q2 , q4} > , với δ(q0 , 0) = {q0 , q3} , δ(q0 , 1) = {q0, q1} , δ(q1, 0) = ∅ , δ(q1, 1) = {q2} , δ(q2, 0) = {q2 } , δ(q2 , 1) = {q2} , δ(q3, 0) = {q4 } , δ(q3, 1) = ∅ , δ(q4, 0) = {q4} , δ(q4, 1) = {q4 } . Cho xâu vào ω = 01001 . Ta có cây đoán nhận ω như sau : Trong cây trên có một đường đi từ q0 đến q4 ∈ F nên xâu ω = 01001 là xâu được đoán nhận bởi otomat A. Đồ thị chuyển của otomat A là : 11