automat deteministyczny Patryk: Narysować diagram automatu deterministycznego skończenie stanowego nad alfabetem {0,1}, który akceptuje wszystkie słowa, które na trzeciej pozycji od końca mają jedynkę Cześć, mam taki diagram link poniżej: https://drive.google.com/file/d/1GC962ehYyS4_VkWbVhFvZyyyUhAxJUmt/view?usp=sharing tylko nie wiem co z kolejnymi symbolami jak się uzyska stan końcowy czy powinienem to zostawić tak jak na rysunku 1, czy powinienem rozpatrzyć w jakiś sposób śmietnik jak na rysunku 2. Prośba o pomoc. Pozdrawiam

Pytający: Ale jeśli już masz jedynkę na trzeciej pozycji od końca (w danym momencie "sprawdzania"), to po kolejnym symbolu musisz wiedzieć, czy wciąż masz tam jedynkę (czyli czy poprzednio była jedynka na drugiej pozycji od końca). Znaczy stan "powinien pamiętać" do trzech ostatnich symboli. Po prostu zrób stany dla: • "ostatnie trzy pozycje to 111" • "ostatnie trzy pozycje to 101" • "ostatnie trzy pozycje to 110" • "ostatnie dwie pozycje to 11 i nie jest to żaden z ww. stanów" • "ostatnie dwie pozycje to 10 i nie jest to żaden z ww. stanów" • "ostatnia pozycja to 1 i nie jest to żaden z ww. stanów" • stan początkowy i zrób odpowiednie przejścia. Każdy z pierwszych trzech wymienionych wyżej stanów to stany akceptujące.

Patryk: @Pytający nie bardzo umiem to przelać na diagram jakaś wskazówka ?

Patryk: https://drive.google.com/file/d/1gDVlc245xHYCqwCj3Fq68Sm62Ph4pDHH/view?usp=sharing mam takie coś ale jakby nie patrzeć to jest 1 do 1 jak ten diagram 1 który wrzuciłem bez śmietnika, pytanie właśnie jak mam sprawdzić czy ta 1 jest aby na pewno na 3 pozycji od końca.

Patryk: mam właśnie kilka innych automatów, które umiem rozpisać ale mam problem ze stwierdzeniem, że dany ciąg lub symbol na pewno będzie na przed ostatniej pozycji czy ostatniej itd, nie wiem co zrobić w danym momencie czy kolejne symbole wyrzucać do śmietnika lub zrobić co innego. Prośba o pomoc.

Pytający: W poprzednim poście zapomniałem jeszcze o stanie dla: • "ostatnie trzy pozycje to 100". Po pierwsze nazywałbym te stany jakoś sensownie/intuicyjnie, prościej będzie robić przejścia (przykładowo "q5" nic mi nie mówi). I nie zgaduj, czy jakieś śmietniki są Ci potrzebne jak w innych wcześniej spotkanych automatach, a zwyczajnie zastanów się nad tym automatem. Jak już wyżej wspomniałem, oczywistym (chyba) jest, że stan musi pamiętać do trzech ostatnich symboli. Wszystkie możliwości "trzech ostatnich symboli", które muszą odpowiadać jakimś tam stanom to: −−− // brak symbolu, jeszcze nic nie było −−0 −−1 −00 −01 −10 −11 000 001 010 011 100 101 110 111 Kolejny wniosek/obserwacja: wiodące zera nic nie zmieniają, nie trzeba o nich pamiętać. Musimy jedynie "mieć w pamięci" jedynki na poprzednich trzech miejscach (znaczy na których są pozycjach). Czyli tak naprawdę mamy stany odpowiadające możliwościom (ciągle interesują nas maksymalnie trzy ostatnie symbole): // "x" niżej oznacza "nie−jedynkę") • xxx // −−−, −−0, −00, 000 • xx1 // −−1, −01, 001 • x10 // −10, 010 • x11 // −11, 011 • 100 • 101 • 110 • 111 Na początku oczywiście mamy stan xxx, bo jeszcze nie było żadnego symbolu. Pozostaje teraz zrobić odpowiednie przejścia, czyli dla każdego z ww. 8 stanów patrzysz ma jaki stan przechodzi odpowiednio dla kolejnego symbolu 0 i 1. Przykładowo: • xxx symbol 0, wtedy mamy xxx0, czyli nowy stan to xxx symbol 1, wtedy mamy xxx1, czyli nowy stan to xx1 • xx1 symbol 0, wtedy mamy xx10, czyli nowy stan to x10 symbol 1, wtedy mamy xx11, czyli nowy stan to x11 • 101 symbol 0, wtedy mamy 1010, czyli nowy stan to x10 symbol 1, wtedy mamy 1011, czyli nowy stan to x11 itd. Analogiczne automaty odpowiednio dla: • jedynka na pierwszej pozycji od końca: https://i.ibb.co/wgq0T8N/jedynka1-Od-Ko-ca.png • jedynka na drugiej pozycji od końca: https://i.ibb.co/XDv90qZ/jedynka2-Od-Ko-ca.png

Patryk: Dzięki za poświęcony czas w dniu jutrzejszym spróbuje narysować taki automat i prześlę do weryfikacji czy jest ostatecznie ok. Pozdrawiam!

Pytający: Ok, zweryfikuję. Dla otuchy masz jeszcze dla czwartej pozycji od końca: https://i.ibb.co/86rgbwt/jedynka4-Od-Ko-ca.png (dla trzeciej jest dwa razy mniej straszny)

Patryk: tak jak rozpisałeś to w końcu zrozumiałem myślę, że jest ok https://drive.google.com/file/d/1vdkCb3ps2ko__c0OycTKe1x1cRwZ71ZH/view?usp=sharing

Pytający: Ano wygląda ok. https://i.ibb.co/GtRvN9P/jedynka3-Od-Ko-ca.png