Lý Thuyết Automata Là Gì

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.Bạn đang xem: Automata là gì

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.

Bạn đang xem: Automata là gì

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.

Xem thêm: Công Ty Kiểm Toán Acpa – Công Ty Dịch Vụ Kiểm Toán Tphcm

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 :

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).

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).

J.A.Garcia and S.Moral- Theory of Finite Automata :

http://decsai.ugr.es/~jags/fat.html

Donald R. Biggar Regular Expression Matching Using Finite Automata:

http://www3.sympatico.ca/dbiggar/FA.home.html

ÔTÔMÁT HỮU HẠN (FA : Finite Automata)

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.

Ô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áctrạ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 sơ đồ chuyển. DFA chấp nhận một chuỗi x nếu như tồn tại dãy các phép chuyển tương ứng trên mỗi ký hiệu của x dẫn từ trạng thái bắt đầu đến một trong những trạng thái kết thúc.

Chẳng hạn, sơ đồ chuyển của một DFA được mô tả trong hình 3.1. Trạng thái khởi đầu q0 được chỉ bằng mũi tên có nhãn “Start”. Chỉ có duy nhất một trạng thái kết thúc, cũng là q0 trong trường hợp này, được chỉ ra bằng hai vòng tròn. Ôtômát này chấp nhận tất cả các chuỗi số 0 và số 1 với số số 0 và số số 1 là số chẵn.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *