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

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

[12:00-13:30]

Η γραμματεία είναι ανοιχτή καθημερινά 12:00-13:30

[antoniat]

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

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

απλα ξερεις τι δεν καταλαβαινω...λεει y=wcw ..αυτο το w ειναι ιδιο πριν και μετα το c? δηλαδη εχει μνημη η μηχανη??η καθε φορα ειναι διαφορετικο πριν και μετα το c??ελπίζω να έγινα κατανοητη..

Ναι η συμβολοσειρα πριν θελεις να ειναι ιδια μετά

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

έχει παρόμοιο λυμένο μες στο βιβλίο. Δε σου ζητάει να υλοποιήσεις μηχανη που να φτιάχνει τέτοιες γλώσσες αλλά που να τις αναγνωρίζει!

πωωω δικιο!οκ ευχαριστω!

[SolidSNK]

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

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

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

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

[antoniat]

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

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

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

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

κομπλε ευχαριστω!

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

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

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

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

[et3rn1ty]

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

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

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

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

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

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

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

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

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

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

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

thanks

αρα δηλαδη στο συγκεκριμενο θεμα ανηκει η συμβολοσειρα που μου δινει στη γλωσσα right?

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

Καλημέρα,
έχει δει κανείς το ερώτημα β του 2ου θέματος Σεπτ15;

Yποψιάζομαι πως η γραμματική είναι ΣΑΦΗΣ αλλα δεν ξέρω πως να το αποδείξω.
Κάθε βοήθεια ευπρόσδεκτη,ευχαριστώ.

edit :
Mαλλον ΑΣΑΦΗΣ είναι.Βασίζομαι στην υπόθεση ότι το +ab μπορεί να προέλθει είτε από +SX είτε από +XS τα οποία έρχονται από +SS.
Σωστά;

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

ΦΕΒ 2014

Θεμα 1
 
στο γ ερωτημα για να δω αν ειναι ισοδυναμες απλα τις "τρεχω" στο ΑΠΑ που εβγαλα απο το β ερωτημα και αν καταληγω και στις 2 περιπτωσεις σε τελικη κατασταση τοτε ειναι ισοδυναμες?

[nvog1993]

Καλημέρα,
έχει δει κανείς το ερώτημα β του 2ου θέματος Σεπτ15;

Yποψιάζομαι πως η γραμματική είναι ΣΑΦΗΣ αλλα δεν ξέρω πως να το αποδείξω.
Κάθε βοήθεια ευπρόσδεκτη,ευχαριστώ.

edit :
Mαλλον ΑΣΑΦΗΣ είναι.Βασίζομαι στην υπόθεση ότι το +ab μπορεί να προέλθει είτε από +SX είτε από +XS τα οποία έρχονται από +SS.
Σωστά;

Δεν νομίζω, γιατί αν κάνεις το δέντρο πάλι και τα δύο S πρέπει να καταλήξουν σε Χ σε κάποια φάση. Το ότι η γραμμή από το S μέχρι το Χ θα είναι μεγαλύτερη μια στο ένα S, μια στο άλλο, δεν έχει σημασία. Πάλι το ίδιο δέντρο θα έχεις. Πιστεύω είναι ΣΑΦΗΣ αλλά το πως το αποδεικνύεις, δεν έχω ίδεα :/

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

Καλημέρα,
έχει δει κανείς το ερώτημα β του 2ου θέματος Σεπτ15;

Yποψιάζομαι πως η γραμματική είναι ΣΑΦΗΣ αλλα δεν ξέρω πως να το αποδείξω.
Κάθε βοήθεια ευπρόσδεκτη,ευχαριστώ.

edit :
Mαλλον ΑΣΑΦΗΣ είναι.Βασίζομαι στην υπόθεση ότι το +ab μπορεί να προέλθει είτε από +SX είτε από +XS τα οποία έρχονται από +SS.
Σωστά;

Δεν νομίζω, γιατί αν κάνεις το δέντρο πάλι και τα δύο S πρέπει να καταλήξουν σε Χ σε κάποια φάση. Το ότι η γραμμή από το S μέχρι το Χ θα είναι μεγαλύτερη μια στο ένα S, μια στο άλλο, δεν έχει σημασία. Πάλι το ίδιο δέντρο θα έχεις. Πιστεύω είναι ΣΑΦΗΣ αλλά το πως το αποδεικνύεις, δεν έχω ίδεα :/

To σκέφτομαι όπως στην σελ.177(lewis-παπαδημητρίου).Εκεί φαίνεται να έχει σημασία η σειρά των αλλαγών δεξιά αριστερά.Ας δώσει και κάποιος άλλος τα φώτα του.

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

Επιπλεόν απ'ότι βλέπω σε άλλα τοπικ'σ φαίνεται να τους έχει δώσει κάποια διόρθωση στο θέμα αυτό.Αναμένουμε αν κάποιος που το έδωσε θυμάται.

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

Καλημέρα,
έχει δει κανείς το ερώτημα β του 2ου θέματος Σεπτ15;

Yποψιάζομαι πως η γραμματική είναι ΣΑΦΗΣ αλλα δεν ξέρω πως να το αποδείξω.
Κάθε βοήθεια ευπρόσδεκτη,ευχαριστώ.

edit :
Mαλλον ΑΣΑΦΗΣ είναι.Βασίζομαι στην υπόθεση ότι το +ab μπορεί να προέλθει είτε από +SX είτε από +XS τα οποία έρχονται από +SS.
Σωστά;

Δεν νομίζω, γιατί αν κάνεις το δέντρο πάλι και τα δύο S πρέπει να καταλήξουν σε Χ σε κάποια φάση. Το ότι η γραμμή από το S μέχρι το Χ θα είναι μεγαλύτερη μια στο ένα S, μια στο άλλο, δεν έχει σημασία. Πάλι το ίδιο δέντρο θα έχεις. Πιστεύω είναι ΣΑΦΗΣ αλλά το πως το αποδεικνύεις, δεν έχω ίδεα :/

To σκέφτομαι όπως στην σελ.177(lewis-παπαδημητρίου).Εκεί φαίνεται να έχει σημασία η σειρά των αλλαγών δεξιά αριστερά.Ας δώσει και κάποιος άλλος τα φώτα του.

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

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

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

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

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

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

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

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

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

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

[greekoo]

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

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

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

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

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

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

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