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

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

[Πληροφορίες Καθηγητών]

Πληροφορίες Καθηγητών

[Ragnar]

παιδιά τι παίζει με το θέμα 2 του 2/2013? 

[Exomag]

παιδιά τι παίζει με το θέμα 2 του 2/2013? 

Ποια ακριβώς είναι η απορία σου;

Ειδικά τα (β) και (γ) έχουν εντελώς μεθοδευμένο τρόπο λύσης.

[Ragnar]

βασικα αφου στο αυτόματο που μας έδωσε δεν μπορούμε να επισκεφθούμε όλες τις καταστάσεις! αρα δεν ειναι αιτοκρατικό νμζ δλδ. πχ εκεί που λέει κανονική έκφραση ποία είναι? η  βααβ? τετοιο εννοεί? και επίσης στο τελευταίο για το αυτόματο δημιουργούμε δικία μας συμβολοσειρά? δεν ξέρω με έχει μπερδέψει λίγο αυτή .....

[SolidSNK]

παιδιά τι παίζει με το θέμα 2 του 2/2013?  

Το α) δεν είναι τόσο προφανές. Γενικά αν τυχαίνει κάποιου είδους άρνηση από το FSA, όπως εδώ που σου λέει: "μετά το ba δε θα δεχτώ αμέσως κι άλλο ba" τα πράγματα περιπλέκονται (π.χ. βιβλίο σελ. 82). Εμένα μου βγήκε κάτι σε a*(a*baa)*((ba)Ua*). Το 3ο θέμα είναι πιο ενδιαφέρον (άμα θες να κάνεις αυστηρά σωστές αποδείξεις).

βασικα αφου στο αυτόματο που μας έδωσε δεν μπορούμε να επισκεφθούμε όλες τις καταστάσεις! αρα δεν ειναι αιτοκρατικό νμζ δλδ. πχ εκεί που λέει κανονική έκφραση ποία είναι? η  βααβ? τετοιο εννοεί? και επίσης στο τελευταίο για το αυτόματο δημιουργούμε δικία μας συμβολοσειρά? δεν ξέρω με έχει μπερδέψει λίγο αυτή .....

Ναι εννοείται οι 2 δεξιές απαλείφονται. Για το τελευταίο κάθε FSA μπορεί να αναπαρασταθεί με ένα εκφυλισμένο αυτόματο στοίβας... που δε χρησιμοποιεί τη στοίβα. Κάθε μηχανή στην ιεραρχία chomsky μπορεί να κάνει ό,τι κάνουν και οι κατώτερες της.

[τσαι-borg]

παιδιά τι παίζει με το θέμα 2 του 2/2013?  

Το α) δεν είναι τόσο προφανές. Γενικά αν τυχαίνει κάποιου είδους άρνηση από το FSA, όπως εδώ που σου λέει: "μετά το ba δε θα δεχτώ αμέσως κι άλλο ba" τα πράγματα περιπλέκονται (π.χ. βιβλίο σελ. 82). Εμένα μου βγήκε κάτι σε a*(a*baa)*((ba)Ua*). Το 3ο θέμα είναι πιο ενδιαφέρον (άμα θες να κάνεις αυστηρά σωστές αποδείξεις).

γιατί να μην είναι η (a*(baa*))* η κ.ε.?

[SolidSNK]

παιδιά τι παίζει με το θέμα 2 του 2/2013?  

Το α) δεν είναι τόσο προφανές. Γενικά αν τυχαίνει κάποιου είδους άρνηση από το FSA, όπως εδώ που σου λέει: "μετά το ba δε θα δεχτώ αμέσως κι άλλο ba" τα πράγματα περιπλέκονται (π.χ. βιβλίο σελ. 82). Εμένα μου βγήκε κάτι σε a*(a*baa)*((ba)Ua*). Το 3ο θέμα είναι πιο ενδιαφέρον (άμα θες να κάνεις αυστηρά σωστές αποδείξεις).

γιατί να μην είναι η (a*(baa*))* η κ.ε.?

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

[Ex_Mechanus]

Επίσης το a*(a*baa)*((ba)Ua*) δεν μπορεί να παράξει το baabaaaabaaaa πχ το οποίο κάνει δεκτό το αυτόματο. a*(a*baa)*(((baaa*)*)Ua*) μήπως?

[SolidSNK]

Επίσης το a*(a*baa)*((ba)Ua*) δεν μπορεί να παράξει το baabaaaabaaaa πχ το οποίο κάνει δεκτό το αυτόματο. a*(a*baa)*(((baaa*)*)Ua*) μήπως?

Τι λες, μια χαρά μπορεί. Χαζέ.

Αι αι, δεν τη δέχεται ε....

[SolidSNK]

1ον αυτό. Και 2ον εσύ δέχεσαι συμβολοσειρές που τελειώνουν σε ba (που θα έπρεπε)?

[SolidSNK]

Μμμ νομίζω τώρα καλύτερα: a*(a*baaa*)*((ba)Ua*)

[Ex_Mechanus]

Σωστός αυτό σκεφτόμουν, μαλακία έγραψα.

[τσαι-borg]

Εκτιμητέα οποιαδήποτε ιδέα για Φεβρουάριο 2014, θέμα 2, ερώτημα β.

[SolidSNK]

Το γενικό πρόβλημα της ασάφειας μιας γραμματικής είναι άλυτο, αλλά στην περίπτωση μας ο Ντελό μπορεί να καλύπτεται από το παρακάτω.

Για να είναι μια γραμματική ασαφής, σημαίνει ότι μπορούν ανόμοιες αριστερότερες παραγωγές να καταλήξουν στην ίδια γραμματοσειρά. Το θέμα είναι πως στην περίπτωση μας, κάθε παραγωγή εισάγει και διαφορετικό τερματικό σε κάποιο σημείο στα αριστερά της παραγώμενης γραμματοσειράς: '+', '-', 'α', 'β' αντίστοιχα. Έτσι για κάθε αριστερή παραγωγή, η αρχή της συμβολοσειράς αποτελείται από διαφορετική "υποσυμβολοσειρά", αποκλείοντας μια πιθανή ασάφεια. Σαφής.

[Lord]

Εμένα μου βγήκε κάτι σε a*(a*baa)*((ba)Ua*). Το 3ο θέμα είναι πιο ενδιαφέρον (άμα θες να κάνεις αυστηρά σωστές αποδείξεις).

Για το 1ο και το 2ο ερώτημα αρκεί να φτιάξουμε μηχανές Turing που να αποφασίζουν αυτές τις γλώσσες;
Το 3ο δεν είναι τετριμμένο με βάση τα δεδομένα που μας δίνει; 

[SolidSNK]

Εμένα μου βγήκε κάτι σε a*(a*baa)*((ba)Ua*). Το 3ο θέμα είναι πιο ενδιαφέρον (άμα θες να κάνεις αυστηρά σωστές αποδείξεις).

Για το 1ο και το 2ο ερώτημα αρκεί να φτιάξουμε μηχανές Turing που να αποφασίζουν αυτές τις γλώσσες;
Το 3ο δεν είναι τετριμμένο με βάση τα δεδομένα που μας δίνει; 

Ναι το α και το β δεν είναι τπτ.. Ουσιαστικά στο γ αναφέρομουν. Η πρόταση είναι προφανής, αλλά η αυστηρή, σωστά διατυπωμένη απόδειξη χρησιμοποιώντας μόνο αυτά σου δίνει ήταν κατ' εμέ πιο ενδιαφέρουσα από τα υπόλοιπα: https://www.thmmy.gr/smf/index.php?topic=61695.msg1070684#msg1070684