Tài liệu ôtômát hữu hạn và ứng dụng

TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN ====== TRẦN THỊ THU THỦY ÔTÔMÁT HỮU HẠN VÀ ỨNG DỤNG KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Toán ứng dụng HÀ NỘI - 2017 TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN ====== TRẦN THỊ THU THỦY ÔTÔMÁT HỮU HẠN VÀ ỨNG DỤNG KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Toán ứng dụng Người hướng dẫn khoa học TS. KIỀU VĂN HƯNG HÀ NỘI - 2017 Khóa luận tốt nghiệp Trần Thị Thu Thủy LỜI CẢM ƠN Trước hết em xin gửi lời cảm ơn đến thầy Kiều Văn Hưng, người đã hướng dẫn em rất nhiều trong suốt quá trình nghiên cứu và hoàn thành khóa luận. Sự hướng dẫn của thầy đã giúp em có những hiều biết về một số vấn đề liên quan đến ôtômát. Đồng thời em cũng xin gửi lời cảm ơn chân thành đến các thầy cô bộ môn cũng như các thầy cô trong trường đã trang bị cho em những kiến thức cơ bản cần thiết để em có thể hoàn thành khóa luận này. Em xin gửi lời cảm ơn đến các thành viên lớp K39A_Toán, những người bạn đã động viên tạo điều kiện để em có thể nghiên cứu và hoàn thành khóa luận. Sau cùng em xin gửi lời cảm ơn đến gia đình luôn bên cạnh ủng hộ em học tập và nghiên cứu. Hà Nội, Ngày 23 tháng 04 năm 2017 Sinh viên Trần Thị Thu Thủy Khóa luận tốt nghiệp Trần Thị Thu Thủy LỜI CAM ĐOAN Khóa luận này là kết quả của bản thân em trong quá trình nghiên cứu. Bên cạnh đó, được sự quan tâm hướng dẫn của các thầy cô trong khoa toán, đặc biệt là sự hướng dẫn nhiệt tình của thầy giáo Kiều Văn Hưng. Trong quá trình nghiên cứu hoàn thành khóa luận em có tham khảo một số tài liệu ghi được ghi trong phần tài liệu tham khảo. Em xin cam đoan kết quả đề tài “ ÔTÔMÁT HỮU HẠN VÀ ỨNG DỤNG “ không có sự trùng lặp cũng như sao chép đề tài khác. Nếu sai em xin hoàn toàn chịu trách nhiệm. Người cam đoan Sinh viên Trần Thị Thu Thủy Khóa luận tốt nghiệp Trần Thị Thu Thủy MỤC LỤC MỞ ĐẦU ........................................................................................................... 1 CHƯƠNG 1: LÝ THUYẾT MỞ ĐẦU ............................................................. 3 1.1. Ngôn ngữ .................................................................................................... 3 1.1.1 Bảng chữ cái ............................................................................................. 3 1.1.2 Xâu ........................................................................................................... 3 1.1.3 Các phép toán trên xâu ............................................................................. 4 1.1.4 Ngôn ngữ .................................................................................................. 6 1.1.5 Các phép toán trên ngôn ngữ ................................................................... 6 CHƯƠNG 2 : ÔTÔMÁT HỮU HẠN............................................................. 11 2.1 Ôtômát ...................................................................................................... 11 2.1.1 Một số khái niệm .................................................................................... 11 2.1.2 Ôtômát .................................................................................................... 11 2.1.3 Hoạt động của ôtômát ............................................................................ 12 2.1.4 Phân loại ôtômát ..................................................................................... 13 2.2 Ôtômát hữu hạn đơn định......................................................................... 14 2.2.1 Ôtômát hữu hạn đơn định....................................................................... 14 2.2.2 Hoạt động của ôtômát hữu hạn đơn định ............................................... 14 2.2.3 Biểu diễn ôtômát hữu hạn đơn định ....................................................... 15 2.2.4 Hoạt động đoán nhận xâu....................................................................... 17 2.2.5 Ngôn ngữ được đoán nhận bởi ôtômát đơn định ................................... 18 2.3 Ôtômát hữu hạn không đơn định............................................................... 19 2.3.1 Ôtômát hữu hạn không đơn định ........................................................... 19 Khóa luận tốt nghiệp Trần Thị Thu Thủy 2.3.2 Hoạt động của ôtômát hữu hạn không đơn định .................................... 19 2.3.3 Biểu diễn một ôtômát hữu hạn không đơn định..................................... 20 2.3.4 Hoạt động đoán nhận xâu....................................................................... 21 2.3.5 Ngôn ngữ được đoán nhận bởi ôtômát không đơn định ........................ 22 2.4 Sự tương đương giữa ôtômát hữu hạn đơn định và ôtômát hữu hạn không đơn định ........................................................................................................... 22 2.4.1 Sự tương đương giữa ôtômát hữu hạn đơn định và ôtômát hữu hạn không đơn định................................................................................................ 22 2.4.2 Xây dựng ôtômát hữu hạn đơn định từ ôtômát hữu hạn không đơn định ......................................................................................................................... 24 CHƯƠNG 3: MỘT VÀI ỨNG DỤNG CỦA ÔTÔMÁT HỮU HẠN ........... 26 3.1 Ứng dụng trong máy tính .......................................................................... 26 3.1.1 Tìm kiếm xâu trong văn bản .................................................................. 26 3.1.2 Tìm kiếm văn bản................................................................................... 27 3.1.3 Nhận diện một bộ từ khóa ...................................................................... 28 3.1.4 Bộ phân tích từ vựng .............................................................................. 29 3.1.5 Trình soạn thảo văn bản ......................................................................... 30 3.2 Ứng dụng thực tế ....................................................................................... 31 3.2.1 Máy giặt.................................................................................................. 31 3.2.2 Máy bán hàng tự động............................................................................ 32 KẾT LUẬN ..................................................................................................... 33 TÀI LIỆU THAM KHẢO ............................................................................... 34 Khóa luận tốt nghiệp Trần Thị Thu Thủy MỞ ĐẦU 1. Lý do chọn đề tài Ngày nay chúng ta chứng kiến sự phát triển mãnh liệt trong các lĩnh vực nghiên cứu toán học liên quan đến tin học và máy tính. Sự phát triển của máy tính và những thay đổi sâu sắc liên quan đến phương pháp luận khoa học đã mở ra chân trời mới cho toán học với một tốc độ không thể sánh được trong suốt chiều dài lịch sử toán học. Những phát triển của toán học đã mở ra thuở ban đầu cho tin học và máy tính, các tiến bộ trong tin học đã dẫn đến sự phát triển rất mạnh mẽ một số ngành toán học. Lý thuyết ngôn ngữ hình thức và ôtômát đóng một vai trò quan trọng trong các cơ sở toán học của tin học. Vì vậy em mạnh dạn nghiên cứu chuyên đề “ ÔTÔMÁT HỮU HẠN VÀ ỨNG DỤNG”. 2. Mục đích nghiên cứu Tìm hiểu một cách tổng quan về ôtômát hữu hạn, là công cụ sinh ngôn ngữ. Ngoài ra tìm hiểu một số ứng dụng của ôtômát hữu hạn. 3. Đối tượng và phạm vi nghiên cứu Đối tượng: các kiến thức cơ bản về ôtômát hữu hạn. Phạm vi: Nội dung kiến thức trong phạm vi của lí thuyết ngôn ngữ hình thức và ôtômát. 4. Nhiệm vụ Tìm hiểu về lí thuyết ôtômát hữu hạn và ứng dụng. 5. Phương pháp nghiên cứu Phương pháp nghiên cứu lí luận. 1 Khóa luận tốt nghiệp Trần Thị Thu Thủy Khóa luận được trình bày trong 3 chương với nội dung mỗi chương như sau: Chương 1: Kiến thức mở đầu Chương 2: Ôtômát hữu hạn Chương 3 : Một vài ứng dụng của ôtômát hữu hạn 2 Khóa luận tốt nghiệp Trần Thị Thu Thủy CHƯƠNG 1: LÝ THUYẾT MỞ ĐẦU Chương thứ nhất trình bày các kiến thức cơ sở cần thiết, được sử dụng trong các chương tiếp theo của khóa luận. Ở đó ta nhắc một số khái niệm về ngôn ngữ. 1.1. Ngôn ngữ 1.1.1 Bảng chữ cái Định nghĩa 1.1 Tập  khác rỗng gồm hữu hạn hay vô hạn kí hiệu được gọi là bảng chữ cái. Mỗi phần tử a   được gọi là một chữ cái hay một kí hiệu. Ví dụ 1.1 Dưới đây là các bảng chữ cái 1. { A, B, ….., Z}: Bảng chữ cái latinh. 2. {α, β, γ……,φ}: Bảng chữ cái Hi Lạp. 3. {I, V, X, L, C, D, M}: Bảng chữ số La Mã. 4. {0, 1, 2,…., 9}: Bảng chữ số thập phân. 1.1.2 Xâu Định nghĩa 1.2 Bảng chữ cái  = { a1, a2, ……, an }, một dãy chữ cái α = ai1ai2ai3.....aim, Với aij   (1 ≤ 𝑗 ≤ 𝑚 ) được gọi là một xâu trên bảng chữ cái . Tổng số vị trí xuất hiện trong xâu α được gọi là độ dài xâu α và kí hiệu là |α|. Vậy một xâu trên bảng chữ cái  gồm một số lớn hơn hay bằng không các chữ cái của , trong đó một chữ có có thể xuất hiện một hay nhiều lần. Xâu không có chữ cái nào được gọi là xâu rỗng, kí hiệu là ε. |ε| = 0. Tập mọi từ trên bảng chữ cái  được kí hiệu là * , còn tập mọi từ khác rỗng trên bảng chữ cái  kí hiệu là +. Như vậy  + = *\{ε} và * = +  {ε}. 3 Khóa luận tốt nghiệp Trần Thị Thu Thủy Ví dụ 1.2 1. Cho  = {a, b, c} thì ε, abc, aab, acc, aabbc là các xâu trên . 2. Cho  = {0, 1} thì 01, 00, 11, 101, 0011 là các xâu trên . Quy ước: Chúng ta sẽ sử dụng các chữ cái thường a, b, c, ….. cho các phần tử của bảng chữ cái , còn các chữ cái u, v, ω,….. cho tên các xâu. 1.1.3 Các phép toán trên xâu I. Phép nhân ghép Định nghĩa 1.3 Tích ghép (hay nhân ghép) của hai xâu α = a1a2….am và xâu β = b1b2….bn trên bảng chữ cái , là xâu γ = a1a2……amb1b2……bn trên bảng chữ cái . Kí hiệu phép nhân ghép là γ = α.β ( hay γ = αβ). Nhận xét Từ định nghĩa ta có • Xâu rỗng là phần tử đơn vị của phép nhân ghép. • Phép nhân ghép có tính chất kế hợp. • Kí hiệu ωn, với n là số tự nhiên, được dùng với định nghĩa thông. thường : 𝜀 𝑘ℎ𝑖 𝑛 = 0 ω = { 𝜔 𝑘ℎ𝑖 𝑛 = 1 𝜔𝑛−1 𝜔 𝑘ℎ𝑖 𝑛 > 1 n • Đối với phép nhân ghép thì hàm độ dài có một số tính chất hình thức của lôgarit: với mọi xâu α, β và mọi số tự nhiên n thì |αβ| = |α| + |β|. |αn| = n|α|. Phần tử đơn vị ε, |ε| = 0. Ví dụ 1.3 Cho  = {a,b}, khi đó 1. Xâu α = abababaa, xâu β = aabb thì γ = αβ = abababaaaabb. 4 Khóa luận tốt nghiệp Trần Thị Thu Thủy 2. Xâu α = aababb có chứa 2 vị trí ab, khi đó là a*ab*ab*b , xâu φ = ab là xâu con của α. 3. Ω = 010111001 trên bảng chữ cái  = {0, 1} thì 0101 là tiền tố và 11001 là hậu tố. II. Phép lấy xâu ngược Định nghĩa 1.4 Cho bảng chữ cái , xâu ω = a1a2.....an khác rỗng, khi đó anan-1.....a1 được gọi là phép lấy xâu ngược của ω, kí hiệu ωR hay ω^. Nhận xét Phép lấy xâu ngược có các tính chất sau: • (ωR)R = ω. • (αβ)R = βRαR. • |αR| = |α|. Ví dụ 1.4 1. Cho xâu ω = 0101001 thì ωR = 1001010. 2. Cho α = 100110 và β = abab trên bảng chữ cái  = {0, 1, a, b}, theo định nghĩa ta có αR = 011001, βR = baba và (αβ)R = βRαR = baba011001. 3. Trên bảng chữ cái  = {a, b, c,......., z} cho xâu ω = yes khi đó ωR = sey và |ωR| = 3. III. Phép chia xâu Định nghĩa 1.5 Phép chia xâu trái của xâu α cho xâu β ( hay thương bên trái của α và β) cho kết quả là phần còn lại của xâu α sau khi cắt bỏ phần đầu β trong xâu α, và được ký hiệu là β\α. Định nghĩa 1.6 Phép chia xâu phải của xâu α cho xâu γ ( hay thương bên phải của α và γ) cho kết quả là phần kết quả là phần còn lại sau khi cắt bỏ phần cuối γ trong xâu α, và được kí hiệu là α/γ. 5 Khóa luận tốt nghiệp Trần Thị Thu Thủy Ví dụ 1.5 Bảng chữ cái  = {a,b,c}, cho các xâu α = abcaaabbbc, β = ab, γ = bbc, khi đó ta có 1. β\α = caaabbbc. 2. α/γ = abaaab. 3. (β\γ)R = cbbbaaac. 1.1.4 Ngôn ngữ Định nghĩa 1.7 Bảng chữ cái , mỗi tập con L  * là một ngôn ngữ trên bảng chữ cái . Tập rỗng, kí hiệu là , là một ngôn ngữ không gồm một từ nào và được gọi là ngôn ngữ rỗng. Ngôn ngữ rỗng là ngôn ngữ thuộc mọi bảng chữ cái. Chú ý ngôn ngữ L =  khác với ngôn ngữ L chỉ gồm một xâu rỗng L = {ε}. Ví dụ 1.6 1. * là ngôn ngữ gồm tất cả các xâu trên bảng chữ cái , còn + là ngôn ngữ gồm tất cả các xâu khác rỗng trên . 2. Cho  = {0, 1} thì L = { ε, 0, 1, 01, 001, 010} là ngôn ngữ trên . 3. Cho  = {a, b} thì L = {aa, bab, bba} là ngôn ngữ trên . 1.1.5 Các phép toán trên ngôn ngữ I. Phép hợp Định nghĩa 1.8 Hợp của hai ngôn ngữ L1 và L2 trên bảng chữ cái , kí hiệu là L1L2, là một ngôn ngữ trên bảng chữ cái  đó là tập : L= {ω  *| ω  L1 hoặc ω  L2}. Định nghĩa phép hợp có thể mở rộng cho hữu hạn ngôn ngữ L1, L2, ......., Ln trên bảng chữ cái  là tập : L = { ω  *| ω  Li, với i nào đó, 1 ≤ 𝑖 ≤ 𝑛}. Nhận xét phép hợp các ngôn ngữ có các tính chất sau: • Phép hợp hai ngôn ngữ có tính chất giao hoán. 6 Khóa luận tốt nghiệp Trần Thị Thu Thủy • Phép hợp hai ngôn ngữ có tính chất kết hợp. • Với ngôn ngữ L trên  thì L = L = L = L và L *= *. Ví dụ 1.7 Cho bảng chữ cái  ={a, b}, ngôn ngữ L1 = {a,b, ab, aab, abb, aba} và ngôn ngữ L2 = {ε, ab, aab, abb}, khi đó ta có L1L2 = {ε, a, b, ab, aab, abb, aba, abb}. II. Phép giao Định nghĩa 1.9 Giao hai ngôn ngữ L1 và L2 trên bảng chữ cái , kí hiệu là L1L2 là một ngôn ngữ trên bảng chữ cái , đó là tập: L = { ω  * | ω  L1 và ω  L2 }. Định nghĩa phép giao có thể mở rộng cho một số hữu hạn các ngôn ngữ tức giao của các ngôn ngữ L1, L2,……., Ln trên bảng chữ cái  là tập từ L = { ω  * | ω  Li, với mọi i, 1 ≤ 𝑖 ≤ 𝑛}. Nhận xét Phép giao các ngôn ngữ có các tính chất sau • Phép giao hai ngôn ngữ có tính chất giao hoán. • Phép giao hai ngôn ngữ có tính chất kết hợp. • Phép giao hai ngôn ngữ có tính chất phân phối đối với phép hợp: ( L1  L2 )  L3 = ( L1  L2 )  ( L1  L3). (L1  L2)  L3 = ( L1  L3 )  ( L2  L3). • Với mọi ngôn ngữ L trên bảng chữ cái  thì : L   =   L =  và L  * = L. Ví dụ 1.8 Bảng chữ cái  = {0, 1}, cho ngôn ngữ L1 = {ε, 0, 1, 01} và ngôn ngữ L2 = {ε, 1, 01, 10}, khi đó ta có : L1L2 = {ε, 1, 01}. 7 Khóa luận tốt nghiệp III. Trần Thị Thu Thủy Phép lấy phần bù Định nghĩa 1.10 Ngôn ngữ phần bù của ngôn ngữ L trên bảng chữ cái , kí hiệu là CL ( hay đơn giản là CL, nếu không gây nhầm lẫn), là một ngôn ngữ trên bảng chữ cái , đó là tập: CL = {ω  * | ω  L }. Nhận xét Phép lấy phần bù có các tính chất sau • C{ε} = +, C+ = {ε}. • C = *, C* = . • C(CL1  CL2) = L1L2. Ví dụ 1.9 Cho bảng chữ cái  = {a, b, c, d}, L = {a, d}, khi đó ta có: CL = {b, c}. IV. Phép nhân ghép Định nghĩa 1.11 Cho hai ngôn ngữ L1 trên bảng chữ cái 1 và L2 trên bảng chữ cái 2. Nhân ghép L1 và L2 là một ngôn ngữ trên bảng chữ cái 12, ký hiệu là L1L2, được xác định : L1L2 = {αβ | α  L1 và β  L2}. Nhận xét Phép nhân ghép có các tính chất sau: • Phép nhân ghép có tính chất kết hợp. • Phép nhân ghép có tính chất phân phối đối với phép hợp. Ví dụ 1.10 Trên bảng chữ cái  = {0, 1}, ngôn ngữ L1 = {0, 1, 01, 10} và ngôn ngữ L2 = {001}, khi đó ta có: L1L2 = {0001, 1001, 01001, 10001}. 8 Khóa luận tốt nghiệp V. Trần Thị Thu Thủy Phép lặp Định nghĩa 1.12 Cho ngôn ngữ L trên bảng chữ cái , khi đó ta có:  • Tập {ε}  L  L2 ……..  Ln …. = n0 Ln được gọi là tập ngôn ngữ lặp của ngôn ngữ L ( hay bao đóng của ngôn ngữ L ), ký hiệu L*.  • Tập L  L ………L = n Ln được gọi là ngôn ngữ lặp cắt của 1 2 n L, kí hiệu L+. Ví dụ 1.11 Bảng chữ cái  = {a, b}, khi đó ta có: L2 = {aa, ab, ba, bb}, tập hợp các xâu độ dài 2. L3 = {aaa, aab, aba, abb, baa, bab, bba, bbb}, tập hợp các xâu độ dài 3. Tương tự, Ln tập hợp các xâu độ dài n. Vậy L* là tập hợp tất cả xâu . VI. Phép lấy ngược ngôn ngữ Định nghĩa 1.13 Cho ngôn ngữ L trên bảng chữ cái , khi đó ngôn ngữ ngược của ngôn ngữ L là một ngôn ngữ trên bảng chữ cái , được kí hiệu là LR, hay L^ là tập: LR = { ω  * | ωR  L}. Nhận xét phép hợp ngôn ngữ có các tính chất sau: • (LR)R = L. • {ε}R = {ε}. • ()R = . Ví dụ1.12 Cho L = { ε, a, b, ab, abb} trên bảng chữ cái  = {a, b}, khi đó ta có LR ={ε, a, b, ba, bba}. VII. Phép chia ngôn ngữ 9 Khóa luận tốt nghiệp Trần Thị Thu Thủy Định nghĩa 1.14 Cho ngôn ngữ X và ngôn ngữ Y trên bảng chữ cái , khi đó thương bên trái của ngôn ngữ X cho ngôn ngữ Y là một ngôn ngữ trên , được kí hiệu là Y\X, là tập: Y\ X = {z   * | x  X, y  Y mà x=yz}. Định nghĩa 1.15 Cho ngôn ngữ X và ngôn ngữ Y trên bảng chữ cái , khi đó thương bên phải của ngôn ngữ X cho ngôn ngữ Y là một ngôn ngữ trên , được kí hiệu là X/Y, là tập : X /Y = {z  *| x  X, y  Y mà x = zy}. Nhận xét phép chia ngôn ngữ có các tính chất • {ε}\ • \ L L = L/{ε} = L. = L/ = L. Ví dụ 1.13 Cho ngôn ngữ X = {a,b,ab,abc} và ngôn ngữ Y = {ε, c} trên bảng chữ cái  = {a, b, c}, khi đó : 1. Y\X = {a,b,ab,abc,c}. 2. X/Y = {a,b,ab,abc,c}. 10 Khóa luận tốt nghiệp Trần Thị Thu Thủy CHƯƠNG 2 : ÔTÔMÁT HỮU HẠN Chúng ta sẽ tìm hiểu về một định nghĩa tổng quát nhất của ôtômát và sau đó thu hẹp cho phù hợp với các ứng dụng của khoa học máy tính. 2.1 Ôtômát 2.1.1 Một số khái niệm Định nghĩa 2.1 Trạng thái nội Là một trạng thái của đơn vị điều khiển mà ôtômát có thể ở vào. Định nghĩa 2.2 Trạng thái kế Là một trạng thái nội của đơn vị điều khiển mà ôtômát có thể ở vào thời điểm kế tiếp. Định nghĩa 2.3 Hàm chuyển trạng thái Là hàm đưa ra trạng thái kế của ôtômát dựa trên trạng thái hiện hành, kí hiệu nhập hiện hành được quét và thông tin hiện hành trong bộ nhớ tạm. Định nghĩa 2.4 Cấu hình Được sử dụng để tham khảo đến bộ ba thông tin : trạng thái cụ thể mà đơn vị điều khiển đang ở vào, vị trí của cơ cấu nhập trên thiết bị nhập ( hay nói cách khác ôtômát đang đọc đến kí hiệu nào của thiết bị nhập), và nội dung hiện hành của bộ nhớ tạm. Định nghĩa 2.5 Di chuyển Là sự chuyển trạng thái của ôtômát từ cấu hình hiện hành sang cấu hình kế tiếp. 2.1.2 Ôtômát Định nghĩa 2.6 Ôtômát là máy tự động, là thiết bị có thể thực hiện công việc mà không cần sự can thiệp của con người. Hoạt động dựa trên một số quy tắc và dựa vào các quy tắc này con người lập trình cho nó hoạt động theo ý muốn của mình. Ví dụ 2.1 Máy tính ngày nay chính là một máy tự động điển hình 11 Khóa luận tốt nghiệp Trần Thị Thu Thủy Ôtômát bao gồm các thành phần Input file  Control unit  Storage  Output Trong đó : • Thiết bị đầu vào ( input file) Là nơi các xâu được nhập và được ôtômát đọc nhưng không thay đổi được nội dung của nó. Nó được chia thành các ô và mỗi ô giữ được một kí hiệu. • Bộ nhớ tạm ( storage) Là thiết bị bao gồm một số không giới hạn các ô nhớ, mỗi ô có thể giữ một kí hiệu từ bảng chữ cái ( không nhất thiết giống với bảng chữ cái ngõ nhập) . Ôtômát có thể đọc và thay đổi nội dung các ô nhớ lưu trữ. • Đơn vị điều khiển ( control unit) Mỗi ôtômát có một đơn vị điều khiển cái mà có thể ở trong một trạng thái bất kì trong trạng thái nội, và có thể chuyển đổi trạng thái trong một kiểu được định nghĩa sẵn nào đó. • Dữ liệu ra (out put) là kết quả trả về của ôtômát. Ngoài ra ôtômát có một cơ cấu nhập: là bộ phận để đọc input file từ trái sang phải, một kí tự tại một thời điểm. Nó cũng có thể dò tìm được điểm kết thúc của xâu nhập. 2.1.3 Hoạt động của ôtômát Một ôtômát được giả thiết là hoạt động trong một khung thời gian rời rạc. 12 Khóa luận tốt nghiệp Trần Thị Thu Thủy Tại một thời điểm bất kì đã cho, đơn vị điều khiển đang ở trong một trạng thái nội nào đó, và cơ cấu nhập là đang quét một kí hiệu cụ thể nào đó trên input file. Trạng thái nội của đơn vị điều khiển tại thời điểm kế tiếp được xác định bởi trạng thái kế hay bởi hàm dịch chuyển trạng thái. Trong suốt quá trình chuyển trạng thái từ khoảng thời gian này đến khoảng thời gian kế, kết quả có thể sinh ra và thông tin trong bộ nhớ lưu trữ có thể được thay đổi. 2.1.4 Phân loại ôtômát Chúng ta có hai cách phân loại ôtômát, dựa theo hoạt động của ôtômát và dựa vào kết quả xuất ra. Đầu tiên, dựa theo hoạt động của ôtômát có hai loại : • Ôtômát đơn định : Là ôtômát mà mỗi dịch chuyển được xác định duy nhất bởi cấu hình hiện tại. Sự duy nhất này thể hiện tính đơn định. • Ôtômát không đơn định : Là ôtômát mà tại mỗi thời điểm nó có một vài khả năng lựa chọn di chuyển. Việc có một vài khả năng lựa chọn thể hiện tính không đơn định. Dựa vào kết quả xuất ra có hai loại : • Accepter : Là ôtômát mà đáp ứng ngõ ra của nó được giới hạn trong hai trạng thái đơn giản ‘ yes’ or ‘ no’ . ‘Yes’tương ứng với việc chấp nhận chuỗi, ‘no’ tương ứng với việc từ chối, không chấp nhận, chuỗi nhập. • Transducer : Là ôtômát tổng quát hơn, có khả năng sinh ra các xâu kí tự ở ngõ xuất. Máy tính số là một transducer điển hình. 13 Khóa luận tốt nghiệp Trần Thị Thu Thủy Sau đây chúng ta xét định nghĩa ôtômát hữu hạn trạng thái gọi tắt là ôtômát hữu hạn 2.2 Ôtômát hữu hạn đơn định 2.2.1 Ôtômát hữu hạn đơn định Định nghĩa 2.7 Một ôtômát hữu hạn đơn định ( Deterministic finite automata- DFA) là một bộ năm : A = ( Q, , δ, q0, F) Trong đó : ❖ Q là một tập hữu hạn khác rỗng, được gọi là tập trạng thái. ❖  là một bảng chữ cái được gọi là bảng chữ vào. ❖ δ: 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. Trong trường hợp D = Q, ta nói A là ôtômát đầy đủ. Nhận xét ❖ Như vậy ta thấy trạng thái của ôtômát chỉ thay đổi khi có dữ liệu vào. ❖ ∀ ω  A*, a  A, δ(q, aω) = δ(δ(q, a), ω), δ(q, ωa) = δ(δ(q, ω), a) Ví dụ 2.1: Cho DFA : A= (Q, , δ, q0, F) với = {0,1} Q= {0,1} q0 = 0 F= {1} δ: (δ(0,0) = 0, δ(0,1) = 1, δ(1,0) = 0, δ(1,1)=1). 2.2.2 Hoạt động của ôtômát hữu hạn đơn định Khi cho xâu vào ω = a0a1….an có thể được mô tả như sau: 14