# 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

## Input `NFA.definition`

```
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
```

Same format as above.

## Input `NFA.tests`

```
acaaab
bbcb
bb
acaa
bab
```

```
1
1
1
0
0
```

Same format as above.

# 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

## Input `LNFA.definition`

```
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
```

Same format as above.

## Input `LNFA.tests`

```
acaaab
bbcb
a
acaa
bab
```

```
1
1
1
0
0
```

Same format as above.