Tin học lý thuyết - Chương 3

ÔTÔMÁT HỮU HẠN VÀ BIỂU THỨC CHÍNH QUY Nội dung chính: Trong chương này, ta sẽ nghiên cứu một loại "máy trừu tượng" gọi là ôtômát hữu hạn. Chúng là công cụ dùng đoán nhận một lớp ngôn ngữ khá đơn giản gọi là lớp ngôn ngữ chính quy. Trước hết, hai dạng của ôtômát hữu hạn sẽ lần lượt được trình bày và có sự chứng minh rằng chúng tương đương nhau về khả năng đoán nhận ngôn ngữ. Tiếp đó, ta sẽ đề cập đến biểu thức chính quy - một phương tiện khác để xác định...
Nội dung trích xuất từ tài liệu:
Tin học lý thuyết - Chương 3 Chương III : Ôtômát hữu hạn và biểu thức chính quy CHƯƠNG III ÔTÔMÁT HỮU HẠN VÀ BIỂU THỨC CHÍNH QUY Nội dung chính: Trong chương này, ta sẽ nghiên cứu một loại máy trừu tượng gọi là ôtômát hữu hạn. Chúng là công cụ dùng đoán nhận một lớp ngôn ngữ khá đơn giản gọi là lớp ngôn ngữ chính quy. Trước hết, hai dạng của ôtômát hữu hạn sẽ lần lượt được trình bày và có sự chứng minh rằng chúng tương đương nhau về khả năng đoán nhận ngôn ngữ. Tiếp đó, ta sẽ đề cập đến biểu thức chính quy - một phương tiện khác để xác định ngôn ngữ và ta lại thấy rằng lớp ngôn ngữ do các ôtômát hữu hạn chấp nhận chính là lớp ngôn ngữ chính quy. Phần tiếp theo của chương sẽ đề cập đến mối quan hệ giữa cơ chế ôtômát và các biểu thức chính quy dùng ký hiệu cho ngôn ngữ. Cuối chương này, một vài ứng dụng cụ thể của ôtômát hữu hạn sẽ được trình bày. Mục tiêu cần đạt: Kết thúc chương này, sinh viên cần nắm vững : Khái niệm ôtômát hữu hạn, các thành phần, các dạng và sự khác biệt cơ bản giữa hai dạng. Cách thức chuyển đổi tương đương từ dạng đơn định sang không đơn định và ngược lại. Viết biểu thức chính quy ký hiệu cho tập ngôn ngữ chính quy. Mối liên quan giữa ôtômát hữu hạn và biểu thức chính quy. Vẽ sơ đồ chuyển trạng thái (đơn định hoặc không đơn định) từ một biểu thức chính quy. Tìm các ứng dụng thực tế khác từ mô hình ôtômát hữu hạn. Kiến thức cơ bản: Để tiếp thu tốt nội dung của chương này, sinh viên cần có một số các kiến thức liên quan về lý thuyết đồ thị, lý thuyết mạch; hiểu các khái niệm cơ bản về kiến trúc máy tính; có sử dụng qua một số trình soạn thảo văn bản thông thường … Tài liệu tham khảo : [1] John E. Hopcroft, Jeffrey D.Ullman – Introduction to Automata Theory, Languages and Computation – Addison – Wesley Publishing Company, Inc – 1979 (Chapter 2 : Finite Automata and Regular Expressions). [2] Phan Thị Tươi – Trình biên dịch – Nhà xuất bản Giáo dục – 1986 (Chương 3 : Bộ phân tích từ vựng). 20 Chương III : Ôtômát hữu hạn và biểu thức chính quy [3] J.A.Garcia and S.Moral- Theory of Finite Automata : http://decsai.ugr.es/~jags/fat.html [4] Donald R. Biggar - Regular Expression Matching Using Finite Automata: http://www3.sympatico.ca/dbiggar/FA.home.html I. ÔTÔMÁT HỮU HẠN (FA : Finite Automata) Ôtômát hữu hạn FA là một mô hình tính toán của hệ thống với sự mô tả bởi các input và output. Tại mỗi thời điểm, hệ thống có thể được xác định ở một trong số hữu hạn các cấu hình nội bộ gọi là các trạng thái (states). Mỗi trạng thái của hệ thống thể hiện sự tóm tắt các thông tin liên quan đến những input đã chuyển qua và xác định các phép chuyển kế tiếp trên dãy input tiếp theo. Trong khoa học máy tính, ta có thể tìm thấy nhiều ví dụ về hệ thống trạng thái hữu hạn, và lý thuyết về ôtômát hữu hạn là một công cụ thiết kế hữu ích cho các hệ thống này. Chẳng hạn, một hệ chuyển mạch như bộ điều khiển (Control Unit) trong máy tính. Một chuyển mạch thì bao gồm một số hữu hạn các cổng (gate) input, mỗi cổng có 2 giá trị 0 hoặc 1. Các giá trị đầu vào này sẽ xác định 2 mức điện thế khác nhau ở cổng output. Mỗi trạng thái của một mạng chuyển mạch với n cổng bất kỳ sẽ là một trường hợp trong 2n phép gán của 0 và 1 đối với các cổng khác nhau. Các chuyển mạch thì được thiết kế theo cách này, vì thế chúng có thể được xem như hệ thống trạng thái hữu hạn. Các chương trình sử dụng thông thường, chẳng hạn trình sọan thảo văn bản hay bộ phân tích từ vựng trong trình biên dịch máy tính cũng được thiết kế như các hệ thống trạng thái hữu hạn. Ví dụ bộ phân tích từ vựng sẽ quét qua tất cả các dòng ký tự của chương trình máy tính để tìm nhóm các chuỗi ký tự tương ứng với một tên biến, hằng số, từ khóa, …Trong quá trình xử lý này, bộ phân tích từ vựng cần phải nhớ một số hữu hạn thông tin như các ký tự bắt đầu hình thành những chuỗi từ khóa. Lý thuyết về ôtômát hữu hạn thường được dùng đến nhiều cho việc thiết kế các công cụ xử lý chuỗi hiệu quả. Máy tính cũng có thể được xem như một hệ thống trạng thái hữu hạn. Trạng thái hiện thời của bộ xử lý trung tâm, bộ nhớ trong và các thiết bị lưu trữ phụ ở mỗi thời điểm bất kỳ là một trong những số rất lớn và hữu hạn của số trạng thái. Bộ não con người cũng là một hệ thống trạng thái hữu hạn, vì số các tế bào thần kinh hay gọi là neurons là số có giới hạn, nhiều nhất có thể là 235. Lý do quan trọng nhất cho việc nghiên cứu các hệ thống trạng thái hữu hạn là tính tự nhiên của khái niệm và khả năng ứng dụng đa dạng trong nhiều lĩnh vực thực tế. Ôtômát hữu hạn (FA) được chia thành 2 loại: đơn định (DFA) và không đơn định (NFA). Cả hai loại ôtômát hữu hạn đều có khả năng nhận dạng chính xác tập chính quy. Ôtômát hữu hạn đơn định có khả năng nhận dạng ngôn ngữ dễ dàng hơn ôtômát hữu hạn không đơn định, nhưng thay vào đó thông thường kích thước của nó lại lớn hơn so với ôtômát hữu hạn không đơn định tương đương. 21 Chương III : Ôtômát hữu hạn và biểu thức chính quy 1.1. Ôtômát hữu hạn đơn định - DFA (Deterministic Finite Automata) Một ôtômát hữu hạn đơn định (DFA) - gọi tắt là FA -gồm một tập hữu hạn các trạng thái và một tập các phép chuyển từ trạng thái này tới trạng thái khác trên các ký hiệu nhập (input symbols) được chọn từ một bộ chữ cái Σ nào đó. Mỗi ký hiệu nhập có đúng một phép chuyển khỏi mỗi trạng thái (có thể chuyển trở về chính nó). Một trạng thái, thường ký hiệu là q0, gọi là trạng thái bắt đầu (trạng thái ôtômát bắt đầu). Một số trạng thái được thiết kế như là các trạng thái kết thúc hay trạng thái chấp nhận. Một đồ thị có hướng, gọi là sơ đồ chuyển (transition diagram) tương ứng với một DFA như sau: các đỉnh của đồ thị là các trạng thái của DFA; nếu có một đường chuyển từ trạng thái q đến trạng thái p trên input a thì có một cung nhãn a chuyển từ trạng thái q đến trạng thái p trong ...