1.3. Nemdeterminisztikus automaták determinizálása

[Megjegyzés]Megjegyzés

A JFLAP program ismeri a determinizálás algoritmusát, gombnyomásra újabb és újabb állapotait készíti el a determinisztikus automatának. Ha a korábbi automatánkból indulunk ki, a JFLAP futásának végeredménye a következő lesz:

JFLAP által generált determinisztikus automata

Érzésünk szerint ebben az esetben, a megoldások során kényelmesebben használható a táblázat, melyet a nemdeterminisztikus automata alapján készítünk el, és nincs szükség arra, hogy rajzos formában ábrázoljuk. A megoldásainkat is táblázatként adjuk meg. Persze előnyös a gráfok használata, segít megérteni az automaták működését.

Az alábbi feladatokban zöld színnel jelöltük a kezdőállapotot és pirossal a végállapotot. A λ-átmeneteknél nem írtuk ki a λ jelet a nyilakra.

Nézzük először, hogy az előző szakasz bemutató példájában megoldásként kapott nemdeterminisztikus automatát hogyan lehet determinizálni! (www.inf.unideb.hu/~aszalos/diak/fordito/re2fsa.html)

  1. Determinizálja az alábbi automatát! Megoldás

    ab*+a*b reguláris kifejezés automatája

  2. Determinizálja az alábbi automatát! Megoldás

    ab*+bc*+ca* reguláris kifejezés automatája

  3. Determinizálja az alábbi automatát! Megoldás

    a(a*+b*)b reguláris kifejezés automatája

  4. Determinizálja az alábbi automatát! Megoldás

    (a+b)*(b+a)* reguláris kifejezés automatája

  5. Determinizálja az alábbi automatát! Megoldás

    (a*ba*b)* reguláris kifejezés automatája

  6. Determinizálja az alábbi automatát! Megoldás

    b*ab*ab* reguláris kifejezés automatája

  7. Determinizálja az alábbi automatát! Megoldás

    ((a+b)(b+a))* reguláris kifejezés automatája

  8. Determinizálja az alábbi automatát! Megoldás

    a*b*c reguláris kifejezés automatája

  9. Determinizálja az alábbi automatát! Megoldás

    ((a*+b)*c)* reguláris kifejezés automatája

  10. Determinizálja az alábbi automatát! Megoldás

    ab*a+a*ba* reguláris kifejezés automatája

  11. Determinizálja az alábbi automatát! Megoldás

    (a+bb)* reguláris kifejezés automatája

  12. Determinizálja az alábbi automatát! Megoldás

    a*((b+c)a*(b+c)a*)* reguláris kifejezés automatája

  13. Determinizálja az alábbi automatát! Megoldás

    (a+b+c)(a+c)(a+b+c)* reguláris kifejezés automatája

  14. Determinizálja az alábbi automatát! Megoldás

    (a+b)(a+b)b(a+b)* reguláris kifejezés automatája

  15. Determinizálja az alábbi automatát! Megoldás

    b*ab*a(a+b)* reguláris kifejezés automatája

  16. Determinizálja az alábbi automatát! Megoldás

    b*(a+λ)b*(a+λ)b* reguláris kifejezés automatája

  17. Determinizálja az alábbi automatát! Megoldás

    [p(kp)*](d[p(kp)*])* reguláris kifejezés automatája

  18. Determinizálja az alábbi automatát! Megoldás

    (a(b(cb)*(c+λ)+c(bc)*(b+λ)))*(a+λ)+a reguláris kifejezés automatája