έστω μια δυο μέρες διαφορά..να μην είναι η εξέταση την ίδια μέρα..

αν καταλαβαίνω καλά την πρώτη απορία, δεν είναι απαραίτητο στο ΜΑΠΑ να έχεις πολλές μεταβάσεις για κάθε κατάσταση. η μη αιτιοκρατικότητα μπορεί να έγκειται στο γεγονός ότι το αυτόματο μπορεί να μπλοκάρει κάπου ή να έχει μεταβάσεις εν κενώ.

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

εχει λυσει κανενας το θεμα 2 του 2008 με την KMC??

οταν ξεκιναει η μηχανη το πρωτο R (που δεν εχει κουτακι κατω δεξια) μετακινει την κεφαλη μια θεση δεξια, τοτε ελεγχει αμα στην θεση αυτη υπαρχει κενο, αν δεν υπαρχει τοτε πηγαινει παλι μια θεση δεξια και κανει παλι το ιδιο και κινειται παλι μια θεση δεξια, οποτε τωρα βρισκεται στην εντολη R (που εχει κουτακι κατω δεξια) και σημαινει να παει στο πρωτο κενο που θα βρει απο δεξια... εκει θα γραψει το α(δηλαδη τον χαρακτηρα που βρηκε στην αρχη, οχι αναγκαστηκα α), και θα παει στην επομενη εντολη που ειναι  R (που εχει κουτακι κατω δεξια) και θα κινηθει παλι μια θεση δεξια και θα γραψει το β δηλαδη το δευτερο γραμμα που διαβασε...

παραδειγμα ταινιας:
>_dfrefgg_ η κεφαλη ειναι στο πρωτο κενο, η μηχανη θα κινηθει δεξια μια θεση και θα βρει το d (που το αποθηκευει στην μεταβλητη a), στην συνεχεια θα μετακινηθει δεξια και θα αντιγραψει στην μεταβλητη b το f, και θα παει στο πρωτο κενο απο δεξια και θα γραψει d και στο δευτερο f οποτε η ταινια μετα θα ειναι   >_dfrefggdf_

το R χωρις κουτακι δεξια σημαινει μονο μετακινηση δεξια, ενω με κουτακι, πηγαινε στο πρωτο κενο χαρακτηρα που θα βρεις...
δεν ξερω ομως αν μπορει στην w να περιεχει κενα...γιατι αν το πρωτο γραμμα ειναι κενο τοτε η μηχανη σταματαει... ολα αυτα τα βρηκα στο βιβλιο σελιδα 252 - 254

Για παραδειγμα εγω χρησιμοποιησα τους κανονες:
S->aSa | + | - | * | / | e | Sa | aS | a | SS

και ενα παραδειγμα υπολογισμου της (((α+α)*α)/α) ειναι:
S->(S) -> (SS) -> ((S)S) -> ((SS)S) -> (((S)S)S) -> (((aSa)S)S) -> (((aSa)S)SS) -> (((aSa)SS)S) -> (((aSa)SS)SS) -> (((a+a)SS)SS) -> (((a+a)*S)SS) ->(((a+a)*a)SS) ->(((a+a)*a)/S) -> (((a+a)*a)/a)

edit: και για το γ ερωτημα: D1 < D2

D1 : S->(S) -> (SS) -> ((S)S) -> ((SS)S) -> (((S)S)S) -> (((aSa)S)S) -> (((aSa)S)SS) -> (((aSa)SS)S) -> (((aSa)SS)SS) -> (((a+a)SS)SS) -> (((a+a)*S)SS) ->(((a+a)*a)SS) ->(((a+a)*a)/S) -> (((a+a)*a)/a)

D2 : S->(S) -> (SS) -> ((S)S) -> ((SS)S) -> (((S)S)S) -> (((S)S)SS) -> (((aSa)S)SS) -> (((aSa)SS)S) -> (((aSa)SS)SS) -> (((a+a)SS)SS) -> (((a+a)*S)SS) ->(((a+a)*a)SS) ->(((a+a)*a)/S) -> (((a+a)*a)/a)

Τωρα εσυ λες για το 3ο θεμα. εγω παντως οταν το δα θεωρησα κ οι πραξεις αποτελουν τερματικα.. δλδ σαν το παραδειγμα 3.13 του βιβλιου.

Έχει κανείς ιδέα πως λύνεται το δεύτερο θέμα απο τις εξετάσεις του Φεβρουαρίου 2009?