λ-NFA to NFA

Starting from a λ-NFA, build an equivalent NFA by removing its λ-transitions.

The idea: from state $q$ if we can reach $r$ via λ and $r$ can reach $s$ via a

It means $q$ can reach $s$ via a

Original automaton

We will convert the following λ-NFA:

l-nfa

Which accepts zero or more abs — language: $(ab)*$. Example accepted words: ab, abab, ababab, λ. Transition table:

$\delta$ a b $\bf{\lambda}$
$\bf{q_0}$     $q_1,q_5$
$\bf{q_1}$ $q_2$    
$\bf{q_2}$     $q_3$
$\bf{q_3}$   $q_4$  
$\bf{q_4}$     $q_1,q_5$
$\bf{q_5}$      

λ-closure

The states that $q$ can reach only by λ-transitions.

$q$ is always in its λ-closure — by doing no transitions, we stay in the same state.

state $\bf{\lambda *}$
$\bf{q_0}$ $q_0, q_1, q_5$
$\bf{q_1}$ $q_1$
$\bf{q_2}$ $q_2, q_3$
$\bf{q_3}$ $q_3$
$\bf{q_4}$ $q_4, q_5, q_1$
$\bf{q_5}$ $q_5$

Attention: the λ-closure does not include only states reachable in one λ-transition, it also includes states λ-reachable from those states as well. Example:

That means $q$ can reach $s$ via λ*, $s \in λ \text{-} closure(q)$.

Transition function

A state $q$ with symbol $x$ can reach all the states resulted from computing: In our case, $x$ can be either a or b.

For symbol a

$\delta_a’$ $\bf{\lambda *}$ a $\bf{\lambda *}$
$\bf{q_0}$ $q_0, q_1, q_5$ $q_2$ $q_2, q_3$
$\bf{q_1}$ $q_1$ $q_2$ $q_2, q_3$
$\bf{q_2}$ $q_2, q_3$    
$\bf{q_3}$ $q_3$    
$\bf{q_4}$ $q_4, q_5, q_1$ $q_2$ $q_2, q_3$
$\bf{q_5}$ $q_5$    

The first column is actually the λ-closure.

For the first row ($q0$), the second column contains all the states reachable from $q_0$ and $q_1$ ($λ \text{-} closure(q_0)$) with a. For the third row ($q_2$), the second column contains nothing as neither $q_2$ nor $q_3$ can reach anything with a.

To get the last column, we combine the λ-closures of all the states in the a column. Since the rows for $q2$, $q_3$ and $q_5$ are blank on the a column, they will be blank in the last column as well.

For symbol b

$\delta_b’$ $\bf{\lambda *}$ b $\bf{\lambda *}$
$\bf{q_0}$ $q_0, q_1, q_5$    
$\bf{q_1}$ $q_1$    
$\bf{q_2}$ $q_2, q_3$ $q_4$ $q_4, q_5, q_1$
$\bf{q_3}$ $q_3$ $q_4$ $q_4, q_5, q_1$
$\bf{q_4}$ $q_4, q_5, q_1$    
$\bf{q_5}$ $q_5$    

Only the row containing $q_3$ in its λ-closure needs to be completed, as $q_3$ is the only function that can transition on b.

Resulting table

Looking at the last column in table a, we see that $q_0$ can reach $q_2$ and $q_3$ (and so can $q_1$ and $q_4$). For symbol b, $q_2$ can reach $q_1$, $q_4$ and $q_5$.

$\delta’$ a b
$\bf{q_0}$ $q_2, q_3$  
$\bf{q_1}$ $q_2, q_3$  
$\bf{q_2}$   $q_1, q_4, q_5$
$\bf{q_3}$   $q_1, q_4, q_5$
$\bf{q_4}$ $q_2, q_3$  
$\bf{q_5}$    

Starting and accepting states

The starting state remains $q_0$.

A state is accepting iff it has an accepting state (in the original automaton) in its λ-closure. In our case, the original automaton had only one accepting state, $q_5$ which can be reached via λ from $q_1$ or $q_4$ (or itself).

Redundant states removal

Two states are redundant if they have the same row in the transition table — their go via a to the same states, via b to the same states and are either both accepting or both non-accepting.

From the resulting table, we can simply delete the rows of such states: $q_0$ and $q_4$ both go to $\langle q_2, q_3 \rangle$ via a; nowhere via b and are both accepting — so we keep only $q_0$. We also replace $q_4$ with $q_0$ everywhere else it appears in the transition table. Next, out of $q_2$ and $q_3$, we only keep $q_3$, following the same steps.

Note: this is an optional step. The automaton functions exactly the same but readability is highly increased.

Converted automaton

We obtained a simpler NFA for the same language $(ab)*$

nfa

Cleaned transition table:

$\delta’$ a b accepting
$\rightarrow \bf{q_0}$ $q_2$  
$\bf{q_1}$ $q_2$    
$\bf{q_2}$   $q_0, q_1, q_5$  
$\bf{q_5}$    

IO

Read the definition of a λ-NFA and print the definition of an equivalent NFA.

Input LNFA.definition
5
0 _ 1
0 _ 5
1 a 2
2 _ 3
3 b 4
4 _ 5
4 _ 1

Accepting states on the first line; entries in the transition table on subsequent lines.

Example output NFA.definition
0 5
0 b 2
2 b 0
2 b 1
2 b 5
1 a 2
2 b 5

Definition of the NFA. It is not the only NFA equivalent to the original λ-NFA — depending on the method you chose, your output may vary.

To verify equivalence we would have to check the output of both atomata on every possible input. Since this is an infinite set, we will settle with just a small relevant subset.

Input NFA.tests
ab
abab
ababab
_

a
ba
aba
abb
bbb
aaa
1
1
1
1

0
0
0
0
0
0

Words to test on the converted automaton.

Another conversion

Language: $(a | b){*}\ a$

Narrated video (direct λ-NFA to DFA conversion)

Input LNFA.definition
8
0 _ 1
0 _ 7
1 _ 2
1 _ 4
2 a 3
3 _ 6
4 b 5
5 _ 6
6 _ 1
6 _ 7
7 a 8
Input NFA.tests
a
aaaa
bba
aabba
bbaa
ababa
babaa
baaaba

b
bbb
ab
aaaab
abab
bbab
1
1
1
1
1
1
1
1

0
0
0
0
0
0

More examples

Narrated transformations: