DFA có chuyển tiếp epsilon/lambda không?

Question

Không thể tìm thấy bất cứ điều gì khẳng định về nó. Và một NFA với bất kỳ quá trình chuyển đổi epsilon là một epsilon-NFA? Cảm ơn.

Answer 1

DFA không có chuyển tiếp epsilon. Nếu có, nó có thể chuyển từ trạng thái hiện tại sang trạng thái khác mà không có bất kỳ đầu vào nào, tức là không có gì, thậm chí không {} hoặc phi. Và như định nghĩa, chúng ta biết rằng đầu vào phải từ tập hợp đầu vào. Hy vọng điều này sẽ xóa bỏ sự nghi ngờ của bạn ...

Answer 2

DFA phải có ký hiệu nhập xác định để chuyển từ trạng thái này sang trạng thái khác. Di chuyển Epsilon không được cho phép trong DFA, bởi vì nó sẽ thay đổi DFA thành NFA. Ví dụ: giả sử bạn đang ở trạng thái Q1 và bạn có chuyển tiếp (Q1, e) = Q2, trong trường hợp này bạn có thể trực tiếp đến Q2 mà không áp dụng bất kỳ đầu vào nào hoặc bạn có thể ở trạng thái Q1, vì vậy bạn có hai cơ hội lựa chọn tại tiểu bang Q1. Trong trường hợp của DFA, bạn không được có bất kỳ tiêu chí lựa chọn nào. Đó là lý do tại sao DFA không có động thái epsilon.

Answer 3

Từ định nghĩa của DFA, "Tự động hữu hạn xác định là một máy không thể di chuyển trên trạng thái khác mà không nhận được bất kỳ đầu vào nào" .Và vì epsilon có nghĩa là không có gì.Hence DFA không thể di chuyển trên epsilon.

Trong khi từ định nghĩa của NFA, "Không xác định hữu hạn tự động là một máy có thể di chuyển trên trạng thái khác mà không nhận được bất kỳ đầu vào". Do đó NFA có thể di chuyển trên di chuyển epsilon.