Διακριτά Μαθηματικά - Μηχανές πεπερασμένων καταστάσεων

[clevercitizen]

Παιδιά θέλω τη βοήθειά σας.

Μια μηχανή πεπερασμένων καταστάσεων έχει αλφάβητο εισόδου / εξόδου {0,1}. Δεδομένης της παρακάτω ακολουθίας προσδιορίστε τη μηχανή

ακολουθία εισόδου: 01111100111

ακολουθία εξόδου: 000011100001

 

Πρέπει να κάνω πινακάκι με Κατασταση/Εισοδο/Εξοδο και έπειτα το γράφημα της μηχανής?

Εαν μου δώσουν το πινακάκι μπορώ να κάνω το γράφημα, μπορώ να βρώ ακόμη και την ακολουθία εξόδου εφόσον μου δίνεται η ακολουθία εισόδου/πινακάκι.

Στο βιβλίο που έχω (C.L.LIU Elements Of Discrete Mathematics) έχει αντίστοιχες ασκήσεις αλλά δεν έχει τις απαντήσεις :mad:

Οποιαδήποτε βοήθεια ευπρόσδεκτη

[C6WGMN]

Νομίζω σου ξέφυγε ένα μηδενικό στην έξοδο. 111 = 001, 1 μετά από αυτά = 1, αλλιώς 0.

[clevercitizen]

Οχι, μια μηχανή πεπερασμένων καταστάσεων παράγει ένα σύμβολο εξόδου(αυτό της αρχικής κατάστασης) πριν δεχτεί το πρώτο σύμβολο εισόδου

[eirinikp]

Βασικά έχεις καταλάβει τι κάνει η μηχανή που σου δίνει αυτό το output? Από ότι φαίνεται μετατρέπει σε κάθε ακολουθία από διαδοχικούς άσσους, τους 2 αριστερότερους σε μηδενικά (υποθέτω...).

Εσύ τώρα θες κάτι του στυλ Κατάσταση + Σύμβολο = Κατάσταση + Σύμβολο + Κίνηση? (πρόγραμμα μηχανής Turing) Ή μήπως θες ένα αυτόματο πεπερασμένων καταστάσεων (DFA) με συμβολάκια, κουτάκια και βελάκια?

Ή κάτι άλλο?

[dop]

Βρες την "περιγραφή" της μηχανής. Δίνει '1' όταν συναντά αλληλουχία από τέσσερα '1'. Αρκεί να έχεις μόλις 4 καταστάσεις για να κάνεις την μηχανή.

 

Ξεκίνα με μία αρχική κατάσταση και άρχισε να δίνεις τιμές για μετάβαση στην αντίστοιχη κατάσταση και συνέχισε να κάνεις το ίδιο μέχρι η μηχανή σου να σου δίνει την επιθυμητή αλληλουχία.