Proofs 4 points 1 4 points Suppose L1 and L2 are languages t

Proofs (4 points)

(1) (4 points) Suppose L1 and L2 are languages that can be recognized by NFAs M1 and M2, respectively. Show that the language L3 = {w|w L1 or w L2} can be recognized by an NFA.

Hint: provide an algorithm that constructs an appropriate NFA M3 from M1 and M2.

Solution

First we will construct two NFA\'s K1 and K2.

K1 is for wL1

K1 has same states and transition table as M1 but we make all the non-final states in M1 as final states and all the final states as non-final states.

K2 is for wL2

K2 has same states and transition table as M2 but we make all the non-final states in M2 as final states and all the final states as non-final states.

Now M3 will be the union of K1 and K2.

Now we create a new state and make it the start state of M3 and from this state we add two transitions with to the two start states of M1 and M2. So now the combined NFA will be M3.