Chuyển đổi NDFA sang DFA

Báo cáo vấn đề

Để cho X = (Q_x, ∑, δ_x, q₀, F_x)là NDFA chấp nhận ngôn ngữ L (X). Chúng tôi phải thiết kế một DFA tương đươngY = (Q_y, ∑, δ_y, q₀, F_y) như vậy mà L(Y) = L(X). Quy trình sau đây chuyển đổi NDFA thành DFA tương đương của nó:

Thuật toán

Input - NDFA

Output - Một DFA tương đương

Step 1 - Tạo bảng trạng thái từ NDFA đã cho.

Step 2 - Tạo một bảng trạng thái trống dưới các bảng chữ cái đầu vào có thể có cho DFA tương đương.

Step 3 - Đánh dấu trạng thái bắt đầu của DFA bằng q0 (Giống như NDFA).

Step 4- Tìm ra sự kết hợp của các Kỳ {Q ₀ , Q ₁ , ..., Q _n } cho mỗi bảng chữ cái đầu vào có thể có.

Step 5 - Mỗi khi chúng tôi tạo một trạng thái DFA mới dưới các cột bảng chữ cái đầu vào, chúng tôi phải áp dụng lại bước 4, nếu không thì chuyển sang bước 6.

Step 6 - Các trạng thái chứa bất kỳ trạng thái cuối cùng nào của NDFA là trạng thái cuối cùng của DFA tương đương.

Thí dụ

Chúng ta hãy xem xét NDFA được thể hiện trong hình bên dưới.

q	δ (q, 0)	δ (q, 1)
a	{a, b, c, d, e}	{d, e}
b	{c}	{e}
c	∅	{b}
d	{e}	∅
e	∅	∅

Sử dụng thuật toán trên, chúng tôi tìm thấy DFA tương đương của nó. Bảng trạng thái của DFA được hiển thị bên dưới.

q	δ (q, 0)	δ (q, 1)
[a]	[a, b, c, d, e]	[d, e]
[a, b, c, d, e]	[a, b, c, d, e]	[b, d, e]
[d, e]	[e]	∅
[b, d, e]	[c, e]	[e]
[e]	∅	∅
[c, e]	∅	[b]
[b]	[c]	[e]
[c]	∅	[b]

Biểu đồ trạng thái của DFA như sau: