Giảm thiểu DFA
Giảm thiểu DFA bằng Định lý Myphill-Nerode
Thuật toán
Input - DFA
Output - DFA giảm thiểu
Step 1- Vẽ một bảng cho tất cả các cặp trạng thái (Q i , Q j ) không nhất thiết phải kết nối trực tiếp [Tất cả đều không được đánh dấu ban đầu]
Step 2- Xem xét mọi cặp trạng thái (Q i , Q j ) trong DFA trong đó Q i ∈ F và Q j ∉ F hoặc ngược lại và đánh dấu chúng. [Ở đây F là tập hợp các trạng thái cuối cùng]
Step 3 - Lặp lại bước này cho đến khi chúng ta không thể đánh dấu trạng thái nữa -
Nếu có một cặp chưa được đánh dấu (Q i , Q j ), hãy đánh dấu nó nếu cặp {δ (Q i , A), δ (Q i , A)} được đánh dấu cho một số bảng chữ cái đầu vào.
Step 4- Kết hợp tất cả các cặp không được đánh dấu (Q i , Q j ) và biến chúng thành một trạng thái duy nhất trong DFA giảm.
Thí dụ
Hãy để chúng tôi sử dụng Thuật toán 2 để giảm thiểu DFA được hiển thị bên dưới.
Step 1 - Chúng tôi vẽ một bảng cho tất cả các cặp trạng thái.
| a | b | c | d | e | f | |
| a | ||||||
| b | ||||||
| c | ||||||
| d | ||||||
| e | ||||||
| f |
Step 2 - Chúng tôi đánh dấu các cặp trạng thái.
| a | b | c | d | e | f | |
| a | ||||||
| b | ||||||
| c | ✔ | ✔ | ||||
| d | ✔ | ✔ | ||||
| e | ✔ | ✔ | ||||
| f | ✔ | ✔ | ✔ |
Step 3- Chúng tôi sẽ cố gắng đánh dấu các cặp trạng thái, với dấu kiểm màu xanh lá cây, chuyển tiếp. Nếu chúng ta nhập 1 vào trạng thái 'a' và 'f', nó sẽ chuyển sang trạng thái 'c' và 'f' tương ứng. (c, f) đã được đánh dấu, do đó chúng ta sẽ đánh dấu cặp (a, f). Bây giờ, chúng ta nhập 1 vào trạng thái 'b' và 'f'; nó sẽ chuyển sang trạng thái 'd' và 'f' tương ứng. (d, f) đã được đánh dấu, do đó chúng ta sẽ đánh dấu cặp (b, f).
| a | b | c | d | e | f | |
| a | ||||||
| b | ||||||
| c | ✔ | ✔ | ||||
| d | ✔ | ✔ | ||||
| e | ✔ | ✔ | ||||
| f | ✔ | ✔ | ✔ | ✔ | ✔ |
Sau bước 3, chúng ta có các tổ hợp trạng thái {a, b} {c, d} {c, e} {d, e} không được đánh dấu.
Chúng ta có thể kết hợp lại {c, d} {c, e} {d, e} thành {c, d, e}
Do đó, chúng tôi có hai trạng thái kết hợp là - {a, b} và {c, d, e}
Vì vậy, DFA thu nhỏ cuối cùng sẽ chứa ba trạng thái {f}, {a, b} và {c, d, e}
Giảm thiểu DFA sử dụng Định lý Tương đương
Nếu X và Y là hai trạng thái trong DFA, chúng ta có thể kết hợp hai trạng thái này thành {X, Y} nếu chúng không thể phân biệt được. Hai trạng thái có thể phân biệt được, nếu có ít nhất một chuỗi S, sao cho một trong hai chuỗi δ (X, S) và δ (Y, S) đang chấp nhận và một chuỗi khác không chấp nhận. Do đó, DFA là tối thiểu nếu và chỉ khi tất cả các trạng thái đều có thể phân biệt được.
Thuật toán 3
Step 1 - Tất cả các tiểu bang Q được chia thành hai phân vùng - final states và non-final states và được ký hiệu bởi P0. Tất cả các trạng thái trong một phân vùng là tương đương thứ 0 . Tính tiềnk và khởi tạo nó bằng 0.
Step 2- Tăng k bằng 1. Với mỗi phân hoạch trong P k , chia các trạng thái trong P k thành hai phân hoạch nếu chúng phân biệt được k. Hai trạng thái trong phân vùng này X và Y không phân biệt được nếu có một đầu vàoS như vậy mà δ(X, S) và δ(Y, S) là (k-1) -không thể phân biệt được.
Step 3- Nếu P k ≠ P k-1 , lặp lại Bước 2, nếu không thì chuyển sang Bước 4.
Step 4- Kết hợp k thứ bộ tương đương và làm cho họ các bang mới của giảm DFA.
Thí dụ
Chúng ta hãy xem xét DFA sau:
| q | δ (q, 0) | δ (q, 1) |
|---|---|---|
| a | b | c |
| b | a | d |
| c | e | f |
| d | e | f |
| e | e | f |
| f | f | f |
Hãy để chúng tôi áp dụng thuật toán trên cho DFA ở trên -
- P 0 = {(c, d, e), (a, b, f)}
- P 1 = {(c, d, e), (a, b), (f)}
- P 2 = {(c, d, e), (a, b), (f)}
Do đó, P 1 = P 2 .
Có ba trạng thái trong DFA giảm. DFA giảm như sau:
| Q | δ (q, 0) | δ (q, 1) |
|---|---|---|
| (a, b) | (a, b) | (c, d, e) |
| (c, d, e) | (c, d, e) | (f) |
| (f) | (f) | (f) |