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

[Megjegyzés]Megjegyzés

Thompson algoritmusát igen sok módon írják le, s így bár ekvivalens, de eltérő méretű nemdeterminisztikus automatákat kapunk. Például a JFLAP algoritmusa a következő megoldást generálja az (ab+a)* reguláris kifejezés esetén:

JFLAP által generált nemdeterminisztikus automata 12 állapottal

Az általunk követett algoritmus ennél kicsit takarékosabb, ezért is javasoljuk ezt a módszert.

Mi módszerünkkel készített automata 9 állapottal

Először lássuk, hogy hogyan kell elkészíteni az (ab+a)* reguláris kifejezést felismerő nemdeterminisztikus automatát! (www.inf.unideb.hu/~aszalos/diak/fordito/re.html)

  1. Készítsen el egy az ab*+a*b reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  2. Készítsen el egy az ab*+bc*+ca* reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  3. Készítsen el egy az a(a*+b*)b reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  4. Készítsen el egy az (a+b)*(b+a)* reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  5. Készítsen el egy az (a*ba*b)* reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  6. Készítsen el egy a b*ab*ab* reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  7. Készítsen el egy az ((a+b)(b+a))* reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  8. Készítsen el egy az a*b*c reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  9. Készítsen el egy az ((a*+b)*c)* reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  10. Készítsen el egy az ab*a+a*ba* reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  11. Készítsen el egy az (a+bb)* reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  12. Készítsen el egy az a*((b+c)a*(b+c)a*)* reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  13. Készítsen el egy az (a+b+c)(a+c)(a+b+c)* reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  14. Készítsen el egy az (a+b)(a+b)b(a+b)* reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  15. Készítsen el egy a b*ab*a(a+b)* reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  16. Készítsen el egy a b*(a+λ)b*(a+λ)b* reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  17. Készítsen el egy a [p(kp)*](d[p(kp)*])* reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás

  18. Készítsen el egy az (a(b(cb)*(c+λ)+c(bc)*(b+λ)))*(a+λ)+a reguláris kifejezést felismerő nemdeterminisztikus automatát! Megoldás