How to use cellular automata?

Deterministic finite automata: intersection and union. How do I use product construction?

• Consider the following two deterministic finite automata. ----a b 1 | 1 2 <--- Start state 2 | 2 1 <--- Final State ---a b 1| 2 3 <--- Start state 2| 3 1 3| 1 2 <--- Final state Use the product construction to produce deterministic automata accepting (a) the intersection and (b) the union of the two sets accepted by these automata. I'm struggling with the difference between product construction and subset construction, and I'm simply not sure how to go about solving this one, any help would be appreciated!  Thank you!

• Answer:

  The two DFAs you describe can be represented pictorially as follows The blue DFA is the first machine you described and the red DFA is the second. To take the product of these machines you can quite literally cross the states with each other to get a new state for every previous pair of states. The start state is the state that corresponds to the original two start states, in this case, state (1, 1). The transitions in this product construction are made by following two edges for every character, one red edge and one blue edge. You can verify for yourself that it doesn't matter which edge you take first. The accept states in the intersection will be precisely those states that correspond to an accept state in both of the original machines. In this case, only state (3, 2). The accept states in the union will be precisely those states that correspond to an accept state in at least one of the original machines. In this case, states (3, 1), (1, 2), (2, 2), and (3, 2). Normally DFAs aren't drawn in a way that requires you to go through two states on each transition. You can collapse each of those transitions to the real transition to get the following DFA. The subset construction (or powerset construction) doesn't make for as nice a picture; it's a lot harder to draw an exponential number of states. The basic difference between the product construction and the powerset construction is that each state in the product construction represents a pair of states in the original machines, whereas each state in the powerset construction represents a subset of the states in the original machine. The powerset construction is typically used to model an NFA as a DFA, using each state in the DFA to represent the set of states you could be in in the NFA. The product construction is typically used to model running two DFAs in parallel.