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.

Moidore

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 .

Sheilasheilah

would you also explain what's the science behind this? what's the regex? – Roentgenogram

Answer 2

It's done using the product of two automata.

Supertonic

I'm still stuck. Can anyone explain this with words? – Moidore

I built the two automata that I can in jflap... how can I combine them into one? – Moidore

Answer 3

The Language L where a are at-least two and b are odd is an regular language. Its DFA is as below:

In this DFA I have combined two DFSs conceptually!

DFA-1 = for odd number of `b`'s (placed vertically three times in diagram)
DFA-2 = for >=  two a           (placed Horizontally two times in diagram)

_{The DFA is too symptomatic and simple so I believe no need in word that how to combine both DFAs}

To draw this DFA you are always keep track how many bs has been come either even or odd. States 0, 2 and 4 means even number of b has been come. So you can divide this DFA in two parts vertically where bottom states at even bs and upper states at odd.

Also String is accepted if odd b hence final state should be in one of state in upper part.

not only number of bs is condition but a should be atleast 2. So you can divide this DFA horizontally in three parts where number of as are 0 at state-0 and 1, as are one at state-2 and 3 and as are 2 at state-4 and 5. After first two as any number of as are allow in string so there is self loop on state q4 and q5.

_{number of state required is six because, 2 state for odd even b and a s hould be atleast 2 so 3 states a=0, a=1, a=2, hence 2*3 = 6}

Cero