323 views

1 Answer

0 votes
0 votes

To quote from Sipser,

"To keep track of both simulation with finite memory you need to remember the state that each machine would be in if it had read up to this point in the input. Therefore you need to remember a pair of states...."

For example, if you have a DFA with two states A and B, and another DFA with states C and D.  Assume that the language is $\{0,1\}$

Now on 0, the first DFA might go to A and the second DFA might go to C. We have to keep track of both these movements, hence we will multiply them and their union goes to AC.

Quoting from another SO answer:

"The key to understand is that you have to run the two DFAs simultanously, or in general you have to maintain the states of both DFAs in the union DFA.

That's why you have to create the new states for the union DFA as a direct multiplication of the original states. This way you have a state for every combination of the states in original DFAs."

The transition rules for the new DFA can be directly calculated then by taking unions in a similar way.

This won't be the optimal DFA, but it can always be minimised later.

Refer to https://stackoverflow.com/questions/4449950/how-do-you-construct-the-union-of-two-dfas for a concrete example.

Related questions

3 votes
3 votes
2 answers
3
0 votes
0 votes
1 answer
4
himgta asked Jul 24, 2018
1,190 views
Find the no. of DFA’s that can be constructed over the alphabet Σ with 5 symbols, and with 10 states?