NFA accepter

The first automaton becomes non-deterministic if we add the transition $\delta(q_1, b)=q_5$. That means we can go from q1 with b in either q3 or q5.

This makes the automaton accept the word bb.

Implementation

• A cell in the transition matrix $\delta$ will not be a single state $q2$, it will be a set of states ${ q_3, q_5 }$.
• The current_state will no longer be a single state, it will be a set of states. When consuming a symbol x, move each of the current state $q$ to where $\delta(q, x)$ points (it is a list as well).

IO

4 5
0 a 2
0 b 1
1 b 2
1 b 5
2 c 3
3 a 3
3 b 4
3 c 5

acaaab
bbcb
bb

acaa
bab

1
1
1

0
0

L-NFA accepter

The first automaton becomes a λ-NFA if we add the transition $\delta(q_2, \lambda)=q_4$. That means we can go from q2 with λ (consuming no additional symbol from the word) in q4.

This makes the automaton accept the word a ($q_0 \rightarrow q_2 \rightarrow q_4$).

Implementation

• The transition matrix $\delta$ can be extended with an additional column $\lambda$.
• When consuming a symbol x, from the current state $q$, also consider states $s$ reachable by $\lambda$ ($\delta(q, \lambda) = s$)
• Treat the situation when $\delta(q, \lambda)=s$ and $\delta(s, \lambda)=r$. That means $r$ is also λ-reachable from $q$.

IO

4 5
0 a 2
0 b 1
1 b 2
2 c 3
2 _ 4
3 a 3
3 b 4
3 c 5

acaaab
bbcb
a

acaa
bab

1
1
1

0
0