Every DFA is NFA:


NFA (Q, Σ , δ,  q0, F)

δ: Q X (Σ ∪ {λ}) → 2Q or P(Q)

DFA (Q, Σ, δ,  q0, F)

δ : Q X Σ → Q


There are all tuples are the same except the δ transition function. We can say that every DFA is NFA. Because DFA satisfies δ : Q X Σ → Q, all moves satisfy the condition.


So, we can say if satisfy δ : Q X Σ → Q  then it also satisfies δ: Q X (Σ ∪ {λ}) → 2Q or P(Q) because Q also belongs to P(Q).

We also take δ: Q X (Σ ∪ {λ}) → 2Q  So, here Σ is also belongs to (Σ  ∪ {λ}). So, every DFA is NFA but every NFA is not DFA


Then    DFA ⇒ NFA


Example: Σ = {a, b}   Smallest NFA


L = ɸ = { } i.e. from above all machine.

From the above example, it is clear that for one language more than one machine can exist.


But always one machine only one Language.


Power of DFA and NFA is same because we can convert NFA to DFA.

We can say two machines have same power if we can convert one machine to another.