7
Nie można znaleźć niczego pozytywnego na ten temat. A NFA z jakimkolwiek przejściem epsilon to epsilon-NFA? Dzięki.Czy DFA ma przejścia epsilon/lambda?
A
Odpowiedz
9
DFA nie ma przejść epsilon.Jeśli to posiada, może przechodzić z bieżącego stanu do innego stanu bez żadnego wejścia, tj. Bez niczego, nawet {} lub phi. Zgodnie z definicją wiemy, że dane wejściowe muszą pochodzić z zestawu wejściowego. Mam nadzieję, że to rozwiało wątpliwości ...
+0
Co by było, gdyby przejście miało stan końcowy? Jak na rysunku 3.51 na stronie 225 tego dokumentu http://www.univasf.edu.br/~marcus.ramos/lfa-2008-1/Secao%2003-06.pdf. – liwing
+0
Wow ... obraz jest już oczywisty ... jak widzisz, q0 przechodzi do q3 bez żadnego wejścia, a więc jest NFA i ma ruchy epsilon, więc jest to epsilon-NFA, a nie DFA .. –
+0
Dzięki za wyjaśnienie – liwing
2
DFA musi mieć określony symbol wejściowy, aby przejść z jednego stanu do drugiego. Ruch Epsilon nie jest dozwolony w DFA, ponieważ zmieni DFA w NFA. Dla przykładu, załóżmy, że jesteś w stanie Q1 i masz przejście (Q1, e) = Q2, w tym przypadku możesz bezpośrednio przejść do Q2 bez stosowania jakichkolwiek danych wejściowych lub możesz pozostać w stanie Q1, więc masz dwie możliwości wyboru w stanie Q1. W przypadku DFA nie możesz mieć żadnych kryteriów wyboru. Właśnie dlatego DFA nie ma ruchów epsilon.
2
Z definicji DFA "Deterministic Finite Automata to maszyna, która nie może przejść do innego stanu bez uzyskania jakichkolwiek danych wejściowych". A ponieważ epsilon nic nie znaczy. Dlatego DFA nie może poruszać się na ruchach epsilon.
Podczas gdy z definicji NFA: "Non deterministic Finite Automata to maszyna, która może poruszać się w innym stanie, nie uzyskując żadnych danych wejściowych". Tak więc NFA może poruszać się na ruchach epsilon.
Co masz na myśli przez przejście lambda? –
Niektóre książki używają lambda zamiast epsilon. To jest to samo. – liwing