The effect about empty string in NFA

906 Views Asked by At

I am learning Sipser's book "Introduction to the Theory of Computation" on automata theory. I am confused about the effect about empty string in NFA when reading the first chapter

There is a state diagram of nondeterministic finite automaton N1 Nondeterministic finite automaton N1

If we feed string "010110" into N1 Then as showed in the book, the computation process will be

The computation of N1 on input 010110

I can't get understand that when N1 read the second symbol from string,that is "1", the state "q1" should split into "q1" and "q2". Why there exist also "q3"

The principle of computation involving "empty string" is described as "If a state with an symbol on some exiting arrow is encountered, the machine split into multiple copies without reading any input"

1

There are 1 best solutions below

0
On BEST ANSWER

You can reach $q_3$ from $q_1$ by reading $1$ followed by $\varepsilon$ as follows $q_1 \xrightarrow{1} q_2 \xrightarrow{\varepsilon} q_3$.