Automata là gì

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.

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 :

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.

Thí; dụ 3.1 :

*

Hình 3.1 – Sơ đồ chuyển của một DFA

Một điều cần lưu ý, DFA sử dụng mỗi trạng thái của nó để giữ chỉ một phần của chuỗi số 0 và 1 chứ không phải chứa một số thực sự, vì thế DFA cần dùng một số hữu hạn trạng thái.

Xem thêm: Thượng Lưu Là Gì – Giới Thượng Lưu Tiếng Anh Là Gì

Định nghĩa

Một cách hình thức ta định nghĩa ôtômát hữu hạn là bộ gồm năm thành phần (Q, Σ, δ, q0, F), trong đó :

. Q là tập hợp hữu hạn các trạng thái.

. Σ là bộ chữ cái nhập hữu hạn.

. δ là hàm chuyển ánh xạ từ Q × Σ → Q, tức là δ(q, a) là một trạng thái được cho bởi phép chuyển từ trạng thái q trên ký hiệu nhập a.

. q0 ∈ Q là trạng thái bắt đầu

. F ⊆ Q là tập các trạng thái kết thúc.

Ta vẽ DFA như là bộ điều khiển hữu hạn, với mỗi trạng thái thuộc Q, DFA đọc một chuỗi các ký hiệu a từ Σ viết trên băng (như hình vẽ).

*

Hình 3.2 Mô tả một DFA

Trong một lần chuyển, DFA đang ở trạng thái q đọc ký hiệu nhập a trên băng, chuyển sang trạng thái được xác định bởi hàm chuyển δ(q, a), rồi dịch đầu đọc sang phải một ký tự. Nếu δ(q, a) chuyển đến một trong những trạng thái kết thúc thì DFA chấp nhận chuỗi được viết trên băng input phí;a trước đầu đọc, nhưng không bao gồm ký tự tại vị trí; đầu đọc vừa dịch chuyển đến. Trong trường hợp đầu đọc đã dịch đến cuối chuỗi trên băng, thì DFA mới chấp nhận toàn bộ chuỗi trên băng.

Hàm chuyển trạng thái mở rộng

Để có thể mô tả một cách hình thức hoạt động của một DFA trên chuỗi, ta mở rộng hàm chuyển δ để áp dụng đối với một trạng thái trên chuỗi hơn là một trạng thái trên từng ký hiệu. Ta định nghĩa hàm chuyển δ như một ánh xạ từ Q × Σ* → Q với ý nghĩa δ(q, w) là trạng thái DFA chuyển đến từ trạng thái q trên chuỗi w. Một cách hình thức, ta định nghĩa :

d (q, ε) = q δ (q, wa) = δ(δ (q, w), a), với mọi chuỗi w và ký hiệu nhập a.

Một số quy ước về ký hiệu :

Q là tập các trạng thái. Ký hiệu q và p (có hoặc không có chỉ số) là các trạng thái, q0 là trạng thái bắt đầu. Σ là bộ chữ cái nhập. Ký hiệu a, b (có hoặc không có chỉ số) và các chữ số là các ký hiệu nhập. δ là hàm chuyển. F là tập các trạng thái kết thúc. w, x, y và z (có hoặc không có chỉ số) là các chuỗi ký hiệu nhập.

Ngôn ngữ được chấp nhận bởi DFA

Một chuỗi w được chấp nhập bởi ôtômát hữu hạn M (Q, Σ, δ, q0, F) nếu δ(q0, w) = p với p ∈ F. Ngôn ngữ được chấp nhận bởi M, ký hiệu L(M) là tập hợp:

*

Thí; dụ 3.2 : Xét sơ đồ chuyển ở hình 3.1. Theo khái niệm hình thức, ta có DFA được xác định bởi M (Q, Σ, δ, q0, F) với Q = {q0, q1, q2, q3}, Σ = {0, 1}, F = {q0} và hàm chuyển δ như sau:

*

Giả sử chuỗi w = 110101 được nhập vào M.

Ta có δ(q0, 1) = q1 và δ(q1, 1) = q0 ,vậy δ(q0, 11) = δ(δ(q0,1),1) = δ(q1, 1) = q0.

Tiếp tục δ(q0, 0) = q2, vậy δ(q0, 110) = δ(δ(q0, 11), 0) = q2.

Tiếp tục ta có δ(q0, 1101) = q3, δ(q0, 11010) = q1

Và cuối cùng δ(q0, 110101) = q0 ∈ F.

(Hay d(q0, 110101) = d(q1, 10101) = d(q0, 0101) = d(q2, 101) = d(q3, 01) = d(q1, 1) = q0 ∈ F)

Vậy 110101 thuộc L(M). Ta có thể chứng minh rằng L(M) là tập mọi chuỗi có số chẵn số 0 và số chẵn số 1.

Theo mô tả DFA như trên, ta thấy cũng có thể dùng bảng hàm chuyển (transition table) để mô tả các phép chuyển trạng thái của một ôtômát hữu hạn. Trong bảng hàm chuyển, hàng chứa các trạng thái thuộc tập trạng thái của ôtômát và cột là các ký hiệu thuộc bộ chữ cái nhập. Bảng hàm chuyển gợi ý cho chúng ta một cấu trúc dữ liệu để mô tả cho một ôtômát hữu hạn, đồng thời cũng cho thấy có thể dễ dàng mô phỏng hoạt động của DFA thông qua một chương trình máy tí;nh, chẳng hạn dùng cấu trúc vòng lặp.

Xem thêm: Extend Là Gì

Giải thuật mô phỏng hoạt động của một DFA

*

Nhận xét :

Một cách tổng quát, ta thấy tập Q của DFA thể hiện các trạng thái lưu trữ của ôtômát trong quá trình đoán nhận ngôn ngữ, và như vậy khả năng lưu trữ của ôtômát là hữu hạn. Mặt khác, hàm chuyển d là hàm toàn phần và đơn trị, cho nên các bước chuyển của ôtômát luôn luôn được xác định một cách duy nhất. Chí;nh vì hai đặc điểm này mà DFA mô tả như trên được gọi là ôtômát hữu hạn đơn định.

Chuyên mục: Hỏi Đáp

=> Xem thêm: Tin tức tổng hợp tại Chobball

Comments are closed.