0.2 Ôtômat hữu hạn và biểu thức chính quy  (Page 9/16)

(q : là một trạng thái của NFA, T : là tập trạng thái của NFA)

a) e-closure(q) : là tập trạng thái của NFA đạt được từ trạng thái q trên sự truyền rỗng.

b) e-closure(T) : là tập trạng thái của NFA đạt được từ tất cả các trạng thái q thuộc tập T trên sự truyền rỗng.

c) d(T, a) : là tập trạng thái của NFA đạt được từ tất cả các trạng thái q thuộc tập T trên sự truyền bằng ký hiệu a.

Phân tích:

Trước khi đọc vào một ký tự nhập, DFA có thể ở một trạng thái bất kỳ trong các trạng thái thuộc e-closure(q0) với q0 là trạng thái bắt đầu của NFA. Gọi trạng thái này là T. Giả sử các trạng thái của T là các trạng thái đạt được từ q0 trên các ký hiệu nhập và giả sử a là ký hiệu nhập kế tiếp. Khi đọc a, NFA có thể chuyển đến một trạng thái bất kỳ trong tập trạng thái d(T, a). Khi chúng ta cho phép sự truyền rỗng, NFA có thể ở bất kỳ trạng thái nào trong e-closure(d(T, a)) sau khi đã đọc a.

Giải thuật :

Trạng thái bắt đầu -closure(q0) chỉ là một trạng thái trong các trạng thái

của DFA và trạng thái này chưa được đánh dấu;

While Có một trạng thái T của DFA chưa được đánh dấu do

Begin

Đánh dấu T; { xét trạng thái T}

For Với mỗi ký hiệu nhập a do

begin

U:= -closure((T, a))

If U không có trong tập trạng thái của DFA then

begin

Thêm U vào tập các trạng thái của DFA và trạng thái

này chưa được đánh dấu;

[T, a] := U; {[T, a]là phần tử của bảng chuyển DFA}end;

end;

End;

Ta xây dựng các trạng thái và bảng hàm chuyển cho DFA theo cách như sau :

- Mỗi trạng thái của DFA tượng trưng bởi một tập trạng thái của NFA mà NFA có thể chuyển đến sau khi đọc một chuỗi ký hiệu nhập gồm: tất cả sự truyền rỗng có thể xảy ra trước hoặc sau các ký hiệu được đọc.

- Trạng thái bắt đầu của DFA là e-closure(q0)

- Các trạng thái và hàm chuyển sẽ được thêm vào D bằng giải thuật trên.

- Một trạng thái của DFA là trạng thái kết thúc nếu nó là tập các trạng thái của NFA chứa ít nhất một trạng thái kết thúc của NFA.

Việc tính toán e-closure(T) có thể xem như quá trình tìm kiếm một đồ thị của các nút từ các nút cho trước và đồ thị bao gồm toàn những cạnh có nhãn e của NFA. Giải thuật đơn giản để tìm e-closure(T) là dùng Stack để lưu giữ các trạng thái mà cạnh của chúng chưa được kiểm tra cho sự truyền rỗng.

Thí dụ 3.10 : Tạo DFA từ NFAe sau

Hình 3.6 – Thí dụ chuyển NFA có -dịch chuyển

Các bước xây dựng tập trạng thái cho DFA :

1. Trạng thái bắt đầu của DFA : -closure(0) = {0, 1, 2, 4, 7} = A*
2. -closure((A, a)) = -closure({3, 8}) = {1, 2, 3, 4, 6, 7, 8} = B*
3. -closure((A, b)) = -closure({5}) = {1, 2, 4, 5, 6, 7} = C*
4. -closure((B, a)) = -closure({3, 8}) = B
5. -closure((B, b)) = -closure({5, 9}) = {1, 2, 4, 5, 6, 7, 9} = D*
6. -closure((C, a)) = -closure({3, 8}) = B
7. -closure((C, b)) = -closure({5}) = C
8. -closure((D, a)) = -closure({3, 8}) = B
9. -closure((D, b)) = -closure({5, 10}) = {1, 2, 4, 5, 6, 7, 10} = E*
10. -closure((E, a)) = -closure({3, 8}) = B
11. -closure((E, b)) = -closure({5}) = C

Từ các tập trạng thái này, ta xác định được A là trạng thái bắt đầu, E là trạng thái kết thúc (vì trong E có chứa trạng thái 10 là trạng thái kết thúc của NFA) và bảng hàm chuyển của DFA như sau :