Geek asks and answers

Combining deterministic finite state machines

I am really new to this, so I apologize for the noobishness here.

Build a Deterministic Finite AutomatonDFA that recognizes the following language:

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

Automation for each part of this is (at least 2 a's, odd # of b's)easy to do separately ... Can someone explain a systematic way to combine them into one? Thank.

+5
source share
3 answers

You can use the following simple steps to create a combined DFA.

Let & Sigma; = {a 1, a 2, ..., a k} .
1st step: Develop DFA for both languages ​​and name their status Q 0, Q 1, ...

: DFA , .. DFA Q 0, Q 1, Q 2, Q 3,... , 0; , .

3- : (& delta;),

  3a. DFA:
              DFA (DFA1 DFA2) Q [i, j], j - DFA1 DFA2 ; .. Q i 1- DFA, Q j 2- DFA Q [i, j] DFA.

  3b. DFA
                  < & delta; (Q i p1 & delta; (Q j, a k) = Q p2, Q p1 DFA1 Q p2 DFA2, & delta; (Q [i, j], a k) = Q < > [p1, p2] >

    3. , Q [i, j].

    3d. DFA:
              AND Q [i, j - DFA1 DFA2 .
nbsp;         > j - DFA1 DFA2.

4- : Q [i, j] () DFA, .

:

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

1:
DFA b.
hgk9i.png
DFA 2 .
cg3i7.png

2:
DFA1
enter image description here

3 (a, b, c):
.
table

Step3d:
DFA, Q [2,4], DFA.
DFA, Q [0,4], Q [2,3], Q [ 1,4], Q [2,4].
.

final table

4:
Q [i, j]
Q [0,3] Q 0
Q [1,3] Q 2
Q [0,4] Q 1
Q [2,3] Q 4
Q [1,4] Q 3
Q [2,4] Q 5
, DFA . table

+10

product .

+1

L, a - , b - , . DFA :
a_and_odd_b

DFA DFS !

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

DFA , , DFA

DFA, , b . States 0, 2 and 4 , b. , DFA , b .

String , b, .

b , a 2. , DFA , a 0 state-0 and 1, a state-2 and 3 a 2 state-4 and 5. a a , q4 q5 self loop.

, 2 b 2, 3 a = 0, a = 1, a = 2, 2 * 3 = 6 >

+1

More articles:


All Articles