You are given 2 DFAs M = (Q1, 2, 81, 910, F) and M2 = (Q2,...

Transcribed Image Text:

You are given 2 DFAs M = (Q1, 2, 81, 910, F) and M2 = (Q2, 2, 82, 920, F2). We want to construct a DFA M = (Q, , 8, 90, F) recognizing the concatenation (Q,, L(M1) L(M2). One solution would be as follows. Connect each accept state of M to the start state of M2 by an e-move, and make the accept states of M non-accepting. This is an NFA N = (Q', , 8', qo, F') accepting L(M) L(M2). Now transform this NFA into an equivalent DFA. If |Q| = k and |Q2| = k2, then 2k1+k2 would be an obvious upper bound on the number of states of such a DFA M. We can actually do much better, because many states of the DFA M obtained with the full subset construction are not reachable from the start state. (a) Identify a large subset of the power set of Q' that are states of M not reachable from the start state. (b) Give a good upper bound on the number of reachable states of the DFA M? You are given 2 DFAs M = (Q1, 2, 81, 910, F) and M2 = (Q2, 2, 82, 920, F2). We want to construct a DFA M = (Q, , 8, 90, F) recognizing the concatenation (Q,, L(M1) L(M2). One solution would be as follows. Connect each accept state of M to the start state of M2 by an e-move, and make the accept states of M non-accepting. This is an NFA N = (Q', , 8', qo, F') accepting L(M) L(M2). Now transform this NFA into an equivalent DFA. If |Q| = k and |Q2| = k2, then 2k1+k2 would be an obvious upper bound on the number of states of such a DFA M. We can actually do much better, because many states of the DFA M obtained with the full subset construction are not reachable from the start state. (a) Identify a large subset of the power set of Q' that are states of M not reachable from the start state. (b) Give a good upper bound on the number of reachable states of the DFA M?

Answer rating: 100% (QA)

a A large subset of the power set of Q that are states of M not reachable from the start s... View the full answer