Un DFA può avere transizioni epsilon/lambda?

Question

Non riesco a trovare nulla di positivo a riguardo. E un NFA con qualsiasi transizione epsilon è un epsilon-NFA? Grazie.

Answer 1

DFA non ha transizioni epsilon. Se ce l'avesse, potrebbe transitare dallo stato corrente ad altro stato senza alcun input, cioè con niente, nemmeno con {} o phi. E come definizione, sappiamo che l'input deve provenire dal set di input. Spero che questo chiarisca il tuo dubbio ...

Answer 2

DFA deve avere un simbolo di input definito per passare da uno stato a un altro stato. Epsilon Move non è consentito in DFA, perché cambierà DFA in NFA. Ad esempio, supponiamo di essere nello stato Q1 e di avere una transizione (Q1, e) = Q2, in questo caso puoi andare direttamente a Q2 senza applicare alcun input o puoi rimanere nello stato Q1, quindi hai due opportunità di scelta allo stato Q1. In caso di DFA non devi avere alcun criterio di scelta. Ecco perché DFA non ha mosse epsilon.

Answer 3

Dalla definizione di DFA, "Deterministic Finite Automata è una macchina che non può spostarsi su altro stato senza ottenere alcun input". E poiché epsilon non significa nulla. Quindi DFA non può muoversi su mosse epsilon.

Considerando che dalla definizione di NFA, "Automazione finita non deterministica è una macchina che può spostarsi su altro stato senza ottenere alcun input". Così NFA può spostarsi su mosse epsilon.