Automata Là Gì – Lý Thuyết Automat

Bài viết Automata Là Gì – Lý Thuyết Automat thuộc chủ đề về Giải Đáp đang được rất nhiều bạn lưu tâm đúng không nào !! Hôm nay, Hãy cùng HappyMobile.vn tìm hiểu Automata Là Gì – Lý Thuyết Automat trong bài viết hôm nay nha !
Các bạn đang xem bài : “Automata Là Gì – Lý Thuyết Automat”

Automata Là Gì

Automata Là Gì? Trong chương này, ta sẽ thống kê 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 cũng như nhau về khả năng đoán nhận ngôn ngữ. Tiếp đó, ta sẽ nói đế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ẽ nói đến mối quan hệ tình dục 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 chi tiết của ôtômát hữu hạn sẽ được trình bày.

Automata Là Gì - Lý Thuyết Automat

Automata Là Gì – Lý Thuyết Automat

Có thể bạn quan tâm: Thời đại 4.0 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 cũng như 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.

Có thể bạn quan tâm: Emoji và Sticker là gì?

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 vài 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ó dùng qua một vài 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 khả năng 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 vài hữu hạn các cổng (gate) input, mỗi cổng có 2 tổng giá trị 0 hoặc 1. Các tổng 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 khả năng được xem như hệ thống trạng thái hữu hạn. Các chương trình 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 quy trình xử lý này, bộ phân tí;ch từ vựng cần phải nhớ một vài 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 kết quả.

Bài Viết Đọc Nhiều  Hỏi đáp về danh mục và dịch vụ tại Thegioididong.com

Máy tí;nh cũng khả năng đượ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 số 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 khả năng là 235.

Lý do quan trọng nhất cho việc thống kê các hệ thống trạng thái hữu hạn là tí;nh một cách 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 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 khả năng nhận dạng ngôn ngữ đơn giản 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 cũng như.

Automata Là Gì

Có thể bạn quan tâm: IQ là gì? Bao nhiêu là cao?

Ô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 (khả năng 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 vài 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 số những trạng thái kết thúc.

Bài Viết Đọc Nhiều  Tài khoản đối ứng là gì

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 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 vài thực sự, vì thế DFA cần dùng một vài hữu hạn trạng thái.

Có thể bạn quan tâm: Slide là gì?

Định nghĩa

Một cách cách 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ẽ).Có thể xây dựng DFA cho các từ có độ dài lẻ với 1 ở giữa không?

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 số 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

Để khả năng mô tả một cách cách thức vận hành 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 cách 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 vài 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

Bài Viết Đọc Nhiều  Range là gì - Happymobile.vn

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 cách 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 khả năng 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 khả năng 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, cùng lúc ấy cũng chỉ ra rằng rằng khả năng đơn giản mô phỏng vận hành 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.

Giải thuật mô phỏng vận hành của một DFA

Giao điểm này của DFA có đúng không?

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

 

Các câu hỏi về Automata Là Gì – Lý Thuyết Automat

Nếu có bắt kỳ câu hỏi thắc mắt nào vê Automata Là Gì – Lý Thuyết Automat hãy cho chúng mình biết nha, mõi thắt mắt hay góp ý của các bạn sẽ giúp mình nâng cao hơn hơn trong các bài sau nha <3

Bài viết Automata Là Gì – Lý Thuyết Automat ! được mình và team xem xét cũng như tổng hợp từ nhiều nguồn. Nếu thấy bài viết Automata Là Gì – Lý Thuyết Automat Cực hay ! Hay thì hãy ủng hộ team Like hoặc share.
Nếu thấy bài viết Automata Là Gì – Lý Thuyết Automat rât hay ! chưa hay, hoặc cần bổ sung. Bạn góp ý giúp mình nha!!

 

Cliph Về Automata Là Gì – Lý Thuyết Automat

Các Hình Ảnh Về Automata Là Gì – Lý Thuyết Automat

Automata Là Gì - Lý Thuyết Automat

Automata Là Gì – Lý Thuyết Automat

Các từ khóa tìm kiếm cho bài viết #Automata #Là #Gì #Lý #Thuyết #Automat

Tra cứu tin tức tại WikiPedia

Bạn hãy xem thêm thông tin về Automata Là Gì – Lý Thuyết Automat từ trang Wikipedia tiếng Việt.◄

source: https://happymobile.vn/

Xem thêm các bài viết về Giải Đáp tại : https://happymobile.vn/hoi-dap/

Từ khóa liên quan:

automata là gì
automat
automaton là gì
automata
dfa là gì
automata com
lý thuyết automata
lý thuyết automat
dfa automat
aitomat

Related Posts

About The Author

Add Comment