2.2. Reguláris kifejezéseket felismerő nemdeterminisztikus automaták

[Megjegyzés]Megjegyzés

Ebben és azt ezt követő fejezetekben Thompson algoritmusát [Thompson68] alkalmazzuk kisebb lépésekben ugyanarra a 18 feladatra.

A feladatok megoldásait jelentő nemdeterminisztikus automatákat a következőképpen adjuk meg: zöld színnel jelöljük a kiinduló állapotot, és pirossal az egyedüli végállapotot. A λ-átmenetnél a nyilat nem címkézzük az egyszerűség kedvéért.

  1. ab*+a*b

    ab*+a*b nemdeterminisztikus automatája

  2. ab*+bc*+ca*

    ab*+bc*+ca* nemdeterminisztikus automatája

  3. a(a*+b*)b

    a(a*+b*)b nemdeterminisztikus automatája

  4. (a+b)*+(b+a)*

    (a+b)*+(b+a)* nemdeterminisztikus automatája

  5. (a*ba*b)*

    (a*ba*b)* nemdeterminisztikus automatája

  6. b*ab*ab*

    b*ab*ab* nemdeterminisztikus automatája

  7. ((a+b)(b+a))*

    ((a+b)(b+a))* nemdeterminisztikus automatája

  8. a*b*c

    a*b*c nemdeterminisztikus automatája

  9. ((a*+b)*c)*

    ((a*+b)*c)* nemdeterminisztikus automatája

  10. ab*a+a*ba*

    ab*a+a*ba* nemdeterminisztikus automatája

  11. (a+bb)*

    (a+bb)* nemdeterminisztikus automatája

  12. a*((b+c)a*(b+c)a*)*

    a*((b+c)a*(b+c)a*)* nemdeterminisztikus automatája

  13. (a+b+c)(a+b)(a+b+c)*

    (a+b+c)(a+b)(a+b+c)* nemdeterminisztikus automatája

  14. (a+b)(a+b)b(a+b)*

    (a+b)(a+b)b(a+b)* nemdeterminisztikus automatája

  15. b*ab*a(a+b)*

    b*ab*a(a+b)* nemdeterminisztikus automatája

  16. b*(a+λ)b*(a+λ)b*

    b*(a+λ)b*(a+λ)b* nemdeterminisztikus automatája

  17. [p(kp)*](d[p(kp)*])*

    [p(kp)*](d[p(kp)*])* nemdeterminisztikus automatája

  18. (a(b(cb)*(c+λ)+c(bc)*(b+λ)))*(a+λ)+a

    (a(b(cb)*(c+λ)+c(bc)*(b+λ)))*(a+λ)+a nemdeterminisztikus automatája