Question

Convert this language to a NFA

L(ab(a+b)*(a+aa))

Answer: the graph is as follows:

Question: How do you know when to insert lambda? Will give thumbs up :)

8 7 5 4 0

Answer 1

Hey,
$\lambda$ denotes an empty string to NFA.

Then language contains (a + b) *, that could an empty string as $\lambda$ or it could be 'a' (i-e ' $\lambda$ a') or 'b' (i-e ' $\lambda$ b') or 'aa' (i-e ' $\lambda$ a $\lambda$ a $\lambda$ ').

so as we know that ( a + b ) * can be the repetition of (a + b) in range of 0 to n.

hence

Case 1: when (a + b) * is empty we can move to state 6 by passing $\lambda$ as empty string.

case 2: when (a + b )is there it will reach to state 6 but again we have ( a + b)* as 'a' (i-e ' $\lambda$ a') or 'b' (i-e ' $\lambda$ b') or 'aa' (i-e ' $\lambda$ a $\lambda$ a $\lambda$ '). then we need to come back on state 2. so with a $\lambda$ will be back to state 2 from 6.

and similarly it could be 'a' (i-e ' $\lambda$ a') so we need $\lambda$ between state 2 to 4 as state 3.

so we can see that to control effect of '*' we need loops and empty string $\lambda$ to construct our NFA. So This is known as NFA with $\lambda$ transition and denoted as (NFA- $\lambda$ ).

Hope I could have explain you, why and where to use $\lambda$ in NFA.

Thanks.