1.4. Determinisztikus automaták minimalizálása

[Megjegyzés]Megjegyzés

A JFLAP programban lépésről lépésre követhetjük az állapothalmazok felbontását az általunk követett táblázatos módszer helyett gráffal ábrázolva. A program ezután elvárja az állapothalmazok közti átmenetek megadását. A korábbi bemutató feladatunk esetén a következő ábrát kapjuk:

Determinisztikus automatánk minimalizáltja

Lássuk először, hogy a korábbi bemutató példánk determinisztikus automatája hogyan is minimalizálható! (www.inf.unideb.hu/~aszalos/diak/fordito/fsamin.html)

  1. Minimalizálja az alábbi automatát!

     ab
    123
    *245
    *366
    443
    *567
    666
    *767

    Megoldás

  2. Minimalizálja az alábbi automatát!

     abc
    1234
    *2565
    *3557
    *4855
    5555
    *6565
    *7557
    *8855

    Megoldás

  3. Minimalizálja az alábbi automatát!

     ab
    123
    245
    333
    446
    *535
    *633

    Megoldás

  4. Minimalizálja az alábbi automatát!

     ab
    *123
    *223
    *323

    Megoldás

  5. Minimalizálja az alábbi automatát!

     ab
    *123
    223
    345
    445
    *523

    Megoldás

  6. Minimalizálja az alábbi automatát!

     ab
    123
    245
    323
    *467
    545
    666
    *767

    Megoldás

  7. Minimalizálja az alábbi automatát!

     ab
    *123
    245
    345
    *423
    *523

    Megoldás

  8. Minimalizálja az alábbi automatát!

     abc
    1234
    2234
    3534
    *4555
    5555

    Megoldás

  9. Minimalizálja az alábbi automatát!

     abc
    *1234
    2234
    3234
    *4234

    Megoldás

  10. Minimalizálja az alábbi automatát!

     ab
    123
    245
    *367
    *483
    *5910
    *667
    777
    883
    *967
    101110
    *1177

    Megoldás

  11. Minimalizálja az alábbi automatát!

     ab
    *123
    *223
    345
    444
    *523

    Megoldás

  12. Minimalizálja az alábbi automatát!

     abc
    *1234
    *2234
    3567
    4567
    5567
    *6834
    *7834
    *8834

    Megoldás

  13. Minimalizálja az alábbi automatát!

     abc
    1234
    2567
    3567
    4567
    *58910
    6666
    *78910
    *88910
    *98910
    *108910

    Megoldás

  14. Minimalizálja az alábbi automatát!

     ab
    123
    245
    345
    467
    567
    666
    *789
    *889
    *989

    Megoldás

  15. Minimalizálja az alábbi automatát!

     ab
    123
    245
    323
    *467
    545
    *667
    *767

    Megoldás

  16. Minimalizálja az alábbi automatát!

     ab
    *123
    *245
    *323
    *467
    *545
    666
    *767

    Megoldás

  17. Minimalizálja az alábbi automatát!

     []dkp
    123333
    233334
    333333
    435363
    *533733
    633338
    793333
    835363
    9333310
    103113123
    *1133733
    12333313
    133113123

    Megoldás

  18. Minimalizálja az alábbi automatát!

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

    Megoldás