FA19:Lecture 27 Non-determinism

From CS2800 wiki


We covered this material slightly differently this semester than we did last semester: we introduced NFA with [math]\epsilon [/math] transitions directly; in the past I have started with NFA without [math]\epsilon [/math] transitions.

It will take some time for me to update the lecture notes. In the meantime, see the FA17 notes for the definition of NFA without [math]\epsilon [/math] transitions.

An [math]\epsilon [/math] transition from one state to another allows the NFA to transition from one state to another "for free". See the lecture slides for the formal definitions and examples.