THMMY.gr

Αξιζει να διαβασουμε καθολου το βιβλιο η μονο τις διαφανειες του Ντελο?

οι διαφανειες ειναι ακριβως οτι εχει οτι βιβλιο..
αλλα το βιβλιο τα αναλυει οποτε ενα περασμα καλο το χρειαζεται σιγουρα.. (προσωπικη αποψη  :P)

Θενξ!

Γενικα τι να προσεξουμε;
Απο ασκησεις κλπ εχει τιποτα ή παμε έτσι;
ποσες μερες πιστευετε ειναι αρκετες για να βγει?  :-\

Εγώ θα προτεινα να δειτε το βιβλιο αρχικα και να λυσετε καμια ασκηση απο κει. Γενικα εμένα ήταν μαθημα που μαρεσε, αλλα με ζορισε. Πιστεύω θελει αρκετές μέρες, ειδικά αν δεν το έχετε ανοίξει μέχρι τώρα.

^funny^
Τρολλαρεις? :P

Διαβασα το βιβλιο αλλα γενικα δε θελει και πολυ παιδεμα,
αμα σκαλωνεις καπου και νιωθεις να μπουχτιζεις πας παρακατω κι ας μη καταλαβες.
Οι διαφανειες του Ντελοπουλου καλες,
καποια πραματακια θα τα βρεις πιο γρηγορα μεσα απο αυτες στις εξετασεις,
καποια θεματα βεβαια υπαρχουν σε πολυ παρομοια παραδειγματα λυμμενα στο βιβλιο.
Ασκησεις βιβλιου, τις αλυτες παντα, εγω λεω πως δε χρειαζεται να λυσεις ουτε μιση.
Σε 4 μερες διαβασμα και παλια θεματα βγαινει ανετοτατα.

Δωστο πρωτα ρε μαλακα και μετα πεστηνα στο παιδι. Τι σαι συ ναουμε.

Επιχειρω να λυσω Θεμα 1 Φλεβαρη 2008 και σκεφτομαι πολλα και διαφορα αλλα νομιζω οτι ειναι ολα χαζομαρες.
Παραδειγμα σκεψης:
α) Δεν ειναι, γιατι αν τη γραψουμε σαν xyz μπλα μπλα μπλα, για yⁱ όπου το i θα παρει π.χ. την τιμη 6, το xyⁱz δε θα ανηκει στην L αφου θα χει μηκος παραπανω απο 5.
Μαλακια; :???: :D

Γενικα λυστε μου αυτο το θεμα please :P

επειδη κ εγω σκαλωσα εκει.. σκεφτηκα τον ορισμο οτι μια γλωσσα ειναι κανονικη αν κ μονο αν υλοποιειται απο πεπερασμενο αυτοματο, οποτε βρισκοντας ενα το λυνεις.
ας μας δωσει τα φωτα του κ κανενας παλιος, θα ναι καλυτερα..

εχω μαζεψει καμποσο χυμα υλικο για ΘΥΑ, κυριως για γλωσσες/αυτοματα
οποιος ενδιαφερεται μπορει να αφησει ενα mail εδω και θα τα στειλω το βραδυ.

εχει κανεις πιο προσφατα παλια θεματα?

οχι

Απλυτος θα μοιραστείς τη γνώση μαζί μου? ;)
μειλ thanasis43@windowslive.com

επιτρεπονται ανοιχτα βιβλια σημειωσεισ??

Στείλε και σε μένα βρωμιάρη

γιεπ!


άπλυτε εγώ σου έστειλα στο φβ  :P

Εστειλα τα email. Αν δεν εφτασε σε καποιον ας το πει :P

Παιζει κανενας να ανεβασει κανα λυμμενο θεμα τωρα;


ΧΡΙΣΤΙΝΑ, ΔΙΑΛΕΓΩ ΕΣΕΝΑ!
(http://media.tumblr.com/tumblr_l04kd2xjcM1qacoyu.jpg)

Xαχαχαχαχα λολλ!

Απλυτε ευχαριστώ! ;)

Έχει κανείς ιδέα πως λύνεται το δεύτερο θέμα απο τις εξετάσεις του Φεβρουαρίου 2009?

Προσπαθώ να το λύσω... Αν υποθέσουμε οτι το αλφάβητο V={a, ( , ) , + , - , * , / } και το σύνολο των τερματικών είναι Σ{ α}  τότε για κάθε Α που είναι στο V-Σ
δηλαδή για Α={ ( , ) , + , - , * , / } πρέπει να γράψουμε κανόνες τις μορφης Α->u όπου u=V ??? Επίσης ως αρχικό σύμβολο από το Α μπορούμε να θεωρήσουμε μόνο την (
ετσι δεν είναι??

Τωρα εσυ λες για το 3ο θεμα. εγω παντως οταν το δα θεωρησα κ οι πραξεις αποτελουν τερματικα.. δλδ σαν το παραδειγμα 3.13 του βιβλιου.

Ναι όντως μπερδευτηκα.Δηλαδή τους κανόνες πως τους έβγαλες? Αν δεν σου είναι κόπος να τους γράψεις γιατι έχω μπερδευτεί..

Όσο για το 2ο αν πάρουμε το θεώρημα 2.4.1 βάζοντας ως γλώσσα την α^(i+1)*b^i και w=α^(n+1)*b^n τότε για y=α^i έχουμε xz=a^(n-i+1)b^n που δεν ανήκει στην L αφού το n-i+1<n

οι πραξεις αποτελουν τερματικα συμβολα, γιατι αν δεν αποτελουσαν τοτε η συμβολοσειρα του ερωτηματος β πρεπει να αποτελειται μονο απο α (γιατι αν τα +,-,*,/,(,) ηταν μη τερματικα τοτε θα ηθελαν αντικατασταση)... δεν νομιζω να ειναι απαραιτητο το αρχικο συμβολο να ειναι το " S-> ( " μπορει να ειναι και το " S->(S) "... Δεν νομιζω να υπαρχει μια σωστη γραμματικη...

Για παραδειγμα εγω χρησιμοποιησα τους κανονες:
S->aSa | + | - | * | / | e | Sa | aS | a | SS

και ενα παραδειγμα υπολογισμου της (((α+α)*α)/α) ειναι:
S->(S) -> (SS) -> ((S)S) -> ((SS)S) -> (((S)S)S) -> (((aSa)S)S) -> (((aSa)S)SS) -> (((aSa)SS)S) -> (((aSa)SS)SS) -> (((a+a)SS)SS) -> (((a+a)*S)SS) ->(((a+a)*a)SS) ->(((a+a)*a)/S) -> (((a+a)*a)/a)

edit: και για το γ ερωτημα: D1 < D2

D1 : S->(S) -> (SS) -> ((S)S) -> ((SS)S) -> (((S)S)S) -> (((aSa)S)S) -> (((aSa)S)SS) -> (((aSa)SS)S) -> (((aSa)SS)SS) -> (((a+a)SS)SS) -> (((a+a)*S)SS) ->(((a+a)*a)SS) ->(((a+a)*a)/S) -> (((a+a)*a)/a)

D2 : S->(S) -> (SS) -> ((S)S) -> ((SS)S) -> (((S)S)S) -> (((S)S)SS) -> (((aSa)S)SS) -> (((aSa)SS)S) -> (((aSa)SS)SS) -> (((a+a)SS)SS) -> (((a+a)*S)SS) ->(((a+a)*a)SS) ->(((a+a)*a)/S) -> (((a+a)*a)/a)

υπαρχει κανεις που να ξερει πως λυνεται το θεμα 2 Φεβ_2009 και θεμα 1 Φεβ_2008... Δεν μπορω να καταλαβω πως θελει να διαπυστωσουμε αν μια γλωσσα ειναι κανονικη...
Μονο αν ξερουμε μια κανονικη εκφραση που να την περιγραφει ή ενα πεπερασμενο αυτοματο που να την αποδεχεται... Δηλαδη θελει να φτιαξουμε ενα απο τα δυο.
Το να φτιαξω μια τυχαια κανονικη εφραση που να περιγραφει καθε φορα την ιδιοτητα Ρ δεν ειναι δυσκολο, αλλα ειναι σωστο?

Χρησιμοποιήσες και τον κανόνα S->(S) φανταζομαι...ωραία αλλά πως ακριβώς τους σκέφτηκες αυτούς τους κανόνες? Εμπειρικα γιατι οι πραξεις είναι της μορφής αSa??

ναι χρησιμοποιησα και τον κανονα S->(S) απλως ξεχασα να τον γραψω... Δεν αναφερει τιποτα περιορισμους για τους κανονες ετσι εφτιαξα μερικους και οσους χρειαζομουνα στην πορεια τους προσθετα. Δεν αναφερει πουθενα οτι πρεπει να βρω τους ελαχιστους κανονες... Δεν ξερω αμα ειναι σωστο...
Οι πραξεις ειναι της μορφης aSa για τις πραξεις που ειναι στην παρενθεση την πρωτη (α+α)... θα εχεις σε πολλες παραστασεις αυτη την μορφη...
Ο κανονας  S->Sa ειναι για τις παραστασεις οπως αυτη (((α+α)*α)/α)... αλλα αν ειχαμε ((α*(α+α))/α) τοτε ειναι ο κανονας S ->aS
Μπορει να μην χρειαζονται ολοι, αλλα νομιζω μπορεις να παρεις οσους θες χωρις να ειμαι σιγουρος

Νομιζω οτι με αυτους τους κανονες ειναι καλυμμενες ολες οι περιπτωσεις παραστασεων που μπορεις να εχεις

Στο πρωτο θεμα 2009 η λυση ειναι οτι το αυτοματο που θα φτιαξουμε ειναι το (Μ1ενωση με το Μ2) και παραθεση με το Μ3*?

edit: μονο αυτο θελει ή πρεπει να το αναλυσουμε πιο πολυ, δηλαδη να βρουμε και τα Δ,F,K,s καθε πραξης?

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

Το θέμα 4 του 2009 το εχεις κοιταξει?

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

οταν ξεκιναει η μηχανη το πρωτο R (που δεν εχει κουτακι κατω δεξια) μετακινει την κεφαλη μια θεση δεξια, τοτε ελεγχει αμα στην θεση αυτη υπαρχει κενο, αν δεν υπαρχει τοτε πηγαινει παλι μια θεση δεξια και κανει παλι το ιδιο και κινειται παλι μια θεση δεξια, οποτε τωρα βρισκεται στην εντολη R (που εχει κουτακι κατω δεξια) και σημαινει να παει στο πρωτο κενο που θα βρει απο δεξια... εκει θα γραψει το α(δηλαδη τον χαρακτηρα που βρηκε στην αρχη, οχι αναγκαστηκα α), και θα παει στην επομενη εντολη που ειναι  R (που εχει κουτακι κατω δεξια) και θα κινηθει παλι μια θεση δεξια και θα γραψει το β δηλαδη το δευτερο γραμμα που διαβασε...

παραδειγμα ταινιας:
>_dfrefgg_ η κεφαλη ειναι στο πρωτο κενο, η μηχανη θα κινηθει δεξια μια θεση και θα βρει το d (που το αποθηκευει στην μεταβλητη a), στην συνεχεια θα μετακινηθει δεξια και θα αντιγραψει στην μεταβλητη b το f, και θα παει στο πρωτο κενο απο δεξια και θα γραψει d και στο δευτερο f οποτε η ταινια μετα θα ειναι   >_dfrefggdf_

το R χωρις κουτακι δεξια σημαινει μονο μετακινηση δεξια, ενω με κουτακι, πηγαινε στο πρωτο κενο χαρακτηρα που θα βρεις...
δεν ξερω ομως αν μπορει στην w να περιεχει κενα...γιατι αν το πρωτο γραμμα ειναι κενο τοτε η μηχανη σταματαει... ολα αυτα τα βρηκα στο βιβλιο σελιδα 252 - 254

Συμφωνα με το παράδειγμα 4.1.8 η w περιεχει μόνο μη κενα συμβολα αλλά μπορεί να είναι κενή. Αν υποθέσουμε οτι δεν ειναι κενή τότε θα πάει μια θέση δεξία αι τώρα η κεφαλή θα διαβάζει το w. Εφόσον το w δεν είναι κενό θα πάει άλλη μια θέση δεξια μέσα στη w. αλλα εμείς δεν ξέρουμε το μηκος της w για να δούμε αν θα συνεχίσει. Πρέπει να πάρουμε περιπτώσεις?

οταν κοιταξει στην πρωτη θεση της w (συμφωνα) με την α != _ το τε θα προχωρησει παρακατω, αμα η w εχει μηκος 1 τοτε στην δευτερη συνθηκη b != _ τοτε θα βρει κενο και θα σταματησει μονο αν τα δυο πρωτα γραμματα ειναι μη κενα θα συνεχησει... δεν μας ενδιαφερει ποσα γραμματα εχει η w, αρκει να ειναι >= του 2

Αν ειναι κενη τοτε θα σταματησει αμεσως
Αν εχει ενα γραμμα θα το διαβασει αλλα μετα θα σταματησει
Αν εχει δυο γραμματα τοτε θα τα διαβασει και θα παει στο τελευταιο κενο και θα τα γραψει το ενα μετα το αλλο
Αν εχει περισσοτερα του δυο τοτε θα διαβασει τα δυο πρωτα και θα παει στο τελευταιο κενο και θα τα γραψει το ενα μετα το αλλο

Εχει κανεις ιδεα για το 2ο θεμα του 2009
αν η L=[w/w ε (0,1)*,w εχει περισσοτερα 1 απο οτι 0] ειναι κανονικη
εγω το λυνω καπως μπακαλιστικα ..πρεπει να υπαρχει λυση χρησιμοποιωντας κλειστοτητα

Λυση απο το μαθημα: Λες οτι για να ειναι κανονικη πρεπει να την αποδεχεται καποιο ΠΑ. Για την απαριθμηση ομως των 0 κ 1 επρεπε να υπαρχει ενα balance. Αυτο απαιτει μια κατασταση για καθε τιμη, αρα απειρες καταστασεις. Ατοπο, η γλωσσα δεν ειναι κανονικη. (Θ. Αντλησης)

ναι ωραια για το συγκεκριμενο παραδειγμα γινεται οπως λες, το εχει και στο βιβλιο σελιδα 128 (για την γλωσσα a^nb^n)... Το θεμα 1 2008 πως λυνεται?

Ευχαριστώ!!!
εψαχνα λυση τύπου
 Ν.δ.ο. L = {w ∈ {0, 1}*: w έχει ίδιο αριθμό 0 και 1}
δεν είναι κανονική.
 L ∩ 0*1* = { 0n 1n : n ≥ 0}, που δεν είναι κανονική.
 0*1* κανονική.
Κανονικές γλώσσες κλειστές ως προς τομή.
Άρα L δεν είναι κανονική.

Τι κανει η μηχανη Τuring στο 4ο θεμα του 2009?
(Μη μου πειτε καλα ειναι :P)

αντιγραφεις τα 2 πρωτα συμβολα στο τελος της w.
η w δεν πρεπει να εχει κενα στην αρχη, ομως αυτο πρεπει να ισχυει εξ ορισμου ετσι κι αλλιως.

Eυχαριστω!

Στο πρωτο του 11 τι θα κανουμε για να βρουμε την G'?

σελιδα 14 σημειώσεων

Στο θέμα με τα αυτόματα όταν κατασκευάζουμε μη αιτιοκρατικό πρέπει να βάλουμε και ίδιες μεταβάσεις? Δηλαδή όταν διαβάσει b να πάει σε μια κατάσταση q1 μη τελική η σε μια q4 τελική?

Και στο αιτιοκρατικό πρέπει απλά να συμπεριλάβουμε όλες τις πιθανές μεταβάσεις χωρίς να έχουμε διπλές?

εχει λυσει κανενας το θεμα 2 του 2008 με την KMC??

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

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

Δεν ξέρω αν είναι απόλυτα σωστο αλλά κατέληξα σε 4 κανόνες: S->XS1 ,S1->SX, S1->X S->X, X->ab και με δυναμικο προγραματισμό έβγαλα οτι η συμβολοσειρα δεν μπορει να βγαίνει απο τους παραπάνω κανόνες.

Δηλαδή σε ένα ΜΑΠΑ αρκεί να βάλω τις μεταβάσεις που θέλω για τη δοσμένη συμβολοσειρά?? Δηλαδη απο την q0 διαβάζοντας b  να καταλήγει σε τερματική q1 και διαβάζοντας α ή b να παραμένει στην q0??(για το θέμα του 2011)

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

στο θέμα του 2011 η συμβολοσειρά που θα ανήκει στη γλώσσα θα έχει οσεσδήποτε παραθέσεις του α ή οσεσδήποτε παραθέσεις του β. δεν πρόκειται σ' αυτήν τη γλώσσα να συναντήσεις συμβολοσειρά που να έχει και α και β. οπότε από την αρχική κατάσταση q0 με α πας στην q1 η οποία έχει βρόχο που με α πηγαίνει στον εαυτό της. με β πας στην q2 που επίσης έχει βρόχο για τον εαυτό της. όλες οι καταστάσεις είναι τελικές.

Aυτο που καναμε στην ταξη?
Παντως δε νομιζω να βαλει...


Το πρωτο του 11??

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

Δεν θα βαλει λεω εγω :P
Εγω ομως μιλαω συγκεκριμενα για το 1α του 2011 :D

για το 1  του 2011 η G' θα έχει τα ίδαι τερματικά, τα ίδια μη τερματικά συν ένα s', αρχική κατάσταση s' και τους ίδιους κανόνες με την G μαζί με έναν καινούριο, τον S'->SS . Aν παρατηρήσεις τη γραμματική σου είναι σε ΚΜC Άρα κάνεις κατευθείαν έλεγχο με πίνακα.

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

δες λιγο σελιδα 208 στο βιβλιο.

το παραδειγμα 3.6.1 τα λεει πολυ ξεκαθαρα

αυτο γιατι?

σορρυ κιολας αλλα παλι στο 1/2011 οι κάθετοι ( | ) τι είναι?

ωραία. λέει στην 209 διαγράφω απο τη γραμματικη τους κενους κανονες και διαγραφει τον S->e) . αυτός γιατί θεωρείται κενός??? κενοι κανονες είναι της μορφης Α->ε αν δεν κανω λαθος...

οι καθετοι διαχωριζουν τους κανονες αν αυτο εννοεις. πχ καν1|καν2|καν3

η παρένθεση ειναι η κανονικη παρένθεση οπως την ξερεις..διαγραφει την S->e

xm.. νομιζω οτι τα κομματα διαχωριζουν τους κανονες.. S->AB|ab, A-> ...

δλδ ειναι σαν να έχουμε S->AB ,S->ab ???

κανονες αντικαταστασης εννοουσα. δηλαδη το Σ αντικαθισταται είτε από τα ΑΒ είτε τα αβ.

Ειναι κενος μιας και απο S σου δίνει e, που είναι το κενο συμβολο.

a kool auto symperana ki ego, thanx!

Οι κενοί κανόνες είναι εξ ορισμού οι κανόνες τύπου A ->e, όπου Α ένα μη τερματικό σύμβολο ( το λέει και στις σημειώσεις, 3η σενότητα, σελίδα 15).

Ευχαριστω edenaxa(s)!

άρα δηλαδή δεν ισχύει αυτό που λέει στο βιβλίο ότι ο Σ->ε) είναι κενός.  :D


βαγγέλη νομίζω ότι το κατάλαβα (αλλά μάλλον μπέρδεψα τους υπόλοιπους  :P ). θενκς!!!

στο βιβλιο λεει"(ο μονος που υπαρχει ειναι ο S->e) η παρενθεση δεν ειναι απο τον κανονα σωστα ειναι στο βιβλιο

interesting... thanks και γι'αυτο.

πειτε λιγο στα γρηγορα :)

1. a*b* "τομή" b*c* = O Σ/Λ
2. b*a* "τομη" a*b* = a* "ενωση" b* Σ/Λ
3. a* "τομή" a*b* = e Σ/Λ
4. a* "τομή" b* = O Σ/Λ

και πανω κατω τη λογική

 
εγω το καταλαβαινω ως εξης
οταν θες να διαγραψεις τους κανονες προς το κενο
1) βρισκεις ποιες καταστασεις με ενα ή περισσότερα βήματα οδηγούν στο e π.χ Α και S
2)αυτες τισ καταστασεις τις κρατας σε ενα συνολο για να θυμασαι εστω π.χ.Ε=[Α,S]
3)διαγραφεις ολους τους κανονες προς το κενό
4)παιρνεις ενα ενα τα στοιχεία του Ε και ελέγχεις αν στους κανόνες που εμειναν υπάρχουν σε κάποιο δεξί μέρος(με 2 γραμματα)
αν ναι τότε για αυτόν τον κανόνα θα προσθέσεις τον ίδιο χωρίς αυτό το σύμβολο αυτό π.χ. αν εχεις Β->ΑC θα προσθέσεις
τον Β->C χωρίς δηλ. το Α που ειναι στο συνολο Ε
ελπιζω να βοηθησα ;)

1 κ 4 ειναι Λ γιατι ειναι Σ το 3
αν δεν παρεις τπτ απο τα * θα εχεις και στις δυο μεριες e που δεν ειναι το κενο συνολο

Για το 2
το πρωτο συνολο το βγαζω {e,b,bb,a,aa,ba,bba,baa...}
το δευτερο                         {e,a,aa,b,bb,ab,aab,a,...}
αρα για σωστο μου φαινεται

σωστος. αλλα οταν εχεις Β->ΑC και Α και C ανηκουν στο Ε ποιο απο 2 προσθετεις Β->Α ή B->C ????

ομως a* "τομη" a* δεν ειναι e, παλι λαθος δεν ειναι?

Μονο αυτο με προβληματιζε...βασικα για το 2 ειναι αυτο?

μηπως ολα ειναι Λ?

Tωρα που το βλεπω ναι και το 3 Λ ειναι

Το 2 λέω ότι είναι σωστό.

σωστη ερωτηση...εγω θα τους εγραφα και τους δυο γιατι τυπικα μια φορα θα εξετασεις τον κανονα για Α και μια για C
και πιθανον να προεκυπτε καποιος κανονας που μπορει να παραληφθει ή ταυτοσημος με αλλον ...λεω τωρα

για το 2, εαν ισχυει ο κανονας για * θα ισχυει και για 1, αρα ab "τομη" ba = a U b <=> O = a U b λαθος.

Και για πειτε.. στο 1ο θεμα, ποια γλωσσα ηταν γιατι εγω κατεληξα σε ενα παραλογο αποτελεσμα..  :-\

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

1 ελαχιστη κατασταση..

με τον αλγοριθμο βρηκα 4, crap...

Γενικα δεν ηταν και τα πιο ευκολα...

Στο itc σας περαστηκε?

Oχι.

Ασχολείται  κανείς με θυα?? Δεν μπορώ ΝΑ καταλάβω την έννοια της κλειστοτητας. Αν εχω πχ. Ro={(a,b),(b,a),(a,c),(d,b),(c,c)}=A ποιο είναι το κλείσιμο του Α;;;


Δηλαδή αν δεν μας ορίζει ποια σχέση R εννοεί  ότι εμεις θα παίρνουμε και την μεταβατική και την ανακλαστικη κλπ...??

μιλάμε για ανακλαστική μεταβατική κλειστότητα

είναι εύκολο να τη βρεις αν κατασκευάσεις το κατευθυνόμενο γράφημα που παριστάνει τη σχέση σου. Καταρχήν πρέπει να προσθέσεις όλες τις μεταβάσεις από τις κορυφές στον εαυτό τους. Επίσης θα προσθέσεις μια ακμή από μια κορυφή σε άλλη  όταν αυτή δεν υπάρχει στην  σχέση, αλλά υπάρχει ένα μονοπάτι που τις συνδέει.

Η ανακλαστική μεταβατική κλειστότητα  της Ro είναι η Ro U {(a,a),(b,b),(d,d),(d,a),(d,c)}

*Κατασκευάζοντας το γράφημα θα προσέξεις ότι τη σύνδεση (d,c) προέκυψε αφού πρώτα δημιουργήθηκε η (d,a), προσθέτοντας δηλαδή ακμές στο γράφημα της ανακλαστικής μεταβατικής κλειστότητας μπορεί να δημιουργούνται καινούρια μονοπάτια.

ok. φαντάζομαι κάπου ξέχασες και το (b,c) . Σε ευχαριστώ ;)

όταν δίνει έναν γράφο για πεπερασμένο αυτόματο και λέει βρείτε την κανονική έκφραση που παραγει τη γλωσσα L(M)..?Τι κανουμε??είναι και σε παλιό θεμα..
(εσυ *** μου φαινεται θα ξερεις   8)) :P )

π.χ. στο 3ο θεμα Σεπτεμβρη 2002 θελει
aa(ab U aba)*

ή στο 2ο θεμα Γεναρη 2002 θελει
(ab) U (aa(ba)*bb)

καλα τα λεω ε; :D
εχω λυσει πολλα παλια θεματα, αφηστε ενα μαιλ εδω ή σε κανα pm να σας τα στειλω το απογευμα-βραδυ κατα τις 8-9++
που θα ευκαιρω γιατι τωρα θελω να διαβασω και να τα τσεκαρω και να λυσω και τα θεματα του Φλεβαρη και να λυσω καποιες αποριες.

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

Αλλά εγώ (όπως και η Αιμιλία φαντάζομαι) το κάνω με το μάτι. Λίγη παρατηρητικότητα απαιτεί.


Καλά νομίζω τα βρήκες. Αλλά για σιγουριά θα σου απαντήσω αργότερα όταν κάνω επανάληψη τα θέματα.

Αχ αυτο το 2β το φλεβαρη με τον δυναμικο προγραμματισμο :P

αν μπορειτε ρωτηστε ποτε θα βγουν ΨΕΕ κ γραφικη :D

συμφωνώ με την christinette. Δες στο βιβλίο σελ. 119 το παράδειγμα, μόνο το σχήμα 2.16. Αυτό που μπορείς να κάνεις σε γενικές γραμμές είναι να απομονώσεις τις καταστάσεις που οδηγούν σε τελικές και να δεις με ποιες εκφράσεις μπορούν να σε οδηγήσουν οι άλλες καταστάσεις σε αυτές. ένα χρήσιμο στοιχείο είναι ότι όπου υπάρχει κύκλος στο γράφο θα πάρεις έκφραση με *.
Στόχος είναι να μείνουν δυο καταστάσεις το πολύ και θα φαίνεται η κανονική έκφραση.

όντως....

Ευχαριστω παααρα πολυ παιδια  :)

στο σχήμα φαίνεται πως δέχεται και το e άρα δεν ξεκινάει πάντα με αα


και το θέμα 3 από 01/02 το είχε λύσει στην τάξη (2010) και το έβγαλε ((ab)U(aba))*

εχεις δικιο

Πώς μπορεί να είναι αυτό σωστό; Αφού τότε η συμβολοσειρά ab θα ανήκε στη γλώσσα. Δε μου φαίνεται ότι αυτό το αυτόματο μπορεί να την αποδεχτεί.

το ab το δέχεται το πα αφού η q3 είναι τελική. Μήπως μπερδεύτηκες και βλέπεις του Σεπτεμβ 2002? Μοιάζουν πολύ ;)

σταματα να διαβαζεις το μαθημα. να ξελαμπικαρεις :P
οσο περισσοτερο το διαβαζουμε τοσο χειροτερα γραφουμε :D :D :D

!! αυτό είναι κάτι παραπάνω από σίγουρο !!

χαχα οκ! νομίζα λέγατε για το ίδιο θέμα του σεπτέμβρη

Από ethmmy...

Αναβολή μαθήματος Τετάρτης 17.10.11
16 Οκτ 2012 12:42 μμ
Ντελόπουλος

Δυστυχώς, για σοβαρούς προσωπικούς λόγους το μάθημα της Τετάρτης 17.10.11 δεν θα πραγματοποιηθεί.
Παρακαλώ ενημερώστε και τους συναδέλφους σας.

παιδες μια απορια!
Στο πινακακι που κανουμε για το δυναμικο προγραμματισμο, στα παλια θεματα που επιχειρησα να λυσω, σε καποια κουτακια μου βγαιναν 2 αποτελεσματα.. Τι εννοω μ αυτο:
πχ το πρωτο κουτακι της σειρας του κουτιου στο οποιο υπολογιζα ειχε την τιμη α. Και το απο πανω την τιμη β. Οποτε βασει θεωριας αφου πχ ειχα μια σχεση πχ Β->αβ, Θα πρεπει στο κουτακι να βαλω Β.. αλλα αντι να μου προκυπτει μονο αυτο το Β, καθως συνεχιζα διαδοχικα τους ελεγχους ειχα πχ και αλλα δεκτα αποτελεσματα.. Οποτε ειχα και μια αλλη τιμη Α πχ στο συγκεκριμενο κουτακι. Σ αυτη την περιπτωση που εχω πχ και Α και Β ως υποψηφιες τιμες του κουτιου τι κανω? κοιταω μηπως υπαρχει πχ καποιος αλλος κανονας που να λεει για παραδειγμα S-> AB ? Oποτε βαζω στο κουτακι το S? η κατι αλλο? ελπιζω να μην σας μπερδεψα πολυ 

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

δεν νομιζω ρε μαν γιατι ειναι σε παλιοτερο θεμα οπου σου εδινε τους κανονες ετοιμους..
δοκιμασε το κ εσυ σαν εξασκηση και πες μου τι εβγαλες (γιατι πιστευω οτι κατα 99% θα βαλει τετοιο θεμα).. ειναι στο θεμα 2 του γεναρη του 2012

και γω την εχω αυτή την απορία αν και σε όσα θέματα έλυσα δεν μου έτυχε ποτέ. Δηλαδή αν στις διαφάνειες του καθηγητή, στο τρίτο pdf σελίδα 21, πάνω, εκεί που έχει τις κουκκίδες

• υπάρχει ο S->(S₁

.
.

• δεν υπαρχει

.
.

• αντι για δεν υπαρχει, υπήρχε κάτι

θα κρατούσαμε το τελευταίο λογικά σύμφωνα με τον αλγόριθμο, σωστά?

Και τα 2 τα βάζεις.. στο κουτάκι μπορεί προφανώς να προκύψουν παραπάνω απο ένας κανόνες.

αν προσέξεις, λέει πως στο κουτάκι βάζουμε το σύνολο των κανόνων

PS. Βλέπω να τον πίνουμε αύριο  ;D

θενξ για την βοηθεια παιδες!
μπα αμφιβαλλω να βαλει δυσκολα.. και τα περσινα πτυχιακης του 2012 ηταν αρκετα ευκολα, και σημερα στα πολυμεσα επιανες αρκετα ευκολα το 5-6

οκ τα βάζουμε και τα δυο στο κουτάκι.. Ας υποθέσουμε ότι έχουμε στο κουτάκι Α και Β. Αυτό θα μετράει σαν ΑΒ? Δηλαδή αν όπως στο παράδειγμα των pdf που έγραψα παραπάνω έχουμε στο Ν(4,4) το ΑΒ και στο Ν(5,7) το Β θα πρέπει να έχω κανόνα π.χ. S->ABB αλλιώς θα βάλω κενό στο Ν(4,7)? Αυτός ο αλγόριθμος δεν είναι μόνο για ΚΜC? Αν πέσει κάτι τέτοιο θα παραδώσω κόλα με μπλε οθόνη

χωρίς να είμαι 100% σίγουρος.. μετράει σαν Α,Β οχι ΑΒ. δηλαδή αν έχεις στο ένα κουτάκι Α,Β και στο άλλο Β. κοιτάς αν υπάρχει κανόνας ΑΒ, ΒΒ..
αν είχες 2 στο καθένα θα κοιτούσες για 4 συνδυασμούς.

Απλά διαισθητικά απαντάω.. δεν το είδα πουθενά έτσι.

Στα θέματα του Σεπτεμβρίου 2002 στο θέμα 3.β αν γράψω (αα(αβ.ένωση.αβα)*)* σημαίνει ότι το αα μπορεί να μπει και ενδιάμεσα μιας συμβολοσειράς που δεν ισχύει άρα είναι λάθος. Αν το γράψω αα(αβ.ένωση.αβα)* σημαίνει ότι το αα θα πρέπει οπωσδήποτε να μπει στην αρχή της συμβολοσειράς που πάλι είναι λάθος... Εσείς πως θα το γράφατε?

Παιδιά πως λύνονται θέματα της μορφής:

"Δειξτε οτι αν οι γλώσσες L1, L2 είναι ανδρομικές τότε και μια άλλη γλώσσα L που προκύπτει από κάποια πράξη (π.χ. ένωση) μεταξύ τους είναι και αυτή αναδρομική "(Θέμα 3ο Φεβρ. 2013).

Επίσης, πως δειχνουμε το σοσ θέματάκι:

"Δείξτε πως κάθε κανονική γλώσσα είναι και αναδρομικά απαριθμήσιμη;"

Ωπ καλή φάση. Δε θυμάμαι τέτοια θέματα πριν από κανά 4ρι χρόνια που το 'χα δώσει. Anywayz, για να δείξεις ότι μια γλώσσα είναι αναδρομική αρκεί να κατασκευάσεις μια μηχανή Turing που την επιλύει. Αφού L1, L2 αναδρομικές υπάρχει μηχανή Turing για την κάθε μία. Γενικά ο μπούσουλας είναι πολύ απλός σε τέτοιες ασκήσεις. Στην περίπτωση της ένωσης παίρνεις μια L3 Turing μηχανή, η οποία "περιέχει" τις L1 και L2, την είσοδο της οποίας feedάρεις στις L1 και L2 και μετά OR τις εξόδους τους (το "ναι" ή "όχι"). Είναι προφανές πως τόσο η αναπαραγωγή μιας εισόδου w στις L1, L2 όσο και η OR στο τέλος είναι πραγματοποιήσιμες από μια μηχανή Turing. Αντίστοιχα για άλλες λογικές πράξεις.

Disclaimer: αυτά τα βγάζω από το κεφάλι μου. Μπορεί να μη γουστάρει τις λύσεις μου ο Ντελό ή να κάνει άλλα στο μάθημα :P

Για το δεύτερο δε σκέφτηκα κάτι πιο κομψό από το προφανές: για κανονική γλώσσα υπάρχει FSM που το αποφασίζει, το οποίο εύκολα μπορεί να μετατραπει σε απλή TM η οποία δε γράφει στη ταινία και σε κάθε μετάβαση προχωράει δεξιά μέχρι να συναντήσει κενό, όπου και τερματίζει. Η TM αποφασίζει τη γλώσσα, άρα είναι αναδρομική => αναδρομικά απαριθμήσιμη.

Σε ευχαριστώ πολύ!  :)
Μου φαινεται λογικό αυτό που λες καθώς με παρόμοιο τρόπο αποδεικνύει τα αντίστοιχα θεωρήματα στο βιβλίο για τις κανονικές γλώσσες.
Thanks και παλι.  ;)