Zadania z Automatów

Witam,

Podczas rozwiązywania wielu zadań spośród: Determinizacji, Twierdzenie Kleenego oraz maszyny Turinga, trafiłem na zadania którym po prostu nie umiem rozwiązać, wydaje mi się że są ok, ale rzeczywistość jest zupełnie inna. Czy ktoś z tutaj z obecnych mógłby wskazać mi błędy? Będę mega wdzięczny!

Zadanie 1:

Dany automat przerobić na deterministyczny:

po mojej przeróbce:

Zadanie 2:

Twierdzenie kleenego

Zadanie 3:

Maszyna Turinga, stworzona na podstawie E={a,b}* : podsłowem jest aa.

Pozdrawiam

(poprawione, dzieki)

Albo ja nie rozumiem treści, albo te twoje "rozwiązania" nijak sie mają do zadań.

1. Automat który dostałeś akceptuje wszystko postaci (a|b)* więc wystarczyłby tam jeden stan akceptujący S i przejscie przez a oraz przez b wracają do niego samego. Ty tam jakieś cuda na kiju namalowałeś. Jakieś dwa stany początkowe S, jakieś przejście przez b które trafia do jakiegoś stanu który nie akceptuje i nie da się z niego wyjść. Co sie tam dzieje? :D
2. A może podasz łaskawie TREŚĆ zadania? o_O
3. jw, nie wiadomo co ty w ogóle miałeś tu zrobić, ale ta MT to się w ogóle nie trzyma kupy :D Ona akceptuje tylko baab, o to chodziło?

W zadaniu 2 jest automat i poniżej zastosowany Kleene dla niego :p Tam nie ma treści.

Ale które twierdzenie? Że każdy język regularny jest akceptowany przez automat skończony? Czyli zadaniem jest podaj wyrażenie regularne akceptujące ten sam język co podany automat!
Te twoje zapiski znowu nie bardzo mają sens. Masz tam tak:

• akceptuj przy pustym stanie
• akceptuj po dodaniu a
• po dodaniu a mozesz dodać ile chcesz b
• akceptuj po dodaniu kolejnego a ale jak chcesz wrócić do b to musisz znów dodać a
  Więc mamy coś w stylu: a?|(ab*)+ a to daje dalej (ab*)*

Shalom napisał(a):

Albo ja nie rozumiem treści, albo te twoje "rozwiązania" nijak sie mają do zadań.

1. Automat który dostałeś akceptuje wszystko postaci (a|b)* więc wystarczyłby tam jeden stan akceptujący S i przejscie przez a oraz przez b wracają do niego samego. Ty tam jakieś cuda na kiju namalowałeś. Jakieś dwa stany początkowe S, jakieś przejście przez b które trafia do jakiegoś stanu który nie akceptuje i nie da się z niego wyjść. Co sie tam dzieje? :D
2. A może podasz łaskawie TREŚĆ zadania? o_O
3. jw, nie wiadomo co ty w ogóle miałeś tu zrobić, ale ta MT to się w ogóle nie trzyma kupy :D Ona akceptuje tylko baab, o to chodziło?

Automat skończony który napisałeś niestety nie będzie poprawny, bo wg. Ciebie mamy stan S : S - > a > S oraz S: S - > b - > S, a na pierwszym zdjęciu wyraźnie widać, że automat musi mieć a + (czyli przynajmniej jedno a MUSI się pojawić). Dzisiaj posiedziałem na tym trochę i aby osiągnąć determinizm, należy zrobić:

ze stanu S wychodzi b do stanu pustego, czyli tzw. "dead state"

Liczyłem na pomoc od osób, które mają wiedzę w danym temacie (po pierwszej wypowiedzi wyraziłeś arogancję nie wiedząc nawet na czym polega stosowanie twierdzenia Kleenego i są tam po kolei wstawione operacje za pomocą rysunku graficznego)

Temat można zamknąć...