CS 373: Lecture Schedule


There is a small error in the conversion from NFA with epsilon transitions to an NFA without epsilon transitions.

On the last slide (slide 12), delta'(q,a), takes a state q and a letter a, and goes to any state in the epsilon closure of p, where p is in delta(q,a).

Intuitively, the above says that if you can do an a-transition from p followed by some number of epsilon transitions and reach q, then you should be able to reach q directly from p on reading an a. However, we need to allow taking epsilon transitions before the a-transition as well. In other words, we need say that if you can do some number of epsilon transitions from p, and then do an a-transition and then do a number of epsilon transitions and reach q, then you should be able to reach q directly from p on reading an a.

Formally, delta(q,a) = { p | \exists q1,q2 such that q1 \in EpsCl(q), delta(q1,a)=q2, and p \in EpsCl(q2)}.