1
$\begingroup$

I was reading Compilers - Aho, Sethi, Ullman, and there is a point unclear.

First it defines the operations on NFA states:

$\epsilon$-closure(s) : Set of NFA states reachable from NFA state $s$ on $\epsilon$-transitions alone.
$\epsilon$-closure(T) : Set of NFA states reachable from some NFA state $s$ in $T$ on $\epsilon$-transitions alone.
$move(T,a)$ : Set of NFA states to which there is a transition on input symbol $a$ from some NFA state $s$ in $T$.

Then on the book follows this paragraph that I don't understand:

Before it sees the first input symbol, $N$ can be in any of the states in the set $\epsilon\mbox{-}closure(s_0)$, where $s_0$ is the start state of $N$. Suppose that exactly the states in the set $T$ are reachable from $s_0$ on a given sequence of input symbols, and let $a$ be the next input symbol. On seeing $a$, $N$ can move to any of the states in the set $move(T,a)$. When we allow for $\epsilon$-transitions, $N$ can be in any of the states in $\epsilon\mbox{-}closure(move(T,a))$, after seeing the $a$.

I have tried to comprehend it, and I considered the following N = NFA, accepting $(a|b)^*abb$:

3.27_aho.png

Let's analyse the paragraph phrase by phrase:

Before it sees the first input symbol, $N$ can be in any of the states in the set $\epsilon\mbox{-}closure(s_0)$, where $s_0$ is the start state of $N$.

If I understand, with $s_0 = 0$, before to process the first symbol, the NFA can be in one of the state of the set $\epsilon\mbox{-}closure(0) = \left \{ 1,2,4,7 \right \}$, i.e. the NFA can proceed only on the epsilon transitions without consuming any symbol.

Suppose that exactly the states in the set $T$ are reachable from $s_0$ on a given sequence of input symbols,

Since says from $s_0$, I think that it can be the initial part of the string, or the entire string. So a given sequence of input symbols can be in this case $aa$, and therefore $T=\left \{ 1, 2, 3, 6 \right \}$. And it stops in $3$ after the second $a$ is read.

and let $a$ be the next input symbol.

We consider $b$ as the next symbol of $aa$ (the given sequence of input symbols of the above).

On seeing $a$, $N$ can move to any of the states in the set $move(T,a)$.

So, the $a$ in the quote, is our $b$. Hence, on seeing $b$, the NFA can move to any of the states in the set $move(\left \{ 1, 2, 3, 6 \right \},b)$.
i.e. if we start from $1$ the states along the path to go to $b$ are
$move(1,b) = \left \{ 4, 5 \right \}$,
and in the same way:
$move(2,b) = \emptyset \\ move(3,b) = \left \{ 6, 1, 4, 5 \right \} \\ move(6,b) = \left \{ 1, 4, 5 \right \}$

When we allow for $\epsilon$-transitions, $N$ can be in any of the states in $\epsilon\mbox{-}closure(move(T,a))$, after seeing the $a$.

If I understand, when we allow for $\epsilon$-transitions, it means that, after the $b$ symbol is read, the NFA can stops in the next state if there is a epsilon transition to this next state. So,
$\epsilon\mbox{-}closure(move(\left \{ 1, 2, 3, 6 \right \},b))$ is the union of the following sets:
$\epsilon\mbox{-}closure(move(1, b)) = \left \{ 1,2,4,5,6,7 \right \}$ there is also $1,2$ because after $6$ it can returns to $1$ and then goes to $2$.
$\epsilon\mbox{-}closure(move(2, b)) = \emptyset$
$\epsilon\mbox{-}closure(move(3, b)) = \left \{ 1,2,4,5,6,7 \right \}$
$\epsilon\mbox{-}closure(move(6, b)) = \left \{ 1,2,4,5,6,7 \right \}$
so the $\epsilon\mbox{-}closure(move(T,b)) = \left \{ 1,2,4,5,6,7 \right \}$ unless for every $\epsilon\mbox{-}closure(move(t, b))$ we have to add $t$ itself and then the $\epsilon\mbox{-}closure(move(T,b)) = \left \{ 1,2,3,4,5,6,7 \right \}$.

Please, can you help me to understand better this argument? Many thanks, really! I know that it is basilar and easy topic, but, if you can do this kindness I would appreciate an helping hand and some advices from you! :) (And also I post here because, writing this kind of argument in the computer science sections means a lot of downvotes, because it is basilar, even if the fully comprehension of this argument can be useful to some other beginner guy out there!, however if you think that here is not the right place to post this argument, let me know it, I will try to post to another StackExch Community)

$\endgroup$

1 Answer 1

1
$\begingroup$

I think you got it all figured out already, I don't understand what exactly is your confusion, but I will try to rephrase the language in more mathematical terms

系-closure(s) = {s} U 系-closure(x) | there exists a 系-transition from x to s i.e 饾浛(s,系) = x

We include s in 系-closure(s) because its upto NFA to take or not take epislon transitions thus by not taking any epislon transitions it can remain at s

As you correctly interpreted,

系-closure(T) = $\bigcup_{ s 鈭 T} 系-closure(s) $

But

系-closure(move(t,b)) = $\bigcup_{ s 鈭 系-closure(t)} 系-closure(x) \ |\ 饾浛(s,b) = x $

which implies 系-closure(move(t,b)) may or may not include t, depending on the transitions

Now because before reading any symbol, since NFA is allowed to take epsilon-transitions it can be in any state in 系-closure(s0)

Now let on reading some characters NFA can reach from s0 to T.

Then on reading an next input a, it can obviously move to states move(T,a) = X(set of states).

Since it could have been on any of the state belonging to T.

Now Since we consider epsilon transitions without reading another symbol it can take epislon transitions to move from X to 系-closure(X) i.e 系-closure(mov(T,a)).

Now there are some issues in your analyzing of above NFA.

系-closure(0)={0,1,2,4,7} - you missed zero. //Check my definition above of closure

After Reading "aa"

T={1,2,3,4,6,7,8}

after reading b i.e

系-closure(mov(T,b)) = { 1,2,4,5,6,7,9}

I am new to SE,so apologies for bad formatting.
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .