ΑΝΤΕ ΡΕ ΝΤΕΛΟΠΟΥΛΕΕΕΕΕΕ!!

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

Και καλά η s2 είναι η αρχική κατάσταση. Κανονικά η λέξη που θα διαβαστεί μπάινει μετά το πρώτο κενό δεξιά από το σύμβολο αρχής. Οπότε λέω ότι άμα διαβάσεις με την αρχική κατάσταση αυτό το πρώτο κενό, τότε δεξιά σου αρχίζει η λέξη. Αν τώρα η λέξη ειναι κενή, θα διαβάσω ακόμα ένα κενό και θα το δεχτώ. Αλλιως, αν δεχομουν τη λέξη από το πρώτο κενό, πιθανώς να δεχομουν κάθε λέξη αφού δεν θα είχα ελέγξει αν υπάρχει λέξη μετά το κενό αυτό.

Νομίζω το 2ο είναι λάθος. Η γλώσσα ουσιαστικα δέχεται οποιαδήποτε λέξη, αρκεί να αρχίζει με α, αφού κάθε λέξη είναι παραθεση των λέξεων, {α, αβ, αββ..} κλπ. Από τη στιγμή που έχει αρχίσει με α, μετά μπορείς να βάλεις ας πουμε οσα β θες και όσα α, αφού η α ανήκει στη γλώσσα και όλα τα β θα ακολουθούνται πάντα από τουλάχιστον ένα α.

Πρέπει να αποδείξεις ότι ξεκινώντας με δύο αναδρομικά απαριθμήσιμες γλώσσες και εφαρμόζοντας τις σχέσεις Ενωση, Παραθεση και Kleene Star, θα καταλήξεις πάλι σε αναδρομικά απαριθμήσιμη γλώσσα. Γενικά οι αποδείξεις αυτές βγαίνουν βρίσκοντας μηχανές Turing που (ημι)αποφασίζουν την εκάστοτε γλώσσα. Για παράδειγμα, για τη γλώσσα (L1 Ένωση L2) , μπορούμε να πούμε ότι η μηχανή που την αποφασίζει είναι μια η οποία ξεκινάει με την μηχανή της L1. Αν δεν τερματίσει αυτή, πηγαίνει πίσω την ταινία στην αρχή της λέξης με μια βασική μηχανή L και συνεχίζει με τη μηχανή της L2. Άρα και η ένωση αναδρομικά απαριθμήσιμων γλωσσών παράγει αναδρομικά απαριθμήσιμη γλώσσα.

Για την παράθεση, απλά βάζεις τη μία μηχανή δίπλα στην άλλη.

Για το Kleene Star της L1 π.χ., αυτό που σκέφτηκα είναι μια μηχανή που θα αρχίζει με τη μηχανή Μ1 της L1. Πριν φτάσει σε κατάσταση αποδοχής μιας λέξης (π.χ. μετά από κάποια βήματα, αν διαβάσει ακόμα ένα α, αποδέχεται τη λέξη της L1), σ αυτό το σημείο, βάζουμε ακόμα μια μηχανή που ελέγχει αν το επόμενο στοιχείο είναι κενό ή όχι, Αν είναι, τότε πάμε σε κατάσταση αποδοχής. Αν δεν είναι, πάμε τη ταινία ένα χαρακτήρα πίσω και πάμε πάλι στην αρχή της μηχανής. Ουσιαστικά, έτσι διαβάζουμε μία μία τις λέξεις από τις οποίες αποτελείται μια λέξη του Kleene Star. Επίσης πρέπει να βάλουμε και μια μηχανή έτσι ώστε αν διαβάσει πρώτο χαρακτήρα κενό, να κάνει αποδοχή.

Τέλος, κάθε κανονική γλώσσα αποτελείται από τις βασικές γλώσσες L[a], a ανήκει στο Σ, τη κενή γλώσσα και τους συνυδασμούς τους μέσω των πράξεων της ένωσης, της παράθεσης και του Kleene Star. Άρα, αφού έχεις αποδείξει τα παραπάνω για κάθε γλώσσα, μπορείς να ισχύριστείς ότι κάθε κανονική γλώσσα είναι και αναδρομικά απαριθμήσιμη

Αρκετά σίγουρος. Έλεγξα ποιες λέξεις διαβάζει και ποιες όχι και μου φάνηκε σωστό. Αν θες, ανέβασε και το δικό σου να δω μηπως όντως έχω κάποιο λάθος.

Θέμα 2ο και 3ο Ιουνιου 2016

@WatchDog, αν έχεις τα θέματα ολοκληρωμένα, ανέβασε τα πλζ.

Σύνδρομο της Στοκχολμης λέγεται

ΨΗΦΙΑΚΑ ΙΙ ΣΗΜΕΡΑ ΤΟ ΒΡΑΔΥ!
ΘΥΑ ΚΑΠΟΙΑ ΣΤΙΓΜΗ ΜΕΣΑ ΣΤΟ 2016!