6
$\begingroup$

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 ?

$\endgroup$
2
  • $\begingroup$ Can you transcribe the image into text? This will enable the search feature to access the text in the image. $\endgroup$ Oct 1, 2017 at 16:21
  • $\begingroup$ @YuvalFilmus : Yes sure $\endgroup$ Oct 1, 2017 at 16:41

1 Answer 1

9
$\begingroup$

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).

$\endgroup$
9
  • $\begingroup$ epsilon closure is a set of states which are always in M or may lie outside M ? $\endgroup$ Oct 1, 2017 at 16:16
  • $\begingroup$ The $\epsilon$-close of $M$ consists of all states you can reach from $M$ by taking zero or more $\epsilon$-transitions. $\endgroup$ Oct 1, 2017 at 16:20
  • $\begingroup$ : So they may not be included in M , right ? $\endgroup$ Oct 1, 2017 at 16:39
  • $\begingroup$ Any suggestions as to why in the defintion of e-closure has he termed "t" to be set of all transitions . As per the way the notation is understood shouldn't it be a set of states ? $\endgroup$ Oct 1, 2017 at 16:41
  • $\begingroup$ I added a paragraph with the meaning of the notation. In fact, $t$ is a single state. $\endgroup$ Oct 1, 2017 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.