Combining deterministic finite automata

Question

I'm really new to this stuff so I apologize for the noobishness here.

construct a Deterministic Finite Automaton DFA recognizing the following language:

L= { w : w has at least two a's and an odd number of b's}. 

The automate for each part of this (at least 2 a's, odd # of b's) are easy to make separately... Can anyone please explain a systematic way to combine them into one? Thanks.

Answer 1

You can use following simple steps to construct combined DFA.

Let Σ = {a₁ , a₂ , ...,a_k }.
1st step: Design DFA for both languages and name their state Q₀, Q₁, ...

2nd step : Rename every state in both DFA uniquely i.e. rename all states in DFA as Q₀, Q₁, Q₂, Q₃ , ... assuming you have started with subscript 0; that means none of the state would have same name.

3rd Step: Construct transition table(δ) by using following steps

   3a. Start state of the combined DFA:
      Take start state of both DFAs(DFA1 and DFA2) and name them as Q_{[ i , j ]} where i and j are the subscript of start state of DFA1 and DFA2 respectively; i.e. Q_i is start state of 1st DFA and Q_j is start state of 2nd DFA and mark Q_{[i , j]} as start state of combined DFA.

   3b. Map state of both DFAs as
           if δ(Q_i,a_k) = Q_p1 and δ(Q_j,a_k) = Q_p2 , where Q_p1 belongs to DFA1 and Q_p2 belongs to DFA2 then  δ(Q_{[ i , j ]} , a_k) = Q_[p1,p2]

   3c. fill entire table while there is any Q_[i,j] remaining in transition table.

   3d. Final state of the combined DFA:
      For AND case final state would be all Q_{[i , j]} where Q_i and Q_j are final state of DFA1 and DFA2 respectively.
      For OR case final state would be all Q_{[i , j]} where either Q_i or Q_j is the final state of DFA1 and DFA2.

4th step: Rename all Q_{[i, j]} (uniquely) and draw DFA this will be your result.

Example:

L= {w: w has at least two a's and an odd number of b's}.

Step1:
DFA for odd number of b's .

DFA for at least 2 a's.

Step2:
Rename the stae of DFA1

Step3(a,b,c):
Constructed transition table will be as.

Step3d:
Since we have to take AND of both DFA so final state would be Q_[2,4] , since it contains final state of both DFA .
If we have to take OR of both DFA the final state would be Q_[0,4],Q_[2,3],Q_[1,4],Q_[2,4] .
Transition table would like this after adding final state .

Step4:
Rename all states Q_[i,j]
Q_[0,3] to Q₀
Q_[1,3] to Q₂
Q_[0,4] to Q₁
Q_[2,3] to Q₄
Q_[1,4] to Q₃
Q_[2,4] to Q₅
So final DFA would will look like as below .