2.3. Nemdeterminisztikus automaták determinizálása

[Megjegyzés]Megjegyzés

Minden megoldást két formában is megadunk. Első esetben a nemdeterminisztikus automata állapotainak halmaza lesz az új automa egy-egy állapota. Az ezeket az állapotokat tartalmazó táblázatban nem jelöltük külön a kezdő és végállapotokat, csupán az átmeneteket. Kezdőállapot az, mely az A-val jelölt állapotot tartalmazza (vagyis az első), és végállapot mindaz, amely a rajzon pirossal jelölt állapotot tartalmazza.

  1. Determinisztikus automata állapothalmazokkal.

     ab
    ABGHJCDFHIJLKL
    CDFHIJLHIJDEFKL
    KL  
    HIJHIJKL
    DEFKL DEFL
       
    DEFL DEFL

    Ugyanaz az automata hagyományos jelöléssel.

     ab
    123
    *245
    *366
    443
    *567
    666
    *767
  2. Determinisztikus automata állapothalmazokkal.

     abc
    ABCHNDEGMSIJLMSOPRS
    DEGMS EFGMS 
    IJLMS  JKLMS
    OPRSPQRS  
        
    EFGMS EFGMS 
    JKLMS  JKLMS
    PQRSPQRS  

    Ugyanaz az automata hagyományos jelöléssel.

     abc
    1234
    *2565
    *3557
    *4855
    5555
    *6565
    *7557
    *8855
  3. Determinisztikus automata állapothalmazokkal.

     ab
    ABCDFGHJK 
    BCDFGHJKDEFKHIJKL
       
    DEFKDEFKL
    HIJKL HIJKL
    L  

    Ugyanaz az automata hagyományos jelöléssel.

     ab
    123
    245
    333
    446
    *535
    *633
  4. Determinisztikus automata állapothalmazokkal.

     ab
    ABCDFIJKLNQRCDEFHIKLNOPQRCDFGHIKLMNPQR
    CDEFHIKLNOPQRCDEFHIKLNOPQRCDFGHIKLMNPQR
    CDFGHIKLMNPQRCDEFHIKLNOPQRCDFGHIKLMNPQR

    Ugyanaz az automata hagyományos jelöléssel.

     ab
    *123
    *223
    *323
  5. Determinisztikus automata állapothalmazokkal.

     ab
    ABCEKCDEFGI
    CDECDEFGI
    FGIGHIBCEJK
    GHIGHIBCEJK
    BCEJKCDEFGI

    Ugyanaz az automata hagyományos jelöléssel.

     ab
    *123
    223
    345
    445
    *523
  6. Determinisztikus automata állapothalmazokkal.

     ab
    ABDEFHBCD
    EFHIJLFGH
    BCDEFHBCD
    IJL JKL
    FGHIJLFGH
       
    JKL JKL

    Ugyanaz az automata hagyományos jelöléssel.

     ab
    123
    245
    323
    *467
    545
    666
    *767
  7. Determinisztikus automata állapothalmazokkal.

     ab
    ABCEMDGHJFGHJ
    DGHJBCEKLMBCEILM
    FGHJBCEKLMBCEILM
    BCEKLMDGHJFGHJ
    BCEILMDGHJFGHJ

    Ugyanaz az automata hagyományos jelöléssel.

     ab
    *123
    245
    345
    *423
    *523
  8. Determinisztikus automata állapothalmazokkal.

     abc
    ABDEGBCDEGEFGH
    BCDEGBCDEGEFGH
    EFG EFGH
    H   
        

    Ugyanaz az automata hagyományos jelöléssel.

     abc
    1234
    2234
    3534
    *4555
    5555
  9. Determinisztikus automata állapothalmazokkal.

     abc
    ABCDEGHJKMCDEFGHJKCDEGHIJKBCDEGHJKLM
    CDEFGHJKCDEFGHJKCDEGHIJKBCDEGHJKLM
    CDEGHIJKCDEFGHJKCDEGHIJKBCDEGHJKLM
    BCDEGHJKLMCDEFGHJKCDEGHIJKBCDEGHJKLM

    Ugyanaz az automata hagyományos jelöléssel.

     abc
    *1234
    2234
    3234
    *4234
  10. Determinisztikus automata állapothalmazokkal.

     ab
    ABHIKCDFIJKLMOP
    CDFIJKGIJKPDEFLMOP
    LMOPMNOP 
    GIJKPIJKLMOP
    DEFLMOPGMNOPDEF
    MNOPMNOP 
       
    IJKIJKLMOP
    GMNOPMNOP 
    DEFGPDEF
    GP  

    Ugyanaz az automata hagyományos jelöléssel.

     ab
    123
    245
    *367
    *483
    *5910
    *667
    777
    883
    *967
    101110
    *1177
  11. Determinisztikus automata állapothalmazokkal.

     ab
    ABCEIBCDEHIF
    BCDEHIBCDEHIF
    F BCEGHI
       
    BCEGHIBCDEHIF

    Ugyanaz az automata hagyományos jelöléssel.

     ab
    *123
    *223
    345
    444
    *523
  12. Determinisztikus automata állapothalmazokkal.

     abc
    ABDEFHVBCDEFHVGJKMNPIJKMNP
    BCDEFHVBCDEFHVGJKMNPIJKMNP
    GJKMNPKLMNPEFHORSUVEFHQRSUV
    IJKMNPKLMNPEFHORSUVEFHQRSUV
    KLMNPKLMNPEFHORSUVEFHQRSUV
    EFHORSUVEFHSTUVGJKMNPIJKMNP
    EFHQRSUVEFHSTUVGJKMNPIJKMNP
    EFHSTUVEFHSTUVGJKMNPIJKMNP

    Ugyanaz az automata hagyományos jelöléssel.

     abc
    *1234
    *2234
    3567
    4567
    5567
    *6834
    *7834
    *8834
  13. Determinisztikus automata állapothalmazokkal.

     abc
    ABCEHDGJKMFGJKMIJKM
    DGJKMLOPQRTWZ NOPQRTWZ
    FGJKMLOPQRTWZ NOPQRTWZ
    IJKMLOPQRTWZ NOPQRTWZ
    LOPQRTWZPQRSTVWYZPQRTUVWYZPQRTWXYZ
        
    NOPQRTWZPQRSTVWYZPQRTUVWYZPQRTWXYZ
    PQRSTVWYZPQRSTVWYZPQRTUVWYZPQRTWXYZ
    PQRTUVWYZPQRSTVWYZPQRTUVWYZPQRTWXYZ
    PQRTWXYZPQRSTVWYZPQRTUVWYZPQRTWXYZ

    Ugyanaz az automata hagyományos jelöléssel.

     abc
    1234
    2567
    3567
    4567
    *58910
    6666
    *78910
    *88910
    *98910
    *108910
  14. Determinisztikus automata állapothalmazokkal.

     ab
    ABDCFGIEFGI
    CFGIHKJK
    EFGIHKJK
    HK LMNPS
    JK LMNPS
       
    LMNPSMNOPRSMNPQRS
    MNOPRSMNOPRSMNPQRS
    MNPQRSMNOPRSMNPQRS

    Ugyanaz az automata hagyományos jelöléssel.

     ab
    123
    245
    345
    467
    567
    666
    *789
    *889
    *989
  15. Determinisztikus automata állapothalmazokkal.

     ab
    ABDEFHBCD
    EFHIJKMPFGH
    BCDEFHBCD
    IJKMPJKLMOPJKMNOP
    FGHIJKMPFGH
    JKLMOPJKLMOPJKMNOP
    JKMNOPJKLMOPJKMNOP

    Ugyanaz az automata hagyományos jelöléssel.

     ab
    123
    245
    323
    *467
    545
    *667
    *767
  16. Determinisztikus automata állapothalmazokkal.

     ab
    ABDEGHIJLMOPQRTFIJLMNOPQRTBCDEGHIJKLMOPQRST
    FIJLMNOPQRTNQRTJKLMOPQRST
    BCDEGHIJKLMOPQRSTFIJLMNOPQRTBCDEGHIJKLMOPQRST
    NQRT RST
    JKLMOPQRSTNQRTJKLMOPQRST
       
    RST RST

    Ugyanaz az automata hagyományos jelöléssel.

     ab
    *123
    *245
    *323
    *467
    *545
    666
    *767
  17. Determinisztikus automata állapothalmazokkal.

     []dkp
    AB    
    B    CDG
          
    CDG HIR E 
    HIR  J  
    E    DFG
    JK    
    DFG HIR E 
    K    LMP
    LMP IQR N 
    IQR  J  
    N    MOP
    MOP IQR N 

    Ugyanaz az automata hagyományos jelöléssel.

     []dkp
    123333
    233334
    333333
    435363
    *533733
    633338
    793333
    835363
    9333310
    103113123
    *1133733
    12333313
    133113123
  18. Determinisztikus automata állapothalmazokkal.

     abc
    ABCbcefghjDEPdgij  
    DEPdgij CFGJKMNOabcefgjCQRUVXYZabcefgj
        
    CFGJKMNOabcefgjDEPdgj CHLOabcefgj
    CQRUVXYZabcefgjDEPdgjCSWZabcefgj 
    DEPdgj CFGJKMNOabcefgjCQRUVXYZabcefgj
    CHLOabcefgjDEPdgjCGIJKMNOabcefgj 
    CSWZabcefgjDEPdgj CRTUVXYZabcefgj
    CGIJKMNOabcefgjDEPdgj CHLOabcefgj
    CRTUVXYZabcefgjDEPdgjCSWZabcefgj 

    Ugyanaz az automata hagyományos jelöléssel.

     abc
    *1233
    *2345
    3333
    *4637
    *5683
    *6345
    *7693
    *86310
    *9637
    *10683