Prove by induction on all positive integer k that if m is any ordinary nfa with k states, and m has fewer than k - 1 transitions, then there exists a state of m that is not reachable.
Let N be the λ-NFA: "L" for "λ"
b
>(1) -----> ((2))
| ^. |
b| | L. | a
V |. V
(3) <------ (4)
L
Prove by induction for all natural number I that the string b(ab)^i is in the language L(N)
The graph did not come out but it is a square with b from >(1) -> ((2)) and >(1) -> (3) and L from (4) -> (3) and (3) -> >(1) and a from ((2)) -> (4)
To prove that the string b(ab)^i is in the language L(N), we can use mathematical induction.
First, let's define the base case for i=0. In this case, the string is simply "b". We need to show that this string is accepted by the NFA, N.
By looking at the diagram of N, we see that there is a transition from state 1 to state 2 with input symbol "b". This means that if the NFA starts in state 1 and receives the input symbol "b", it can transition to state 2. From state 2, there are no outgoing transitions, so if the NFA reaches state 2, it can accept the string.
Now, let's assume that for some natural number i=k, the string b(ab)^k is accepted by N. We want to prove that for i=k+1, the string b(ab)^(k+1) is also accepted by N.
For i=k+1, the string can be written as b(ab)^k(ab). We can split this string into two parts, b(ab)^k and ab. The first part, b(ab)^k, is already proven to be accepted by the NFA according to our assumption. Now, we need to consider the second part, ab.
By looking at the diagram of N, we see that there is a transition from state 2 to state 3 with input symbol "a". This means that if the NFA is in state 2 and receives the input symbol "a", it can transition to state 3. From state 3, there is a lambda (λ) transition to state 4. Finally, from state 4, there is a transition back to state 3 with input symbol "b". This means that if the NFA is in state 4 and receives the input symbol "b", it can transition back to state 3.
Combining these two parts, we can conclude that if the NFA starts in state 1 and receives the input string b(ab)^k(ab), it can transition from state 1 to state 2 (with input symbol "b"), then to state 3 (with input symbol "a"), then to state 4 (via the lambda transition), and finally back to state 3 (with input symbol "b"). Since state 3 is an accepting state, the NFA can accept the string b(ab)^(k+1).
Therefore, by using mathematical induction, we have proven that for all natural numbers i, the string b(ab)^i is accepted by the NFA N.