Giới thiệu lý thuyết tự động hóa
Automata - Nó là gì?
Thuật ngữ "Automata" có nguồn gốc từ tiếng Hy Lạp "αὐτόματα" có nghĩa là "tự hoạt động". Automaton (Automata ở dạng số nhiều) là một thiết bị tính toán tự hành trừu tượng tự động tuân theo một chuỗi hoạt động định trước.
Một automaton với một số trạng thái hữu hạn được gọi là Finite Automaton (FA) hoặc Finite State Machine (FSM).
Định nghĩa chính thức về Automaton hữu hạn
Một automaton có thể được biểu diễn bằng 5 bộ (Q, ∑, δ, q 0 , F), trong đó -
Q là một tập hợp hữu hạn các trạng thái.
∑ là một tập hợp hữu hạn các ký hiệu, được gọi là alphabet của ô tô.
δ là hàm chuyển tiếp.
q0là trạng thái ban đầu mà từ đó bất kỳ đầu vào nào được xử lý (q 0 ∈ Q).
F là tập hợp các trạng thái / trạng thái cuối cùng của Q (F ⊆ Q).
Các thuật ngữ liên quan
Bảng chữ cái
Definition - An alphabet là bất kỳ bộ ký hiệu hữu hạn nào.
Example - ∑ = {a, b, c, d} là một alphabet set trong đó 'a', 'b', 'c' và 'd' là symbols.
Chuỗi
Definition - A string là một dãy hữu hạn các ký hiệu lấy từ ∑.
Example - 'cabcad' là một chuỗi hợp lệ trên bộ chữ cái ∑ = {a, b, c, d}
Chiều dài của một chuỗi
Definition- Là số lượng ký hiệu có trong một chuỗi. (Đóng góp bởi|S|).
Examples -
Nếu S = 'cabcad', | S | = 6
Nếu | S | = 0, nó được gọi là empty string (Đóng góp bởi λ hoặc là ε)
Kleene Star
Definition - Ngôi sao Kleene, ∑*, là toán tử một ngôi trên một tập hợp các ký hiệu hoặc chuỗi, ∑, điều đó cung cấp cho tập hợp vô hạn tất cả các chuỗi có thể có tất cả các độ dài có thể ∑ kể cả λ.
Representation- ∑ * = ∑ 0 ∪ ∑ 1 ∪ ∑ 2 ∪ ……. trong đó ∑ p là tập hợp tất cả các chuỗi có thể có độ dài p.
Example - Nếu ∑ = {a, b}, ∑ * = {λ, a, b, aa, ab, ba, bb, ……… ..}
Kleene Closure / Plus
Definition - Bộ ∑+ là tập hợp vô hạn của tất cả các chuỗi có thể có tất cả các độ dài có thể trên ∑ không bao gồm λ.
Representation- ∑ + = ∑ 1 ∪ ∑ 2 ∪ ∑ 3 ∪ …….
∑ + = ∑ * - {λ}
Example- Nếu ∑ = {a, b}, ∑ + = {a, b, aa, ab, ba, bb, ……… ..}
Ngôn ngữ
Definition- Một ngôn ngữ là một tập hợp con của ∑ * cho một số bảng chữ cái ∑. Nó có thể là hữu hạn hoặc vô hạn.
Example - Nếu ngôn ngữ nhận tất cả các chuỗi có thể có độ dài 2 trên ∑ = {a, b} thì L = {ab, aa, ba, bb}