Menu
Does anyone have a straightforward description of the algorithm for constructing the union of two given DFA's? For example, say we have two DFA's over {0,1} where
{w|w has an odd number of characters}
w has states A and B
delta | 0 | 1
----------------
A | B | B
----------------
B | A | A
{x|x has an even number of 1s}
x has states a and b
delta | 0 | 1
----------------
a | a | b
----------------
b | b | a
I have a resulting transition table showing the union as:
delta | 0 | 1
----------------
Aa | Ba | Bb
----------------
Ab | Bb | Ba
----------------
Ba | Aa | Ab
----------------
Bb | Ab | Aa
I have a pictorial solution in my lecture notes, but would like to see how others would describe it. From this, I can see that we essentially "multiply" these two original tables using their state values to result in a larger transition table. The DFA can be thus drawn from the resultant table. Does this sound right and should this work for all DFA cases, or is there something I'm missing?
257
Step 1: Create a NFA from the two DFAs. Open one of the DFAs and use the Combine Two option on the Convert menu to select the other machine. Step 3: Using JFLAP, convert to a DFA by using the convert>DFA tool, and Complete and press Done.
It accepts all the string that accept 01 at end. It accepts all the string that accept with even number of 1's. State Transition Diagram of L1 ∩ L2 : Intersection of L1 and L2 can be explained by language that a string over {0, 1} accept such that it ends with 01 and has even number of 1's.
The complement of a DFA can be obtained by making the non-final states as final states and vice-versa. The language accepted by the complemented DFA L2 is the complement of the language L1.
Given two strings w1 and w2, we define the concatenation of w1 and w2 to be the string as w1w2. Examples. If w1 = pq and w2 = r, then w1w2 = pqr.
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. For example if you are in state Ab, and you get a 0 on input, the first DFA would go to state B and the second one to state b, so the union DFA's next state for this input will be Bb.
This method works in every case when you need to make a union of two or more DFAs. The resulting DFA may not be optimal, but later you can minimize it with any algorithm you like.
73
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
