Automaton hữu hạn xác định

Automaton hữu hạn có thể được phân thành hai loại:

• Automaton hữu hạn xác định (DFA)
• Automaton hữu hạn không xác định (NDFA / NFA)

Automaton hữu hạn xác định (DFA)

Trong DFA, đối với mỗi ký hiệu đầu vào, người ta có thể xác định trạng thái mà máy sẽ di chuyển. Do đó, nó được gọi làDeterministic Automaton. Vì nó có một số trạng thái hữu hạn, máy được gọi làDeterministic Finite Machine hoặc là Deterministic Finite Automaton.

Định nghĩa chính thức về DFA

Một DFA có thể được biểu diễn bằng 5 bộ (Q, ∑, δ, q ₀ , 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à bảng chữ cái.

• δ là hàm chuyển đổi trong đó δ: Q × ∑ → Q

• q₀là trạng thái ban đầu mà từ đó bất kỳ đầu vào nào được xử lý (q ₀ ∈ 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).

Biểu diễn đồ họa của một DFA

DFA được biểu thị bằng các đồ thị được gọi là state diagram.

• Các đỉnh đại diện cho các trạng thái.
• Các cung được gắn nhãn với bảng chữ cái đầu vào hiển thị các chuyển đổi.
• Trạng thái ban đầu được biểu thị bằng một cung tới trống.
• Trạng thái cuối cùng được biểu thị bằng các vòng tròn đôi.

Thí dụ

Cho một tự động hữu hạn xác định là →

• Q = {a, b, c},
• ∑ = {0, 1},
• q ₀ = {a},
• F = {c} và

Hàm chuyển đổi δ được thể hiện trong bảng sau:

Trạng thái hiện tại	Trạng thái tiếp theo cho đầu vào 0	Trạng thái tiếp theo cho đầu vào 1
a	a	b
b	c	a
c	b	c

Biểu diễn đồ họa của nó sẽ như sau: