NFA operation with example

Question

Explain briefly NFA operation with example.

Answer 1

Example of NFA operation:

alphabet Σ = {0,1}

input: 0 1 0
not accepted

input: 1 1 0
accepted

One way to think of NFA operation:

string x = x₁ x₂ x₃ … x_n accepted if and only if

–there exists a way of inserting ε’s into x
x₁ εε x₂ x₃…ε x_n

– so that there exists a path of transitions from the start state to an accept state.