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, những thành phần, những dạng và sự độc lạ 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.

Bạn đang đọc: Automata là gì

Viết biểu thức chí ; nh quy ký hiệu cho tập ngôn từ chí ; nh quy. Mối tương 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 những ứng dụng thực tiễn khác từ quy mô ô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ó 1 số ít những kiến thức và kỹ năng tương quan về triết lý đồ thị, kim chỉ nan mạch ; hiểu những khái niệm cơ bản về kiến trúc máy tí ; nh ; có sử dụng qua một số ít trình soạn thảo văn bản thường thì …

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 đào tạo – 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) ÔTÔMÁT HỮU HẠN ( FA : Finite Automata )Trong khoa học máy tí ; nh, ta hoàn toàn có thể tìm thấy nhiều ví ; dụ về mạng lưới hệ thống trạng thái hữu hạn, và triết lý về ôtômát hữu hạn là một công cụ phong cách thiết kế hữu í ; ch cho những mạng lưới hệ thống này. Chẳng hạn, một hệ chuyển mạch như bộ điều khiển và tinh chỉnh ( Control Unit ) trong máy tí ; nh. Một chuyển mạch thì gồm có 1 số ít hữu hạn những cổng ( gate ) input, mỗi cổng có 2 giá trị 0 hoặc 1. Các giá trị nguồn vào này sẽ xác lập 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 2 n phép gán của 0 và 1 so với những cổng khác nhau. Các chuyển mạch thì được phong cách thiết kế theo cách này, cho nên vì thế chúng hoàn toàn có thể được xem như mạng lưới hệ thống trạng thái hữu hạn. Các chương trình sử dụng thường thì, ví dụ điển hình 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 phong cách thiết kế như những mạng lưới 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 toàn bộ những dòng ký tự của chương trình máy tí ; nh để tìm nhóm những chuỗi ký tự tương ứng với một tên biến, hằng số, từ khóa, … Trong quy trình giải quyết và xử lý này, bộ phân tí ; ch từ vựng cần phải nhớ một số ít hữu hạn thông tin như những ký tự khởi đầ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 phong cách thiết kế những công cụ giải quyết và xử lý chuỗi hiệu suất cao. Máy tí ; nh cũng hoàn toàn có thể được xem như một mạng lưới hệ thống trạng thái hữu hạn. Trạng thái hiện thời của bộ giải quyết và xử lý TT, bộ nhớ trong và những thiết bị tàng trữ phụ ở mỗi thời gian 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 mạng lưới hệ thống trạng thái hữu hạn, vì số những tế bào thần kinh hay gọi là neurons là số có số lượng giới hạn, nhiều nhất hoàn toàn có thể là 235. Lý do quan trọng nhất cho việc nghiên cứu và điều tra những mạng lưới hệ thống trạng thái hữu hạn là tí ; nh tự nhiên của khái niệm và năng lực ứng dụng phong phú trong nhiều nghành nghề dịch vụ trong thực tiễn. Ô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ó năng lực nhận dạng chí ; nh xác tập chí ; nh quy. Ôtômát hữu hạn đơn định có năng lực nhận dạng ngôn từ thuận tiện hơn ôtômát hữu hạn không đơn định, nhưng thay vào đó thường thì 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 tự.

Ô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 những phép chuyển từ trạng thái này tới trạng thái khác trên những ký hiệu nhập ( input symbols ) được chọn từ một bộ vần âm Σ 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 ( hoàn toàn 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 khởi đầu ( trạng thái ôtômát mở màn ). Một số trạng thái được phong cách thiết kế như thể những trạng thái kết thúc hay trạng thái đồng ý. Một đồ thị có hướng, gọi là sơ đồ chuyển ( transition diagram ) tương ứng với một DFA như sau : những đỉnh của đồ thị là những 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 đồng ý một chuỗi x nếu như sống sót dãy những phép chuyển tương ứng trên mỗi ký hiệu của x dẫn từ trạng thái mở màn đế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 miêu 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 đồng ý toàn bộ những 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 – 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 những 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 mở màn. F ⊆ Q. là tập những trạng thái kết thúc. Ta vẽ DFA như là bộ điều khiển và tinh chỉnh hữu hạn, với mỗi trạng thái thuộc Q., DFA đọc một chuỗi những 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 lập 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 gật đầu chuỗi được viết trên băng input phí ; a trước đầu đọc, nhưng không gồm có ký tự tại vị trí ; đầu đọc vừa di dời đến. Trong trường hợp đầu đọc đã dịch đến cuối chuỗi trên băng, thì DFA mới đồng ý hàng loạt chuỗi trên băng. Hàm chuyển trạng thái lan rộng ra Để hoàn toàn có thể diễn đạt một cách hình thức hoạt động giải trí của một DFA trên chuỗi, ta lan rộng ra hàm chuyển δ để vận dụng so 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. 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. Q. là tập những trạng thái. Ký hiệu q và p ( có hoặc không có chỉ số ) là những trạng thái, q0 là trạng thái mở màn. Σ là bộ chữ cái nhập. Ký hiệu a, b ( có hoặc không có chỉ số ) và những chữ số là những ký hiệu nhập. δ là hàm chuyển. F là tập những trạng thái kết thúc. w, x, y và z ( có hoặc không có chỉ số ) là những chuỗi ký hiệu nhập .Ngôn ngữ được đồng ý 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 gật đầu 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 lập 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à ở đầu cuối δ ( 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 hoàn toàn có thể chứng tỏ 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 bộc lộ những trạng thái tàng trữ của ôtômát trong quy trình đoán nhận ngôn từ, và như vậy năng lực tàng 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ị, vì vậy những bước chuyển của ôtômát luôn luôn được xác lập một cách duy nhất. Chí ; nh vì hai đặc thù này mà DFA diễn đạt như trên được gọi là ôtômát hữu hạn đơn định .
Chuyên mục: Chuyên mục : Hỏi Đáp

Source: https://iseo1.com
Category: Coin

Trả lời

Email của bạn sẽ không được hiển thị công khai.