Understanding definition of epsilon closure and finite automata states

Question

I am going through the book , introduction to compiler design , by Torben Ægidius Mogensen.

It provides the following definition of an epsilon closure :

Given a set M of NFA states, we define $\ \epsilon $-closure($\ M $) to be the least (in terms of the subset relation) solution to the set equation $\ \epsilon $-closure($\ M $) =$\ M $ $\ \cup $ {$\ t $|$\ s $ ∈ $\ \epsilon $-closure($\ M $) and $\ s^\epsilon t$∈T}, where T is the set of transitions in the NFA.

Initially , it defined the notion $\ a^b c $ to mean that a transition from state $\ a $ to $\ b$ takes place when a symbol $\ c $ is encountered .

But in the above definition $\ s^\epsilon t $ , $\ t$ is an element of the set of transitions , not the set of states .

This has resulted in a bit of confusion as to what exactly does an epsilon closure mean .

One more terminology word-play that wanted to be clear about is , the exact meaning of a sentence of the following sort :

"We extend the set of NFA states with those you can reach from these by using only epsilon transitions ."

But in a set of NFA states , the epsilon transition would direct one state to another which would be already included in the set of NFA states. So , how is it possible to extend the same set with the elements already contained in it ?

Answer 1

Your textbook is being very formal, probably since it aims at using set equations later on. However, $\epsilon$-closure is a very simple concept. The $\epsilon$-closure of a set $M$ of states is the collection of states that can be reached from a state in $M$ by taking any number of $\epsilon$-transitions (possibly zero).

The textbook uses a different (but equivalent) definition: it defines the $\epsilon$-closure of $M$ to be the smallest set of states that contains $M$ and that for every state $s$ that it contains, contains all states reachable from $s$ by a single $\epsilon$-transition.

Regarding the second quote, there is some context missing. Here is one possible context which would make sense. For an NFA without $\epsilon$-transitions, we define $\delta(q,a)$ to be the set of states that can be reached from $q$ by taking a transition labeled $a$. When we have $\epsilon$-transitions, there are several different possible definitions of the transition function. One possibility is to define $\delta(q,a)$ to be the set of states that can be reached from $q$ by taking a transition labeled $a$ and then an arbitrary number of transitions labeled $\epsilon$ (possibly none).