You are given 2 NFAs N = (Q, E, 61, 910, F1) and N = (Q2,...

 

Transcribed Image Text:

You are given 2 NFAs N₁ = (Q₁, E, 61, 910, F1) and N₂ = (Q2, E, 62, 920, F2). Con- struct an NFA N = (Q, E, 6, qo, F) recognizing L(N₁) L(N₂). One solution would be to find DFAs equivalent to N₁ and N₂, followed by a known construction for a DFA recognizing the intersection. If |Q₁ = k₁ and Q2| = k2 then such a DFA would have up to 2k1+k2 states. We want to be much more efficient. (a) Find a solution N with much fewer states. (b) How many states has your NFA N? You are given 2 NFAs N₁ = (Q₁, E, 61, 910, F1) and N₂ = (Q2, E, 62, 920, F2). Con- struct an NFA N = (Q, E, 6, qo, F) recognizing L(N₁) L(N₂). One solution would be to find DFAs equivalent to N₁ and N₂, followed by a known construction for a DFA recognizing the intersection. If |Q₁ = k₁ and Q2| = k2 then such a DFA would have up to 2k1+k2 states. We want to be much more efficient. (a) Find a solution N with much fewer states. (b) How many states has your NFA N?

Answer rating: 100% (QA)

a A solution N with much fewer states can be constructed by combining the two NFAs into one NFA The ... View the full answer