[Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες

[Thmmy.gr portal]

  Thmmy.gr portal
   Forum
   Downloads
   Ενεργ. Λογαριασμού
   Επικοινωνία
  
  Χρήσιμα links
   Σελίδα τμήματος
   Βιβλιοθήκη Τμήματος
   Elearning
   Φοιτητικά fora
   Πρόγραμμα Λέσχης
   Πρακτική Άσκηση
   Ηλεκτρονική Εξυπηρέτηση Φοιτητών
   Διανομή Συγγραμμάτων
   Ψηφιακό Καταθετήριο Διπλωματικών
   Πληροφορίες Καθηγητών
   Instagram @thmmy.gr
   mTHMMY
  
  Φοιτητικές Ομάδες
   ACM
   Aristurtle
   ART
   ASAT
   BEAM
   BEST Thessaloniki
   EESTEC LC Thessaloniki
   EΜΒ Auth
   IAESTE Thessaloniki
   IEEE φοιτητικό παράρτημα ΑΠΘ
   SpaceDot
   VROOM
   Panther
  

THMMY.gr Web

Helios_MultiScribbles2SMF Default ThemeSMFone_Blue

[Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads]

Είσαι πρωτοετής;... Καλώς ήρθες! Μπορείς να βρεις πληροφορίες εδώ. Βοήθεια για τους καινούργιους μέσω χάρτη.

Κατεβάστε εδώ το Android Application για εύκολη πρόσβαση στο forum.

Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads με προσοχή στα ονόματα των αρχείων!

[height=400]

  Όταν ανεβάζουμε φωτογραφίες στις Ανακοινώσεις και Έκτακτα νέα, βάζουμε τη μεγαλύτερη πλευρά 400 (width=400 ή height=400 ). π.χ. [img height=400 (κλείνει η αγκύλη) 

[κύριος Φασόλης]

απο τα θεματα του φεβρουαριου του 2015:

στο θεμα 2 πως κατασκευαζω την α) ?

στο θεμα 3 για να ανηκει η συμβολοσειρα στη γλωσσα L(G) αρκει στο κατω δεξια τετραγωνο του πινακα που προκυπτει για τον δυν.προγραμματισμο να βρω κατι που ανηκει στους κανονες της γλωσσας? (εν ολιγοις κατι διαφορο του κενου)

2α: Η γλώσσα είναι κενή, άρα δεν έχει καμία συμβολοσειρά, άρα η μηχανή δεν πρέπει να αποδέχεται καμία συμβολοσειρά. Με στοιχειώδεις Μ.Τ μπορείς απλά να κάνεις μία μηχανή που πάει δεξιά 1 και λέει Νο: R->No

3: Για να παράγεται η συμβολοσειρά από την γλώσσα, πρεπει στην κάτω δεξιά γωνία να έχεις σύμβολο της γλώσσας που βρίσκεται στο αριστερό μέρος κανόνα. Σε αυτή την περίπτωση S ή W ή C.
(pro tip: Συνήθως όταν βάζει άσκηση με ΔΠ η συμβολοσειρά δεν παράγεται από τη γλώσσα, το βάζει μιας και ο ΔΠ είναι ο μόνος τρόπος να το αποδείξεις αυτό, ενώ αντίθετα μπορείς να αποδείξεις και χωρίς ΔΠ ότι ανήκει μια συμβολοσειρά στη γλώσσα σου) S

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

EDIT: Βλ. βιβλίο σελίδα 213 πάνω πάνω

ωραιος! ναι εχεις δικιο

[greekoo]

Mπορεί κάποιος μια και καλή να απαντήσει στις ερωτήσεις του τύπου: "Να αποδείξετε ότι το σύνολο των αναδρομικa απαριθμήσιμο γλωσσών είναι κλειστό ως προς ένωση,παράθεση κλπ;; " 

Πιστεύω είναι πολύ πιθανό να πέσει κάτι τέτοιο αύριο μιας και δν έπεσε ούτε το Σεπτέμβρη ούτε πέρυσι.
(Βλέπε φωτο, για κάποιο λόγο δεν μπορω να την βάλω embedded)

http://oi64.tinypic.com/abtpic.jpg

[κύριος Φασόλης]

Mπορεί κάποιος μια και καλή να απαντήσει στις ερωτήσεις του τύπου: "Να αποδείξετε ότι το σύνολο των αναδρομικa απαριθμήσιμο γλωσσών είναι κλειστό ως προς ένωση,παράθεση κλπ;; " 

Πιστεύω είναι πολύ πιθανό να πέσει κάτι τέτοιο αύριο μιας και δν έπεσε ούτε το Σεπτέμβρη ούτε πέρυσι.
(Βλέπε φωτο, για κάποιο λόγο δεν μπορω να την βάλω embedded)

http://oi64.tinypic.com/abtpic.jpg

+1

[Λήσταρχος Γιαγκούλας]

+@itsitsou

αναφορικά με τις λύσεις του 03/02/15 θέμα 1 ερώτημα γ
http://www.intelligence.tuc.gr/~theory/previous/Theory_2007/lectures/theory2007lecture04.pdf
και την σελίδα 6 μήπως το γ είναι τελικά σωστό?(abb,bba ισοδύναμα καθώς καμία δεν ανήκει στη νέα L)?

+Ευχαριστούμε πολύ για το υλικό σου. 

[isitsou]

Έγινε μια συζήτηση για αυτό το ερώτημα στο "[Θ.Υ.Α.] Γενικές απορίες και ανακοινώσεις/επικαιρότητα 2015-2016". Ρίξε μια ματιά εκεί αν θες, νομίζω ότι αυτό που έγραψα στα λυμένα θέματα είναι τελικά σωστό.

[isitsou]

                                                 S                                  S
                                                 |                                    |
                                               S+S                              S + S
                                               |    |                               /      \
                                               a+S+S                       S+S + S
                                               |   |    |                        |    |      |
                                               a + b  + a                   a+b   + a

Ελα ρε παιχταρα,στο α ερώτημα και γω το ίδιο έκανα  

Τετοιος ειμαι αφου ξες

Το αυτοματο ΑΣ μετα με ποια λογικη το κανουμε?

Δες το παράδειγμα στην σελίδα 12 του 3ου Μέρους διαφανειών. 

[Andromedas]

Έγινε μια συζήτηση για αυτό το ερώτημα στο "[Θ.Υ.Α.] Γενικές απορίες και ανακοινώσεις/επικαιρότητα 2015-2016". Ρίξε μια ματιά εκεί αν θες, νομίζω ότι αυτό που έγραψα στα λυμένα θέματα είναι τελικά σωστό.

Είναι σωστό βάση του θεωρήματος  myhill Nerode σελ 138 και επειδή το απα που σχεδιάσαμε είναι το ελάχιστο άρα κλάσεις ισοδυναμίας της L είναι οι καταστάσεις του Μ   (αφού είναι οι ελάχιστες).
Νομίζω ότι το έχω καταλάβει σωστά αν δεν ισχύει πείτε τπτ

[Eilex]

μπορεί κάποιος να μου εξηγήσει το θέμα 3 φεβρουάριος του 11??

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

'Η απλά λες (για να 'χεις στο τσεπάκι το ερώτημα πριν φτάξεις μηχανή) ότι η παράθεση κανονικών εκφράσεων παράγει κανονική γλώσσα (w κανονική όπως και ο χαρακτήρας 'c'), άρα υπάρχει πεπερασμένο αυτόματο και άρα υπάρχει T.M.

Επίσης ζητάει την ύπαρξη T.M. που να την αποφασίζει και όχι να την ημι-αποφασίζει. Άρα μάλλον όχι, ισοδύναμα δε σου λέει να δείξεις ότι είναι αναδρομικά απαριθμήσιμη αλλά αναδρομική.

Η wcw δεν απαιτει μνημη;μπορει να ειναι παραθεση κανονικων γλωσσων αλλα εχει το στοιχειο οτι επαναλαμβανεται ακριβως η ιδια συμβολοσειρα!Δεν μπορει να ξερει το αυτοματο τι εχει γινει πριν το c ωστε να το επαναλαβει.

[Niobe]

Εχει κανεις τελειωμενο το θεμα 2 φλεβαρης '15??

Επισης αν μπορει να εξηγησει καποιος την εξαλειψη κοντων κανονων  για ΚΜC

[Κηπουρίδης]

Mπορεί κάποιος μια και καλή να απαντήσει στις ερωτήσεις του τύπου: "Να αποδείξετε ότι το σύνολο των αναδρομικa απαριθμήσιμο γλωσσών είναι κλειστό ως προς ένωση,παράθεση κλπ;; "  

Πιστεύω είναι πολύ πιθανό να πέσει κάτι τέτοιο αύριο μιας και δν έπεσε ούτε το Σεπτέμβρη ούτε πέρυσι.
(Βλέπε φωτο, για κάποιο λόγο δεν μπορω να την βάλω embedded)

http://oi64.tinypic.com/abtpic.jpg

+1

Οι συγκεκριμενες ερωτησεις ειναι οι πιο δυσκολες ερωτησεις κλειστοτητας που μπορουν να πεσουν, κι αυτο γιατι ειναι πιθανο η αντιστοιχη turing machine (TM) που ημι-αποφασιζει μια αναδρομικα απαριθμήσιμη γλώσσα να μην τελειωνει ποτε. Η τεχνικη που θα χρησιμοποιησω ξεπερναει αυτο το προβλημα, ομως αφου ο,τι αλλο και να βαλει (κανονικες γλωσσες, αναδρομικες γλωσσες) εχουμε αντιστοιχα μηχανημα που τερματιζει με σιγουρια, τα πραγματα γινονται πολυ πιο απλα.

Παραθεση : Εχουμε δηλαδη TM1 που ημιαποφασιζει L1 και TM2 που ημιαποφασιζει L2. Με μια καινουρια TM δημιουργουμε ολα τα πιθανα w1, w2 ωστε να ισχυει w1w2 = w, οπου w το input. Προφανως αν |w| = n τοτε τα πιθανα σπασιματα που θα κανουμε ειναι περιπου n (για την ακριβεια ειναι n+1 γιατι w1 μπορει να ειναι απο κενο μεχρι w).
Η δουλεια που θα κανει το TM μας κατοπιν ειναι καπως ετσι :
for (i=1; true; ++i) //Δε σταματαει ποτε
 for all possible pairs w1,w2
  simulate one step of w1 using TM1
  simulate one step of w2 using TM2
  if both accepted
   accept

Μπορουμε να αποδειξουμε ευκολα οτι ετσι ημιαποφασιζεται η L1L2. Εξ ορισμου αν το w ανηκει L1L2 τοτε υπαρχουν δυο strings w1 ανηκει L1 και w2 ανηκει L2, το καθε ενα απ τα οποια ημιαποφασιζεται απο την TM1 ή την TM2 (εστω σε x βηματα το ενα και σε y βηματα το αλλο). Οταν i=max {x,y }+1 τοτε θα εχουν ηδη γινει αρκετα βηματα και για τα δυο strings ωστε να εχουν αποδεχτει και τα δυο, κι ετσι η TM μας θα αποδεχτει.
Μπορουμε ευκολα να δουμε οτι αν δεν υπαρχουν τετοια strings (w δεν ανηκει L1L2) τοτε η TM μας δε θα σταματησει ποτε, ομως δεν ειναι καν αναγκαστικο αυτο! Αρκει αυτο που αποδειξαμε.

Η ενωση ειναι καπως πιο ευκολη, γιατι δε χρειαζεται τα διαφορα σπασιματα και συνεπως την εσωτερικη for.

Το kleene star με την ιδια ακριβως λογικη, το σπαμε με ολους τους δυνατους τροπους που γινεται και προσομοιωνουμε μεχρι κατι απο ολους αυτους τους (παρα παρα παρα πολλους, αλλα πεπερασμενους) τροπους να αποδεχτει.

Το κλειδι ειναι δηλαδη οτι εργαζομαστε παραλληλα σε ολα, ετσι ωστε ακομα κι αν κατι μπει σε infinite loop, οι υπολοιποι να μπορουν να συνεχισουν.

Το (α) ερωτημα ειναι γελοιο, αρκει να κανουμε μια αντιστοιχη TM που θα εχει 3 καταστασεις ετσι οπως το σκεφτομαι ολες κι ολες.
Το (γ) ειναι ενδιαφερον, λεμε οτι αφου ισχυει το (α) (base case), και μπορουμε να εφαρμοσουμε καθε πραξη που εφαρμοζεται στις κανονικες εκφρασεις, αρα μπορουμε να ημι-αποφασισουμε καθε γλωσσα που οριζεται απο κανονικη εκφραση. Εξ ορισμου αυτες ειναι οι κανονικες γλωσσες.

Παρατηρηση 1 :
Το γεγονος οτι δε γνωριζουμε τα x και y που εγραψα δε μας πειραζει, αφου η επαναληψη μας τρεχει επ απειρον, οποτε σιγουρα (αν υπαρχουν x και y, δηλαδη αν ανηκει το w στην L1L2) καποια στιγμη θα τα πετυχει.
Παρατηρηση 2:
Τα πραγματα θα γινονταν δραματικα ευκολοτερα αν μας ζητουσε το ιδιο πραγμα για αναδρομικες γλωσσες. Τοτε υπαρχει TM που σιγουρα τερματιζει, οποτε δε χρειαζεται το κολπο της (σειριακης) παραλληλοποιησης. Απλως θα τρεχαμε ολα τα ζευγαρια μεχρι να τελειωσουν κι αν εστω κι ενα ζευγαρι ειχε δυο YES θα αποδεχομασταν, αλλιως δε θα αποδεχομασταν.

[SolidSNK]

μπορεί κάποιος να μου εξηγήσει το θέμα 3 φεβρουάριος του 11??

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

'Η απλά λες (για να 'χεις στο τσεπάκι το ερώτημα πριν φτάξεις μηχανή) ότι η παράθεση κανονικών εκφράσεων παράγει κανονική γλώσσα (w κανονική όπως και ο χαρακτήρας 'c'), άρα υπάρχει πεπερασμένο αυτόματο και άρα υπάρχει T.M.

Επίσης ζητάει την ύπαρξη T.M. που να την αποφασίζει και όχι να την ημι-αποφασίζει. Άρα μάλλον όχι, ισοδύναμα δε σου λέει να δείξεις ότι είναι αναδρομικά απαριθμήσιμη αλλά αναδρομική.

Η wcw δεν απαιτει μνημη;μπορει να ειναι παραθεση κανονικων γλωσσων αλλα εχει το στοιχειο οτι επαναλαμβανεται ακριβως η ιδια συμβολοσειρα!Δεν μπορει να ξερει το αυτοματο τι εχει γινει πριν το c ωστε να το επαναλαβει.

Αν η εκφώνηση αναφέρεται στο ίδιο, αυτούσιο w πριν και μετά το c τότε δε μιλάμε για παράθεση κανονικών γλωσσών και ναι δεν είναι regular αλλά context-free. Για να αποδειχθεί αναδρομικότητα εδώ θα κατασκεύαζα την αντίστοιχη context-free grammar (άρα υπάρχει αυτόματο στοίβας και άρα υπάρχει Τ.Μ.).

Δεν το σκέφτηκα ότι αναφέρεται στο ίδιο string. Αν ισχύει, good spot!

[SolidSNK]

Mπορεί κάποιος μια και καλή να απαντήσει στις ερωτήσεις του τύπου: "Να αποδείξετε ότι το σύνολο των αναδρομικa απαριθμήσιμο γλωσσών είναι κλειστό ως προς ένωση,παράθεση κλπ;; "  

Πιστεύω είναι πολύ πιθανό να πέσει κάτι τέτοιο αύριο μιας και δν έπεσε ούτε το Σεπτέμβρη ούτε πέρυσι.
(Βλέπε φωτο, για κάποιο λόγο δεν μπορω να την βάλω embedded)

http://oi64.tinypic.com/abtpic.jpg

+1

Οι συγκεκριμενες ερωτησεις ειναι οι πιο δυσκολες ερωτησεις κλειστοτητας που μπορουν να πεσουν, κι αυτο γιατι ειναι πιθανο η αντιστοιχη turing machine (TM) που ημι-αποφασιζει μια αναδρομικα απαριθμήσιμη γλώσσα να μην τελειωνει ποτε. Η τεχνικη που θα χρησιμοποιησω ξεπερναει αυτο το προβλημα, ομως αφου ο,τι αλλο και να βαλει (κανονικες γλωσσες, αναδρομικες γλωσσες) εχουμε αντιστοιχα μηχανημα που τερματιζει με σιγουρια, τα πραγματα γινονται πολυ πιο απλα.

Παραθεση : Εχουμε δηλαδη TM1 που ημιαποφασιζει L1 και TM2 που ημιαποφασιζει L2. Με μια καινουρια TM δημιουργουμε ολα τα πιθανα w1, w2 ωστε να ισχυει w1w2 = w, οπου w το input. Προφανως αν |w| = n τοτε τα πιθανα σπασιματα που θα κανουμε ειναι περιπου n (για την ακριβεια ειναι n+1 γιατι w1 μπορει να ειναι απο κενο μεχρι w).
Η δουλεια που θα κανει το TM μας κατοπιν ειναι καπως ετσι :
for (i=1; true; ++i) //Δε σταματαει ποτε
 for all possible pairs w1,w2
  simulate one step of w1 using TM1
  simulate one step of w2 using TM2
  if both accepted
   accept

Μπορουμε να αποδειξουμε ευκολα οτι ετσι ημιαποφασιζεται η L1L2. Εξ ορισμου αν το w ανηκει L1L2 τοτε υπαρχουν δυο strings w1 ανηκει L1 και w2 ανηκει L2, το καθε ενα απ τα οποια ημιαποφασιζεται απο την TM1 ή την TM2 (εστω σε x βηματα το ενα και σε y βηματα το αλλο). Οταν i=max {x,y }+1 τοτε θα εχουν ηδη γινει αρκετα βηματα και για τα δυο strings ωστε να εχουν αποδεχτει και τα δυο, κι ετσι η TM μας θα αποδεχτει.
Μπορουμε ευκολα να δουμε οτι αν δεν υπαρχουν τετοια strings (w δεν ανηκει L1L2) τοτε η TM μας δε θα σταματησει ποτε, ομως δεν ειναι καν αναγκαστικο αυτο! Αρκει αυτο που αποδειξαμε.

Η ενωση ειναι καπως πιο ευκολη, γιατι δε χρειαζεται τα διαφορα σπασιματα και συνεπως την εσωτερικη for.

Το kleene star με την ιδια ακριβως λογικη, το σπαμε με ολους τους δυνατους τροπους που γινεται και προσομοιωνουμε μεχρι κατι απο ολους αυτους τους (παρα παρα παρα πολλους, αλλα πεπερασμενους) τροπους να αποδεχτει.

Το κλειδι ειναι δηλαδη οτι εργαζομαστε παραλληλα σε ολα, ετσι ωστε ακομα κι αν κατι μπει σε infinite loop, οι υπολοιποι να μπορουν να συνεχισουν.

Το (α) ερωτημα ειναι γελοιο, αρκει να κανουμε μια αντιστοιχη TM που θα εχει 3 καταστασεις ετσι οπως το σκεφτομαι ολες κι ολες.
Το (γ) ειναι ενδιαφερον, λεμε οτι αφου ισχυει το (α) (base case), και μπορουμε να εφαρμοσουμε καθε πραξη που εφαρμοζεται στις κανονικες εκφρασεις, αρα μπορουμε να ημι-αποφασισουμε καθε γλωσσα που οριζεται απο κανονικη εκφραση. Εξ ορισμου αυτες ειναι οι κανονικες γλωσσες.

Παρατηρηση 1 :
Το γεγονος οτι δε γνωριζουμε τα x και y που εγραψα δε μας πειραζει, αφου η επαναληψη μας τρεχει επ απειρον, οποτε σιγουρα (αν υπαρχουν x και y, δηλαδη αν ανηκει το w στην L1L2) καποια στιγμη θα τα πετυχει.
Παρατηρηση 2:
Τα πραγματα θα γινονταν δραματικα ευκολοτερα αν μας ζητουσε το ιδιο πραγμα για αναδρομικες γλωσσες. Τοτε υπαρχει TM που σιγουρα τερματιζει, οποτε δε χρειαζεται το κολπο της (σειριακης) παραλληλοποιησης. Απλως θα τρεχαμε ολα τα ζευγαρια μεχρι να τελειωσουν κι αν εστω κι ενα ζευγαρι ειχε δυο YES θα αποδεχομασταν, αλλιως δε θα αποδεχομασταν.

Ρίξτε και μια ματιά και σε παλαιότερη απόπειρα μου.

απο φεβ. 14 το 3ο θεμα πως λυνεται;   

Για το α) και το β) υπάρχουν αρκετοί τρόποι. Εξαρτάται τι ακριβώς θέλει από σένα. Μπορείς να πεις από τη θεωρία πως γνωρίζουμε πως κάθε κανονική γλώσσα είναι αναδρομική, αλλά δε νομίζω να ζητάει αυτό. So, θα σου πρότεινα τόσο το α) όσο και το β) να το πας κατασκευαστικά. Το μεν α) σχεδιάζοντας μια TM από το εκφυλισμένο FSA που αποφασίζει τη γλώσσα, ενώ για το μεν β) νομίζω έχω ήδη ποστάρει παλαιότερα τη λύση σε τέτοια θέματα: υπέθεσε πως έχεις 2 TM που αποφασίζουν τις L1 και L2, με την L3 να δέχεται την έξοδο τους και να εκτελεί OR, συνάρτηση που προφανώς είναι αναδρομική.

Για το γ) είμαι σίγουρος πως θέλει κάτι αυστηρό. So be it. Αρχικά, υπέθεσε ένα αλφάβητο και πες ότι η τετριμμένη γλώσσα που αποτελείται από ένα μόνο γράμμα του αλφαβήτου (π.χ. La={a}) είναι αναδρομική. Δε νομίζω να χρειάζεται εξήγηση αυτό, άμα θες να είσαι τέρμα αυστηρός φτιάξε τη χαζή TM που αναγνωρίζει το γράμμα. Εφόσον δίνεται πως το σύνολο των ανδρομικών γλωσσών είναι κλειστό προς αυτές τις πράξεις, τότε η κλειστότητα των τετριμμέννων {a}, {b}, {c}... γλωσσών με τις συγκεκριμένες πράξεις θα είναι επίσης αναδρομικές γλώσσες. Όμως σύμφωνα με τον ορισμό (δες κεφάλαιο "Πεπερασμένη αναπαράσταση των γλωσσών" από το βιβλίο), αυτή η κλειστότητα είναι το σύνολο των κανονικών γλωσσών ως προς το συγκεκριμένο αλφάβητο. Άρα κάθε κανονική γλώσσα είναι αναδρομική.

[Κηπουρίδης]

Ρίξτε και μια ματιά και σε παλαιότερη απόπειρα μου.

απο φεβ. 14 το 3ο θεμα πως λυνεται;   

Για το α) και το β) υπάρχουν αρκετοί τρόποι. Εξαρτάται τι ακριβώς θέλει από σένα. Μπορείς να πεις από τη θεωρία πως γνωρίζουμε πως κάθε κανονική γλώσσα είναι αναδρομική, αλλά δε νομίζω να ζητάει αυτό. So, θα σου πρότεινα τόσο το α) όσο και το β) να το πας κατασκευαστικά. Το μεν α) σχεδιάζοντας μια TM από το εκφυλισμένο FSA που αποφασίζει τη γλώσσα, ενώ για το μεν β) νομίζω έχω ήδη ποστάρει παλαιότερα τη λύση σε τέτοια θέματα: υπέθεσε πως έχεις 2 TM που αποφασίζουν τις L1 και L2, με την L3 να δέχεται την έξοδο τους και να εκτελεί OR, συνάρτηση που προφανώς είναι αναδρομική.

Για το γ) είμαι σίγουρος πως θέλει κάτι αυστηρό. So be it. Αρχικά, υπέθεσε ένα αλφάβητο και πες ότι η τετριμμένη γλώσσα που αποτελείται από ένα μόνο γράμμα του αλφαβήτου (π.χ. La={a}) είναι αναδρομική. Δε νομίζω να χρειάζεται εξήγηση αυτό, άμα θες να είσαι τέρμα αυστηρός φτιάξε τη χαζή TM που αναγνωρίζει το γράμμα. Εφόσον δίνεται πως το σύνολο των ανδρομικών γλωσσών είναι κλειστό προς αυτές τις πράξεις, τότε η κλειστότητα των τετριμμέννων {a}, {b}, {c}... γλωσσών με τις συγκεκριμένες πράξεις θα είναι επίσης αναδρομικές γλώσσες. Όμως σύμφωνα με τον ορισμό (δες κεφάλαιο "Πεπερασμένη αναπαράσταση των γλωσσών" από το βιβλίο), αυτή η κλειστότητα είναι το σύνολο των κανονικών γλωσσών ως προς το συγκεκριμένο αλφάβητο. Άρα κάθε κανονική γλώσσα είναι αναδρομική.

Εχει λαθος αυτο που εγραψες στο (β). Κι αυτο επειδη λεγοντας να παρεις το OR δυο πραγματων χωρις να πεις τον τροπο με τον οποιο θα το παρεις μπορει να πεσεις σε infinite loop (προυποθετεις εσωτερικα χωρις να το εχεις πει οτι τα TM θα τερματισουν, χωρις αυτο απαραιτητα να ισχυει ομως). Πρεπει οπωσδηποτε να γινει η (σειριακη) παραλληλοποιηση ωστε ακομα κι αν ενα σπασιμο w1w2 ειναι αποτυχημενο, να μην επηρεασει τα υπολοιπα σπασιματα που μπορει να τερματισουν.

[Andromedas]

Εχει κανεις τελειωμενο το θεμα 2 φλεβαρης '15??

Επισης αν μπορει να εξηγησει καποιος την εξαλειψη κοντων κανονων  για ΚΜC

Με επιφύλαξη για το α)
θεμα 2 φλεβαρης '15

[Κηπουρίδης]

Εχει κανεις τελειωμενο το θεμα 2 φλεβαρης '15??

Επισης αν μπορει να εξηγησει καποιος την εξαλειψη κοντων κανονων  για ΚΜC

Η λογικη ειναι οτι απλως τους αφαιρεις, και μετα κοιτας που μπορει να ειχαν συνεισφερει.
Πχ αν εχεις S->AB και A->k τοτε αυτο θα μπορουσε να συνεισφερει στον S ως S->kB (απλη αντικατασταση). Πας και ενημερωνεις ολους οσους μπορει να επηρεαστηκαν απο την αφαιρεση του κοντου κανονα με αμεση αντικατασταση και θα εισαι τζετ στα πλαισια της εξετασης.