Xây dựng FA từ RE
Chúng ta có thể sử dụng Thompson's Construction để tìm ra một Automaton hữu hạn từ một Biểu thức chính quy. Chúng tôi sẽ giảm biểu thức chính quy thành các biểu thức chính quy nhỏ nhất và chuyển đổi chúng thành NFA và cuối cùng là DFA.
Một số biểu thức RA cơ bản như sau:
Case 1 - Đối với một biểu thức chính quy 'a', chúng ta có thể xây dựng FA sau:
Case 2 - Đối với một biểu thức chính quy 'ab', chúng ta có thể xây dựng FA sau:
Case 3 - Đối với một biểu thức chính quy (a + b), chúng ta có thể xây dựng FA sau:
Case 4 - Đối với biểu thức chính quy (a + b) *, chúng ta có thể xây dựng FA sau:
phương pháp
Step 1 Xây dựng NFA với Null di chuyển từ biểu thức chính quy đã cho.
Step 2 Xóa chuyển đổi Null khỏi NFA và chuyển đổi nó thành DFA tương đương.
Problem
Chuyển đổi RA sau thành DFA tương đương - 1 (0 + 1) * 0
Solution
Chúng tôi sẽ nối ba biểu thức "1", "(0 + 1) *" và "0"
Bây giờ chúng tôi sẽ xóa εchuyển tiếp. Sau khi chúng tôi loại bỏε chuyển đổi từ NDFA, chúng tôi nhận được những điều sau:
Nó là NDFA tương ứng với RE-1 (0 + 1) * 0. Nếu bạn muốn chuyển nó thành DFA, chỉ cần áp dụng phương pháp chuyển đổi NDFA thành DFA được thảo luận trong Chương 1.
Dữ liệu tự động hữu hạn với Null Moves (NFA-ε)
Một Automaton hữu hạn với các chuyển động rỗng (FA-ε) không chỉ chuyển tiếp sau khi đưa ra đầu vào từ bộ bảng chữ cái mà còn không có bất kỳ ký hiệu đầu vào nào. Quá trình chuyển đổi không có đầu vào này được gọi lànull move.
NFA-ε được biểu diễn chính thức bởi một bộ 5 (Q, ∑, δ, q 0 , F), bao gồm
Q - một tập hợp hữu hạn các trạng thái
∑ - một tập hợp hữu hạn các ký hiệu đầu vào
δ- một hàm chuyển tiếp δ: Q × (∑ ∪ {ε}) → 2 Q
q0- trạng thái ban đầu q 0 ∈ Q
F - một tập hợp các trạng thái / trạng thái cuối cùng của Q (F⊆Q).
Trên (FA-ε) chấp nhận một tập hợp chuỗi - {0, 1, 01}
Loại bỏ Null Moves khỏi dữ liệu tự động hữu hạn
Nếu trong NDFA, có sự di chuyển giữa đỉnh X sang đỉnh Y, chúng ta có thể loại bỏ nó bằng cách sử dụng các bước sau:
- Tìm tất cả các cạnh đi ra từ Y.
- Sao chép tất cả các cạnh này bắt đầu từ X mà không thay đổi nhãn cạnh.
- Nếu X là trạng thái ban đầu thì Y cũng là trạng thái ban đầu.
- Nếu Y là trạng thái cuối cùng thì X cũng là trạng thái cuối.
Problem
Chuyển đổi NFA-ε sau thành NFA mà không cần di chuyển Null.
Solution
Step 1 -
Đây là quá trình chuyển đổi giữa q1 và q2, vì vậy hãy q1 Là X và qf Là Y.
Ở đây các cạnh đi ra từ q f là q f cho các đầu vào 0 và 1.
Step 2 -
Bây giờ chúng ta sẽ Sao chép tất cả các cạnh này từ q 1 mà không thay đổi các cạnh từ q f và nhận được FA sau:
Step 3 -
Ở đây q 1 là một trạng thái ban đầu, vì vậy chúng ta làm cho q f cũng là một trạng thái ban đầu.
Vì vậy, FA trở thành -
Step 4 -
Ở đây q f là một trạng thái cuối cùng, vì vậy chúng ta làm cho q 1 cũng là một trạng thái cuối cùng.
Vì vậy, FA trở thành -
