FA19:Lecture 27 Non-determinism

From CS2800 wiki
Revision as of 16:06, 4 November 2019 by {{GENDER:Mdg39|[math]'"2}} [/math]'"7
(<math>1) </math>2 | <math>3 (</math>4) | <math>5 (</math>6)


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.