[Θ.Υ.Α.] Απορίες στις ασκησεις 2014-2015

[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 με προσοχή στα ονόματα των αρχείων!

Για ανανέωση (ή προσθήκη νέου) avatar, πρέπει η μεγαλύτερη διάσταση της εικόνας να είναι 110 pixels.

[princess_of_the_dawn]

στο πρωτο pdf στην πρωτη ασκηση π λεει πρεπει να αποδειξω οτι καθε συμβολοσειρα της γινεται αποδεκτη απο το αυτοματο αυτο ισχυει γιατι καταληγει σε τελικη κατασταση q0 παντα ??

ξεκινάς από την αρχική κ/ση
για α καταλήγει πάλι σε q₀
για ββα έχουμε την διαδρομή q₀,b->q₁,b->q₂,a->q₀,e

αρα πάντα καταλήγει σε q0

[xameno kormi]

ποτε δεν θα ισχυε αυτο που μας λεει να αποδειξουμε? αν κατεληγε στην q1 ας πουμε ?

edit: απανταω στον εαυτο μου ναι τωρα το ειδα στις σημειωσεις οτι πρεπει να καταληγει σε τελικη κατασταση για να ναι αποδεκτη

[Σαλτιμπάγκος]

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

[Σαλτιμπάγκος]

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

κανενας; 

φεβ '13 ...το 1)α) καμια δεν ανηκει;;

[τσαι-borg]

εγώ νομίζω πως ανήκουν οι 1,2,4.

[SolidSNK]

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

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

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

[Slifer]

Όταν έχω μια μηχανή Turing, πρέπει να ορίσω τη μετάβαση δ(q,|>) (όπου με "|>" εννοώ το πλάγιο τριγωνάκι απ όπου ξεκινάμε) για όλες τις καταστάσεις, ή αρκεί να το ορίσω μόνο για την αρχική κατάσταση?
Επίσης, πρέπει σε όλες τις καταστάσεις q που έχω να ορίζω την δ για κάθε σύμβολο του Σ και αν όχι για αυτά που δεν ορίζω τι γίνεται αν βρεθεί εκεί η ΤΜ?

[Tracy_McGrady]

Όταν έχω μια μηχανή Turing, πρέπει να ορίσω τη μετάβαση δ(q,|>) (όπου με "|>" εννοώ το πλάγιο τριγωνάκι απ όπου ξεκινάμε) για όλες τις καταστάσεις, ή αρκεί να το ορίσω μόνο για την αρχική κατάσταση?
Επίσης, πρέπει σε όλες τις καταστάσεις q που έχω να ορίζω την δ για κάθε σύμβολο του Σ και αν όχι για αυτά που δεν ορίζω τι γίνεται αν βρεθεί εκεί η ΤΜ?

Όλα τα ορίζεις!

[princess_of_the_dawn]

εγώ νομίζω πως ανήκουν οι 1,2,4.

κι εγώ έτσι νομίζω

[Exomag]

εγώ νομίζω πως ανήκουν οι 1,2,4.

κι εγώ έτσι νομίζω

+1

[Tracy_McGrady]

Μπορεί κάποιος να εξηγήσει το κριτήριο άντλησης κανονικών γλωσσών( γιατί δεν βγάζω και πολύ νόημα απο τα παραδειγματα στο βιβλίο)???

[τσαι-borg]

αν πχ θελεις να δειξεις την μη κανονικοτητα της aⁿbⁿ, οπως στο παραδειγμα του βιβλιου.
εστω πως ειναι κανονικη, τοτε ισχυειτο θεωρημα αντλησης αρα η w=aⁿbⁿ τριχοτομειται σε xyz, με τς ιδιοτητες που αναφερει το θεωρημα. αν μπορει να γραφεται ετσι, δεν ειναι λογικο το y να ειναι τη μορφης a^k? αρα η w=a^n-ka^kbⁿ και μαλιστα το xyⁱz
πρεπει να ανηκει στ γλωσσα για ΚΑΘΕ i>=0.
επιλέγω i=0 και τοτε
a^n-ka^i*kbⁿ=>a^n-kbⁿ πρεπει να ανηκει στη γλωσσα. παπαρια ανηκε ομως γιατι n-k!=n. αρα παπαρια κανονικη ειναι.

[Σα τανυστής]

hey,

πως δειχνουμε οτι μια γραμματικη ειναι σαφης?

Φεβ '14 2 (β)

[Tracy_McGrady]

εγώ νομίζω πως ανήκουν οι 1,2,4.

κι εγώ έτσι νομίζω

+1

+10

[SolidSNK]

hey,

πως δειχνουμε οτι μια γραμματικη ειναι σαφης?

Φεβ '14 2 (β)

Το έλυσα στο άλλο τόπικ.