Đăng ký Đăng nhập
Trang chủ Giáo dục - Đào tạo Cao đẳng - Đại học Sư phạm Luận văn otomat hữu hạn và ứng dụng trong phân tích từ vựng...

Tài liệu Luận văn otomat hữu hạn và ứng dụng trong phân tích từ vựng

.PDF
69
205
126

Mô tả:

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 NGUYỄN DIỆU LINH OTOMAT HỮU HẠN VÀ ỨNG DỤNG TRONG PHÂN TÍCH TỪ VỰNG LUẬN VĂN THẠC SĨ TOÁN HỌC Hà Nội - 2018 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 NGUYỄN DIỆU LINH OTOMAT HỮU HẠN VÀ ỨNG DỤNG TRONG PHÂN TÍCH TỪ VỰNG Chuyên ngành: Toán ứng dụng Mã số: 8460112 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: TS. KIỀU VĂN HƯNG Hà Nội - 2018 LỜI CẢM ƠN Luận văn được hoàn thành tại Trường Đại học Sư phạm Hà Nội 2. Tác giả chân thành cảm ơn TS. Kiều Văn Hưng đã tận tình hướng dẫn, tạo điều kiện cho tác giả hoàn thành luận văn Thạc sĩ. Tác giả xin bày tỏ lòng biết ơn các thầy cô giáo và cán bộ công nhân viên của Trường Đại học Sư phạm Hà Nội 2 đã quan tâm giúp đỡ. Hà Nội, ngày 08 tháng 06 năm 2018 Tác giả luận văn Nguyễn Diệu Linh LỜI CAM ĐOAN Tôi xin cam đoan luận văn này là kết quả nghiên cứu của riêng tôi dưới sự hướng dẫn của TS. Kiều Văn Hưng. Trong quá trình nghiên cứu, tôi đã kế thừa thành quả khoa học của các nhà khoa học với sự trân trọng và biết ơn. Các kết quả trích dẫn trong luận văn này đã được chỉ rõ nguồn gốc. Hà Nội, ngày 08 tháng 06 năm 2018 Tác giả luận văn Nguyễn Diệu Linh Mục lục MỞ ĐẦU 5 1 Otomat hữu hạn 7 1.1. Kiến thức cơ sở . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.1. Bảng chữ, từ, ngôn ngữ . . . . . . . . . . . . . . . 8 1.1.2. Ngôn ngữ chính quy và biểu thức chính quy . . . 12 1.2. Otomat hữu hạn . . . . . . . . . . . . . . . . . . . . . . 15 1.2.1. Otomat hữu hạn đơn định . . . . . . . . . . . . . 15 1.2.2. Otomat hữu hạn không đơn định . . . . . . . . . 21 1.2.3. Sự tương đương giữa otomat đơn định và không đơn định . . . . . . . . . . . . . . . . . . . . . . . 24 1.2.4. Quan hệ giữa otomat hữu hạn và ngôn ngữ chính quy . . . . . . . . . . . . . . . . . . . . . . . . . . 27 1.2.5. Định lý Myhill – Nerode và tối thiểu hóa otomat hữu hạn . . . . . . . . . . . . . . . . . . . . . . . 30 2 Ứng dụng của otomat hữu hạn trong phân tích từ vựng 38 2.1. Tổng quan về ứng dụng của otomat . . . . . . . . . . . . 3 38 2.1.1. Thiết kế và kiểm tra hoạt động của các mạch số . 39 2.1.2. Tìm kiếm từ trong văn bản . . . . . . . . . . . . 40 2.2. Phân tích từ vựng . . . . . . . . . . . . . . . . . . . . . . 46 2.2.1. Vai trò của bộ phân tích từ vựng . . . . . . . . . 46 2.2.2. Lưu trữ tạm chương trình nguồn . . . . . . . . . 50 2.2.3. Nhận dạng token . . . . . . . . . . . . . . . . . . 53 2.2.4. Ngôn ngữ đặc tả cho bộ phân tích từ vựng . . . . 60 Kết luận 65 Tài liệu tham khảo 65 4 Mở đầu 1. Lý do chọn đề tài Ngôn ngữ hình thức là một sự tổng quát của ngôn ngữ tự nhiên dưới dạng mô hình toán học, được nghiên cứu từ năm 1879 bởi G.Frege được phát triển bởi N. Chomsky cùng nhiều tác giả khác vào những năm 50 của thế kỉ trước. Otomat hữu hạn là một mô hình máy trừu tượng khá đơn giản dùng để đoán nhận lớp ngôn ngữ chính quy - một lớp ngôn ngữ có nhiều tính chất đặc biệt và được ứng dụng nhiều trong lĩnh vực công nghệ thông tin. Otomat hữu hạn có vai trò quan trọng trong xử lý ngôn ngữ, mật mã và có nhiều ứng dụng trong khoa học, kỹ thuật và thực tế. Với mong muốn tìm hiểu sâu hơn về otomat hữu hạn và những ứng dụng của chúng, dưới sự hướng dẫn của TS. Kiều Văn Hưng em quyết định chọn đề tài nghiên cứu “Otomat hữu hạn và ứng dụng trong phân tích từ vựng” cho luận văn tốt nghiệp thạc sĩ chuyên ngành Toán ứng dụng. 2. Mục đích nghiên cứu Tìm hiểu về otomat hữu hạn và ứng dụng của chúng trong phân tích từ vựng. 5 3. Nhiệm vụ nghiên cứu Trình bày một cách hệ thống về lý thuyết otomat hữu hạn và ứng dụng của otomat hữu hạn trong phân tích từ vựng. 4. Đối tượng và phạm vi nghiên nghiên cứu • Đối tượng nghiên cứu: Otomat hữu hạn và ứng dụng của otomat trong phân tích từ vựng. • Phạm vi nghiên cứu: Tìm hiểu tổng quan về otomat hữu hạn đơn định và otomat hữu hạn đa định. 5. Phương pháp nghiên cứu Tìm hiểu các tài liệu, sách, báo liên quan đến các kết quả đã có về otomat hữu hạn. Tổng hợp kiến thức và trình bày một cách hệ thống. 6. Đóng góp mới Hệ thống các kiến thức về otomat hữu hạn và ứng dụng của otomat, góp phần làm sinh động hơn các kết quả, sự hiểu biết về otomat và ngôn ngữ chính quy. Hi vọng luận văn là một tài liệu tham khảo hữu ích về lý thuyết otomat, ngôn ngữ hình thức nói chung và lớp ngôn ngữ chính quy nói riêng. 6 Chương 1 Otomat hữu hạn Lý thuyết otomat đề cập một mô hình tính toán có vai trò quan trọng trong lĩnh vực khoa học máy tính. Mô hình otomat hữu hạn là công cụ hữu hiệu để nghiên cứu về lý thuyết tính toán và những lĩnh vực liên quan đến khoa học máy tính với nhiều ứng dụng quan trọng trong xử lý văn bản, trình biên dịch, thiết kế phần cứng, ngôn ngữ lập trình và trí tuệ nhân tạo. Một số nhà khoa học tiêu biểu phát triển mạnh hướng nghiên cứu này là Mecullock, Pittis (1943), Kleene (1956), Mc – Naughton, Yamad (1960), Rabin, Shepherdson (1959),... Với các nghiên cứu về otomat hữu hạn đơn định (DFA – Deterministic Finite Automat), otomat hữu hạn không đơn định (NFA – Nondeterministic Finite Automat), otomat không đơn định với ε chuyển (ε − N F A), otomat hữu hạn 2 phía (two – way Finite Automat), otomat hữu hạn có ra (Finite Automat with output),... Trong luận văn này, chúng ta chỉ tìm hiểu otomat hữu hạn đơn định (DFA) và otomat hữu hạn không đơn định (NFA). 7 1.1. Kiến thức cơ sở 1.1.1. Bảng chữ, từ, ngôn ngữ Định nghĩa 1.1. Một tập hợp khác rỗng, hữu hạn hay vô hạn được gọi là bảng chữ. Mỗi phần tử của bảng chữ được gọi là một chữ hay một kí hiệu. Trong luận văn này chúng ta chỉ xét các bảng chữ hữu hạn, thường được kí hiệu là Σ. Ví dụ 1.1. Sau đây là một số bảng chữ: + Σ = {a, b, c, d, e, ..., z}; + ∆ = {α, β, γ, δ}; + Γ = {0, 1}. Định nghĩa 1.2. Cho bảng chữ Σ. Một từ (hay chuỗi) là một dãy hữu hạn các chữ của bảng chữ Σ. Đặc biệt, từ rỗng là từ mà không chứa bất kì chữ nào trong bảng chữ và được kí hiệu là ε. Như vậy, một từ trên bảng chữ Σ là một dãy hữu hạn gồm một số lớn hơn hay bằng không các chữ của Σ, trong đó một chữ có thể xuất hiện nhiều lần. Tổng số vị trí của các kí hiệu xuất hiện trong từ α được gọi là độ dài của từ α và kí hiệu |α|. Quy ước |ε| = 0. Tập tất cả các từ trên bảng chữ Σ được kí hiệu là Σ∗ và Σ+ = Σ∗ \ {ε}. Nói cách khác, Σ∗ = Σ+ ∪ {ε}. Ví dụ 1.2. Cho Σ = {1, 2, 3, ..., n}, Γ = {x, y} là 2 bảng chữ. Khi đó xyx và xxy là các từ trên bảng chữ Γ và |xyx| = |xxy| = 3. 1, 12, 21, 8 1111, 111222 là các từ trên bảng chữ Σ và |1| = 1, |12| = 2, |1111| = 4, |111222| = 6. Nhận xét: Nếu α là một từ trên bảng chữ Σ và Σ ⊆ ∆ thì α cũng là từ trên bảng chữ ∆. Các phép toán trên từ: Cho bảng chữ Σ và các từ α = a1 a2 ...am , β = b1 b2 ...bn và γ = c1 c2 ...ck (m, n, k ∈ N). Ta xác định các phép toán sau: - Phép nhân ghép: Tích ghép (hay nhân ghép) của hai từ α và β là từ α.β = β.α = a1 a2 ...am b1 b2 ...bn . - Phép lấy từ ngược: Giả sử từ α 6= ε thì từ αR = am am−1 ...a2 a1 là từ ngược (hay từ soi gương) của từ α. - Phép chia từ: là phép ngắt bỏ phần đầu hay phần cuối của một từ. Phép chia trái (phải) của từ α cho từ β(tương ứng, γ) hay gọi là thương bên trái (phải) của α và β(tương ứng, γ) cho kết quả là phần còn lại của từ α sau khi ngắt bỏ phần đầu (cuối) β(tương ứng, γ) trong từ α, và được ký hiệu là α /γ (tương ứng, β \α ). Ví dụ 1.3. Cho các từ α = 1231331223, β = 123, γ = 223 trên bảng chữ Σ = {1, 2, 3}. Khi đó: + α.β = 1231331223123, γ.α = 2231231221223; + αR = 3221331321, β R = 321; + α /γ = 1231331 , β \α = 1221223. Định nghĩa 1.3. Cho bảng chữ Σ. Mỗi tập con L ⊆ Σ∗ được gọi là một ngôn ngữ trên bảng chữ Σ. Chú ý rằng tập rỗng, kí hiệu ∅, là một ngôn ngữ không gồm một chữ cái nào và được gọi là ngôn ngữ rỗng. Ngôn ngữ rỗng là ngôn ngữ 9 trên mọi bảng chữ. Ta phân biệt ngôn ngữ rỗng L 6= ∅ khác với ngôn ngữ chỉ gồm một phần tử rỗng L = {ε}. Ví dụ 1.4. + Σ∗ là ngôn ngữ gồm tất cả các từ trên Σ và Σ+ là ngôn ngữ gồm tất cả các từ khác rỗng trên Σ. + A = {a, b, c}, B = {aa, bb, cc, ab, bc, ca}, C = {abca, cba, a, bc}, D = {abccda, acbab, abcc, ac} là ngôn ngữ trên bảng chữ Σ = {a, b, c}. + L1 = {0}, L2 = {000, 10, 1111, 110}, L3 = {0100, 01010, 100, 01010} là các ngôn ngữ trên bảng chữ Γ = {0, 1}. Các phép toán trên ngôn ngữ: Do mỗi ngôn ngữ là một tập hợp nên ta có các phép toán đại số tập hợp như là phép giao, phép hợp, phép hiệu, phép lấy phần bù trên các ngôn ngữ. Chẳng hạn, với L1 và L2 là hai ngôn ngữ trên bảng chữ Σ thì ta có các ngôn ngữ mới sau đây trên bảng chữ Σ. - Phép hợp: Hợp của hai ngôn ngữ L1 và L2 trên bảng chữ Σ, ký hiệu L1 ∪ L2 , là một ngôn ngữ trên bảng chữ Σ xác định như sau  L1 ∪ L2 = ω ∈ Σ∗ | ω ∈ L1 hoặc ω ∈ L2 . Tương tự như vậy ta có thể định nghĩa hợp của một số hữu hạn các ngôn ngữ L1 , L2 , ..., Ln (n ≥ 2) trên bảng chữ Σ như sau n S  Li = ω ∈ Σ∗ | ω ∈ Li , với i nào đó, 1 ≤ i ≤ n . i=1 - Phép giao: Giao của hai ngôn ngữ L1 và L2 trên bảng chữ Σ, ký hiệu L1 ∩ L2 , là một ngôn ngữ trên bảng chữ Σ xác định như sau  L1 ∩ L2 = ω ∈ L1 và ω ∈ L2 . 10 Tương tự như vậy ta có thể định nghĩa giao của của một số hữu hạn các ngôn ngữ L1 , L2 , ..., Ln (n ≥ 2) trên bảng chữ Σ như sau n T  Li = ω ∈ Σ∗ | ω ∈ Li , với mọi i, 1 ≤ i ≤ n . i=1 - Phép hiệu: Cho hai ngôn ngữ L1 và L2 trên bảng chữ Σ, ký hiệu L1 \ L2 hoặc L1 − L2 , là một ngôn ngữ trên bảng chữ Σ xác định như sau  L1 − L2 = ω ∈ L1 và ω ∈ / L2 . - Phép lấy phần bù: Ngôn ngữ phần bù của ngôn ngữ L trên bảng chữ Σ, ký hiệu L là một ngôn ngữ trên bảng chữ Σ xác định như sau L = {ω ∈ L∗ | ω ∈ / L}. - Phép nhân ghép: Với hai ngôn ngữ L1 trên bảng chữ Σ1 và L2 trên bảng chữ Σ2 , nhân ghép (hay tích) của hai ngôn ngữ L1 và L2 là một ngôn ngữ trên bảng chữ Σ1 ∪ Σ2 , ký hiệu L1 L2 , được xác định bởi  L1 L2 = αβ | α ∈ L1 và β ∈ L2 . - Phép lặp: Cho ngôn ngữ L trên bảng chữ Σ, ta có ∞ S + Tập từ ε ∪ L ∪ L2 ∪ ... ∪ Ln ∪ ... = Ln được gọi là ngôn ngữ lặp của n=0 ngôn ngữ L (hay bao đóng ghép của ngôn ngữ L), ký hiệu L∗ . Nói cách ∞ S khác ngôn ngữ lặp của L là hợp mọi lũy thừa của L: L∗ = Ln . + Tập từ L ∪ L2 ∪ ... ∪ Ln ∪ ... = ∞ S n=0 Ln được gọi là ngôn ngữ lặp cắt n=1 của ngôn ngữ L, ký hiệu L+ . Mặt khác ngôn ngữ lặp cắt của L là hợp ∞ S mọi lũy thừa của L: L+ = Ln . n=1 11 - Phép lấy ngôn ngữ ngược: Cho ngôn ngữ L trên bản chữ Σ, khi đó ngôn ngữ ngược của L là một ngôn ngữ trên bảng chữ Σ, ký hiệu LR , xác định bởi  LR = ω ∈ Σ∗ | ω R ∈ L . - Phép chia ngôn ngữ: Cho ngôn ngữ X và Y trên bảng chữ Σ, khi đó thương bên trái (phải) của ngôn ngữ X cho ngôn ngữ Y là một ngôn ngữ trên Σ, ký hiệu Y \X (X /Y ), được xác định  = z ∈ Σ∗ | x ∈ X, y ∈ Y mà x = yz  (X /Y = z ∈ Σ∗ | x ∈ X, y ∈ Y mà x = zy ). X Y\ Ví dụ 1.5. Xét các ngôn ngữ L0 = {x, y}, L1 = {xx, yyy, yx, yyx}, L2 = {xx, yyy, xyxx, yxx, xyx} và L3 = {ε, yx} trên bảng chữ Σ = {x, y}. Ta thực hiện các phép toán sau: + Phép hợp: L1 ∪ L2 = {xx, yyy, yx, yyx, xyxx, yxx, xyx}; + Phép giao: L1 ∩ L2 = {xx, yyy}; + Phép lặp: L20 = {xx, yx, xy, yy}, L30 = {xxx, xxy, xyx, yxx, yyx, yxy, xyy, yyy}; + Phép lấy phần bù: L20 = {ω ∈ Σ∗ | |ω| = 6 2}; + Phép lấy ngôn ngữ ngược: LR 1 = {xx, yyy, xy, xyy}; + Phép nhân ghép: L1 L0 = {xxx, yyyx, yxx, yyxx, xxy, yyy, yxy, yyxy}; + Phép chia ngôn ngữ: L1 L3 \ 1.1.2. = {xx, yyy, yx, yyx, ε}, L1 /L3 = {xx, yyy, yx, yyx, ε, y}. Ngôn ngữ chính quy và biểu thức chính quy Định nghĩa 1.4. Cho bảng chữ Σ = {a1 , a2 , ..., an }. Khi đó ngôn ngữ chính quy được định nghĩa đệ quy như sau: 12 (i) Các ngôn ngữ rỗng và ngôn ngữ gồm một phần tử {ai } với i = 1, n được gọi là ngôn ngữ chính quy trên Σ. (ii) Nếu L1 và L2 là hai ngôn ngữ chính quy trên Σ thì L1 ∪ L2 , L1 L2 , L∗1 , L∗2 cũng là các ngôn ngữ chính quy trên Σ. (iii) Không có ngôn ngữ chính quy nào khác trên Σ ngoài các ngôn ngữ chính quy được định nghĩa ở trên. Ví dụ 1.6. + {ε} là ngôn ngữ chính quy vì φ∗ = {ε} .  + L1 = a2 , ab = {a} {a, b} = {a} ({a} ∪ {b}) là ngôn ngữ chính quy.   + L2 = a∗ b, a2 = {a∗ b} ∪ a2 là ngôn ngữ chính quy. Dưới đây là một số tính chất cơ bản của ngôn ngữ chính quy. Định lý 1.1. Mọi ngôn ngữ chính quy trên bảng chữ Σ đều nhận được từ các ngôn ngữ hữu hạn bằng cách áp dụng một số hữu hạn lần các phép toán hợp, nhân ghép và lặp. Định lý 1.2. (Bổ đề Bơm) Nếu L là ngôn ngữ chính quy thì tồn tại một số nguyên dương n sao cho với mọi w ∈ L và |w| ≥ n đều tồn tại một cách phân tích w có dạng w = xyz với |xy| ≤ n và |y| ≥ 1, sao cho xy i z ∈ L, ∀i = 0, 1, 2, ... Định lý 1.3. Cho L1 , L2 là các ngôn ngữ chính quy trên bảng chữ Σ. Khi đó, L1 × L2 , L1 ∪ L2 , L∗1 cũng là các ngôn ngữ chính quy. Định lý 1.4. Cho L1 , L2 là các ngôn ngữ chính quy trên bảng chữ Σ. Khi đó, L1 , L1 ∩ L2 , L1 \ L2 , LR 1 là ngôn ngữ chính quy. 13 Định nghĩa 1.5. Cho bảng chữ Σ = {a1 , a2 , ..., an } , khi đó biểu thức chính quy được định nghĩa đệ quy như sau: (i) φ, ai (ai ∈ Σ) được gọi là biểu thức chính quy trên bảng chữ Σ biểu diễn ngôn ngữ rỗng và ngôn ngữ {ai } . (ii) Nếu l1 và l2 là hai biểu thức chính quy trên bảng chữ Σ thì l1 + l2 , l1 .l2 , l1∗ , l2∗ cũng là các biểu thức chính quy trên bảng chữ Σ biểu diễn các ngôn ngữ L1 ∪ L2 , L1 L2 , L∗1 , L∗2 . (iii) Không có biểu thức chính quy nào khác trên bảng chữ Σ ngoài các biểu thức chính quy được định nghĩa ở trên. Định nghĩa 1.6. Hai biểu thức chính quy l1 và l2 gọi là tương đương nếu chúng biểu diễn cùng một ngôn ngữ, kí hiệu l1 = l2 . Một số tính chất của biểu thức chính quy Với l1 , l2 , l3 là các biểu thức chính qui trên Σ ta có các kết quả sau: + l1 + l2 = l2 + l1 . + (l1 + l2 ) + l3 = l1 + (l2 + l3 ) . + l1 + l1 = l1 . +(l1 l2 ) l3 = l1 (l2 l3 ) . + l1 (l2 + l3 ) = l1 l2 + l1 l3 ; (l1 + l2 ) l3 = l1 l3 + l2 l3 . + φ∗ = {ε} . + (l1∗ )∗ = l1∗ ; l1+ + = l1+ . Định lý 1.5. Một ngôn ngữ trên bảng chữ Σ là chính quy khi và chỉ khi nó được biểu diễn bằng một biểu thức chính quy. Ví dụ 1.7. 14 + Biểu thức 01 biểu diễn ngôn ngữ chính quy {01} . + Biểu thức chính quy a. (a + b) biểu diễn ngôn ngữ chính quy  {a} ({a} ∪ {b}) = {a} {a, b} = a2 , ab . + Biểu thức chính quy (0 + 1)∗ 000(0 + 1)∗ biểu diễn ngôn ngữ chính quy {0, 1}∗ {000} {0, 1}∗ , tức ngôn ngữ đó gồm tất cả các từ có ba số 0 liên tiếp. Ví dụ 1.8. + Ngôn ngữ L = {a, ba} được biểu diễn bởi biểu thức chính quy a + ba. + Ngôn ngữ L = {a}∗ {ba} được biểu diễn bởi biểu thức chính quy an .ba, ∀n ∈ N. + Ngôn ngữ L = {a, ε} {bba} được biểu diễn bởi biểu thức chính quy abba + bba. 1.2. Otomat hữu hạn 1.2.1. Otomat hữu hạn đơn định Mô cách phi hình thức, otomat hữu hạn là "máy" đoán nhận từ gồm 3 thành phần: + Có một băng vào, mỗi ô ghi một chữ của bảng chữ Σ. + Có một đầu đọc, mỗi thời điểm quan sát một ô trên băng vào. 15 + Có một bộ điều khiển gồm hữu hạn trạng thái, tại mỗi thời điểm có một trạng thái hiện thời. Hình 1.1: Mô tả một DFA Hoạt động của otomat hữu hạn + Otomat hữu hạn làm việc theo từng bước rời rạc. Một bước làm việc như sau: Tùy theo trạng thái hiện thời của Q và kí hiệu mà đầu đọc quan sát được mà otomat chuyển sang trạng thái mới, đồng thời đầu đọc dịch chuyển sang phải 1 ô. Quy luật chuyển trạng thái được cho bởi 1 hàm, gọi là hàm chuyển δ : Q × Σ → Q. + Trong Q có một phân biệt một trạng thái q0 -trạng thái đầu và một tập F - các trạng thái kết thúc (trạng thái cuối). + Ta nói otomat đoán nhận một xâu vào ω ∈ Σ∗ nếu otomat xuất phát từ trạng thái đầu q0 với đầu đọc nhóm vào kí tự trái nhất của ω, sau một số hữu hạn bước làm việc, nó đọc xong xâu ω và đầu đọc rơi vào một trong những trạng thái cuối. + Tập hợp mọi xâu đoán nhận của otomat lập thành ngôn ngữ đoán nhận được bởi otomat đó. Định nghĩa 1.7. Otomat hữu hạn đơn định(DFA) là một bộ gồm 5 thành phần A = (Q, Σ, δ, q0 , F ), trong đó: 16 + Q là một tập hữu hạn khác rỗng các trạng thái; + Σ là một bảng chữ, được gọi là bảng chữ vào; + δ : Q × Σ → Q là hàm chuyển trạng thái; + q0 ∈ Q được gọi là trạng thái bắt đầu; + F ⊆ Q được gọi là tập trạng thái kết thúc. Nếu δ (q, a) xác định ∀q ∈ Q, ∀a ∈ Σ, thì otomat A được gọi là otomat hữu hạn đơn định đầy đủ. Hàm chuyển trạng thái mở rộng: Để mô tả hoạt động của một DFA trên chuỗi, ta mở rộng hàm chuyển δ như sau: δb : Q × Σ∗ → Q + δb (q, ε) = q;   b b + δ (q, wa) = δ δ (q, w) , a . b a) = δ(δ(q, b ε), a) = δ(q, a), với mọi a ∈ Σ nên người ta Vì δ(q, b thường kí hiệu δ thay cho δ. Ngôn ngữ đoán nhận bởi DFA: Một chuỗi w được đoán nhập bởi otomat hữu hạn đơn định A = (Q, Σ, δ, q0 , F ) , nếu δ (q0 , w) = p với p ∈ F. Ngôn ngữ được đoán nhận bởi A, ký hiệu L(A) là tập hợp: L (A) = {w|δ (q0 , w) ∈ F } . Định nghĩa 1.8. Hai otomat cùng đoán nhận một ngôn ngữ thì gọi là hai otomat tương đương. Biểu diễn otomat hữu hạn đơn định 17 Cho otomat hữu hạn đơn định A = (Q, Σ, δ, q0 , F ) với Q = {q0 , q1 , ..., qm } và Σ = {a1 , a2 , ..., an }. Biểu diễn otomat bằng bảng chuyển Dựa vào hàm chuyển của otomat hữu hạn A, ta lập bảng chuyển với các ô (i, j) như sau:   δ (q , a ) , nếu δ (q , a ) ∈ Q; i j i j (i, j) =  ∅, nếu δ (qi , aj ) ∈ / Q. Ta đánh dấu → trước trạng thái bắt đầu và trạng thái kết thúc được in đậm trong cột đầu tiên của bảng. Biểu diễn otomat bằng đồ thị chuyển Hàm chuyển của otomat A có thể được biểu diễn bằng một đồ thị chuyển có hướng, có khuyên G được xây dựng như sau: + Tập đỉnh của G được gán nhãn bằng các trạng thái qi , với qi ∈ Q. + Một cung có hướng từ đỉnh qi sang đỉnh qj và trên cung được gán nhãn a nếu có hàm chuyển δ (qi , a) = qj . + Đỉnh vào của đồ thị G luôn là q0 và được đánh đấu → ở phía bên trái. Các đỉnh có các trạng thái kết thúc của đồ thị được vẽ bằng đường tròn nét đậm và các đỉnh còn lại được vẽ bằng đường tròn nét mảnh. 18
- Xem thêm -

Tài liệu liên quan

Tài liệu vừa đăng