THMMY.gr

Εγώ θα έλεγα ότι οι (i) και (iii) ανήκουν.

Μπορεί κάποιος να περιγράψει, με απλά λόγια, το τρίτο βήμα για την μετατροπή μιας γραμματικής σε κανονική μορφή Chomsky  (εξάλειψη κοντών κανόνων) ?? 

Δεν νομίζω πως μπορώ να εξηγήσω πιο απλά/σωστά σε σχέση με το πως το εξηγεί ο ίδιος ο Ντελόπουλος (σε 10 σειρές) στη σελίδα 17 από εδώ (http://alexander.ee.auth.gr:8083/eTHMMY/archive/89/downloadFile/989/771H-lecture-set3.v.3.pdf).

Διάβασε τη μεθοδολογία όπως την περιγράφει εκεί και αν έχεις κάποια απορία για αυτά που γράφει στη συγκεκριμένη σελίδα, feel free to ask.

βσκ δες και στο βιβλιο παπαδημητριου/lewis σελ 210 εχει ενα παραδειγμα σαν αυτο στις σημειωσεις απλα το επεξηγει γενικα

μπορεί να εξηγήσει κανεις το δυναμικό προγραμματισμό στη σελ 21 των διαφανειών;
δεν καταλαβαίνω ποτέ πρπει ν βαλουμε κενό κ ποτέ s...

+1

δες την ασκηση σελ 3 απο το πρωτο pdf Με σημειωσεις ασκησεων ντελο

Μπορεί κάποιος να εξηγήσει πως προκύπτουν οι κλάσεις ισοδυναμίας μιας γλώσσας διαφάνεια 17 pdf αυτομάτων???

χωρίς να είμαι σίγουρη

ν=0 Κ1=όλες οι τελικές καταστάσεις      Κ2=οι υπόλοιπες
ν=1  πας πρώτα στις εναπομείναντες: βλέπεις την επόμενη κατάσταση μέσω των α,β (πχ δ(q₂,a=q₅ )
       αυτές που για το ίδιο α ή για το ίδιο β τερματίζουν σε τελικές καταστάσεις και για το ίδιο α ή β δεν τερματίζουν σε τελ.καταστ. τις βάζεις μαζί (εδώ πχ οι q4,q6 για α τερματίζουν σε τελικές καταστάσεις και για β όχι ενώ για β η q2 επίσης σε τελική κατάσταση-άρα έχεις ενα ζευγάρι thn q4,q6 και οι άλλες 2 μόνες τους)
     για τις τελικές βλέπεις ότι για α ταυτίζονται επίσης άρα μένουν ως έχουν(ζευγαρακι δλδ)
ν=2 το μόνο που μπορείς να ελέγξεις είναι το q4,q6 που μένει ως έχει, άρα τελειώσαμε με τις ισοδύναμες

από τις ασκήσεςι που ανέβασε ο ετέρντιτι το 20 πδφ σελ 4 γιατί ο ισχυρισμός Τ->αβα είναι ψευδής;
γενικά αν έχουμε 2 εναλλακτικές για κάποιο σύμβολο σε μία(στην ίδια) σσ θα παίρνουμε πάντα τη 1 ή μπορούμε και εναλλάξ;
δλδ αν έχουμε χΤχ και χ->α/β μπορούμε να έχουμε αΤβ ή απαραίτητα μόνο αΤα ή βΤβ;

Γίνεται αυτό που λες (μπορείς να αντικαταστήσεις το πρώτο Χ με α και το δεύτερο με β), το πρόβλημα είναι ότι έτσι όπως το έχει γραμμένο στο .pdf υπονοεί οτί αυτό θα γίνει σε ένα βήμα (το βελάκι της συνεπαγωγής δεν έχει αστερίσκο που να υποδηλώνει πολλά βήματα), το οποίο δεν γίνεται.

αχαμ
οκ θένκιου  :-*

Γενικώς, το Ε(q_x) είναι το σύνολο των καταστάσεων (από τις αρχικές) που μπορείς να φτάσεις από την q_x με "e". Χωρίς να χρησιμοποιήσεις κανένα γράμμα δηλαδή.

Τώρα, ο Ντελόπουλος επέλεξε να ονομάζει τις καταστάσεις του νέου αυτομάτου (οι οποίες αποτελούνται από σύνολα των καταστάσεων του αρχικού ΜΑΠΑ) με Q_y. Το y προκύπτει από την δυαδική αναπαράσταση των καταστάσεων q_x που υπάρχουν στο σύνολο της κατάστασης Q_y. Στη συγκεκριμένη περίπτωση, πχ, είναι Ε(q₀) = {q₀,q₁} οπότε βάζει άσους στα αντίστοιχα ψηφία του δυαδικού αριθμού και προκύπτει 0011 = 3. Άρα το Q_y που αντιστοιχεί στο Ε(q₀) = {q₀,q₁} είναι το Q₃ = Q₀₀₁₁.

ty,δεν το έχω πλήρως αλλά κάτι κατάλαβα

υγ.διέγραψα καταλάθος την ερώτηση  :-[

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

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

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

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

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

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

κανενας; 

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

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

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

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

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

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

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

+1

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

αν πχ θελεις να δειξεις την μη κανονικοτητα της 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 (β)

+10

Το έλυσα στο άλλο τόπικ (https://www.thmmy.gr/smf/index.php?topic=1894.msg1070701#msg1070701).

έστω η κανονική έκφραση a(ab)*Ua και θέλουμε να βρούμε τρεις εκφράσεις και να κατασκευάοσυμε το ΜΑΠΑ
η φώτοου που επισυνάπτω είναι σωστή;
γενικά το (αβ)* είναι πολλές φορές το αβ ή α*β* ?
κι επίσης για το ΜΑΠΑ αν ικανοποιεί την κανονική έκφραση αλλά ικανοποιεί και άλλες εκφράσεις, είναι λάθος;

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

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

Τέλος πώς θα γίνει ένα ΜΑΠΑ να ικανοποιεί 2 κανονικές εκφράσεις;

Έχει καταλάβει κανείς με ποιο τρόπο λυνονται τέτοια Σ-Λ?
L[a*b]τομή L[ab*]={a,b}
L[b*c*]τομή L[a*b*]={}
L[b*a*]τομή L[a*b*]=L[a*ένωση b*]

Λ-Λ-Σ. Αφήνω την εξήγηση σε σένα!

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

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

Εφ'όσον οι γλώσσες είναι σύνολα, η τομή τους είναι οι λέξεις που ανήκουν και στις δύο γλώσσες. Λύνονται με αναλυτική σκέψη, δηλαδή (έστω για το πρώτο)

είναι λάθος, γιατί:
Η είναι μία γλώσσα που περιλαμβάνει 0 ή περισσότερα a ακολουθούμενα από ακριβώς 1 b, δηλαδή:
L1 = {b, ab, aab, aaab, ...}

Η είναι αντίστοιχα η
L2 = {a, ab, abb, abbb, ...}

Προφανώς όσο προσθέτουμε a στην L1 ή b στην L2 δεν θα βρούμε άλλο κοινό στοιχείο, άρα η τομή (κοινά στοιχεία) είναι μόνο το ab. Τα a, b δεν είναι κοινά στοιχεία.

Κατά πλήρη αντιστοιχία για τις υπόλοιπες - πρέπει να βρεις ή την ένωση, ή το αντιπαράδειγμα - πχ θα μπορούσα κατευθείαν να έχω πει, δεν ξέρω ποιό είναι το αποτέλεσμα, αλλά το b δεν ανήκει στην L2 και το a δεν ανήκει στην L1 άρα σίγουρα είναι λάθος, δεν μπορεί το {a, b} να είναι η τομή τους

What he said.

Νομίζω το ξεκαθάρισα. Ευχαριστώ  :)

Και μία τελευταία ερώτηση: Πώς δείχνουμε ότι κάθε κανονική γλώσσα είναι αναδρομικά απαριθμήσιμη; :)

Αν θυμάμαι καλά, αναδρομικά απαριθμήσιμες είναι οι γλώσσες για τις οποίες μία Μηχανή Turing μπορεί να αποφανθεί ότι μία λέξη ανήκει στη γλώσσα (αλλά δεν μπορεί να αποφανθεί απαραίτητα ότι μία λέξη δεν ανήκει). Σωστά θυμάμαι?


Αυτό που θα έκανα εγώ θα ήταν να εξηγήσω πώς μπορώ να φτιάξω μία μηχανή Turing που να αποδέχεται μία Κανονική Γλώσσα. Αν το αποδείξω αυτό, έχω τον εξής συλλογισμό:
-Οι ΚΓ γίνονται αποδεκτές από ΑΠΑ,
-Οι ΑΠΑ ανάγονται σε Turing οι οποίες αποδέχονται αναδρομικές γλώσσες, τότε
-κάθε ΚΓ είναι και αναδρομική γλώσσα.
-Οι αναδρομικές γλώσσες είναι υποσύνολο των αναδρομικά απαριθμήσιμων γλωσσών (αν ισχύει ο ορισμός που έδωσα, αλλά μπορεί και να μην ισχύει), και άρα qed

Σωστά θυμάσαι! Ευχαριστώ και πάλι

Μια απορία τελευταίας στιγμής στο 2ο θέμα του φεβρουαρίου 2015 πως δείχνουμε το κενό(οχι το e) στην μηχανή turing?

Νομίζω γράφεις απλά   >n

To ab ανήκει στη γλώσσα R=( (a ((ab)b)* ) U b* ) ??? Εγώ νομίζω πως ναι... αλλα στο pdf των ασκήσεων λέει όχι. Ξέρει μήπως κανείς την σωστή απάντηση???
 (askiseis2.pdf    σελ.4   17/12/14) 

Όντως δεν ανήκει. Πέρα από τα b, bb... στη γλώσσα ανήκουν τα a, aabb, aabbabb....

Περιγραφικα ειναι : ειτε βαζεις ενα α και μετα εναν οποιοδηποτε αριθμο απο abb ειτε εναν οποιονδηποτε αριθμο απο b.

Πάνω σε αυτο... Τι διαφορά έχει το a(a*∪b*)b από το a(a∪b)b ??

Το (a* U b*) είναι ευρύτερο: σου λέει πάρε όσα θες (0 ή παραπάνω) a, ή πάρε όσα θες (0 ή παραπάνω) b. Αντίθετα το a U b λέει πάρε ή 1 a ή ένα b ακριβώς. Άρα η 1η έκφραση βγάζει πχ τα

ab, aab, abb, aaab, abbb, aaaab, abbbb, ..., (άπειρα στοιχεία) ενώ η δεύτερη μόνο τα aab και abb.

Στο 2ο θέμα Ιούλιος 2015 στο β ερώτημα, πως μπορούμε να βρούμε την κανονική έκφραση;

Γινεται καποιος να δωσει μια λυση για τα α) και β) του θεματος 2 απο φλεβάρη 2015; Εχω κατι ιδεες αλλα δεν ειμαι και τοσο σιγουρος

Μάλλον θα έπρεπε να γράψεις κάτι σαν αυτό στη σελίδα 1 εδώ  (https://www.thmmy.gr/smf/index.php?action=tpmod;dl=item2560) :P

Στο θεμα 3ο η γλωσσα ειναι σε κανονικη Chomsky ε? (πειτε ναι, plz)

Αχά.

Το (α) τα απορρίπτει όλα (R-> n) και το (β) δέχεται μόνο το κενό.

(Υποθέτω ότι η ταινία αρχίζει, έχει ένα κενό και μετά την λέξη.

α) Η γλώσσα δεν περιέχει καμία συμβολοσειρά. Αφού η μηχανή πρέπει να απορρίπτει όσες συμβολοσειρές δεν ανήκουν στη γλώσσα, πρέπει να απορρίπτει όλες τις συμβολοσειρές, άρα να μην αποδέχεται καμία. Με στοιχειώδεις μηχανές:
>Ν (που Ν είναι η κατάσταση που λέει όχι). Μπορείς και >R -> N

β) Η γλώσσα περιέχει μόνο την κενή συμβολοσειρά, άρα πάμε 1 δεξιά, αν έχει οτιδήποτε πέρα από κενό απορρίπτουμε αλλιώς αποδεχόμαστε:

>R -(κενό)-> Υ
      |--->Ν

Νομίζω αυτά είναι σωστά, αν κάποιος διαφωνεί διορθώστε με

Θεμα 1 ιουνιου, δε θα επρεπε να με παιδευει τοσο πολυ ε?

 >:( >:( >:( >:( >:(

Εκτός αν κατάλαβα λάθος πρέπει να είναι:

(0*10*10*10*)U(0*110*10*)U(0*10*110*)U(0*1110*)

Edit: Μαλακία μου, το (0*10*10*10*) αρκεί.

Σωραιος, θενκς

Γιατί όχι απλά 0*10*10*10*;

Βασικά ναι ρε, δίκιο έχει ο L. Οτιδήποτε πέρα από το  0*10*10*10* είναι περιττό.

Ergo η 1 μοναδουλα για καλη αρχη

Πως αποδεικνύουμε οτι το σύνολο των αναδρομικά απαριθμήσιμων γλωσσών είναι κλειστό ως προς την Ένωση, την Παράθεση και το Kleene Star (Θέμα 3ο, Φεβ 2015)


Edit: Επίσης, το θέμα 1ο, Σεπτέμβρης 14, το ΑΠΑ είναι ελάχιστο ή όχι? Και πως το διαπιστώνουμε?

Επειδή σ'αγαπώ κι ας με μισείς

(τελικά οπότε (ab+aba)*)

Θεμα 3 Φλεβαρης '15, βρισκω οτι δεν την αποφασιζει γιατι εχω W στο 1,6
Σωστο?

Αυτο που δίναμε μαζι είναι???Σωστο! :P και τοτε τ ειχες βρει elelel

όταν μας ζητάει η άσκηση να προσδιορίσουμε την μορφή μιας μηχανής turing τι κάνουμε? πχ Ιουλίους 2015 θέμα 4

Αμαν με το elele

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

Για το θεμα 4 του ιουλη 15 καμια φωτο; Να ειμαστε σιγουροι γιατι κοβει αβερτα αν δεν τα κανεις ολοσωστα... ::)

Θεμα 3 Ιουνη του 15 βρηκατε οτι δεν την αποδεχεται;

Ναι, μου βγήκε ότι δεν ανήκει.


Νομίζω πρέπει απλά να καθορίσεις τα Κ,Σ,δ,s,H, που είναι όλα αρκετά εύκολα πέρα από το Κ (και κατ' επέκταση το δ). Δεν ξέρω αν υπάρχει κάνας αλγόριθμος για το πως το κάνουμε, μπορείς να αυτοσχεδιάσεις αλλά δεν ξέρω πόσο σωστή θα είναι μια τέτοια προσέγγιση...


+1

Αφου τα ΜΑΠΑ δεν μπορουμε να τα ελαχιστοποιησουμε!!!!

ΥΓ:Σου ειπα παρε την σ αλλα εσυ εκει το χαβα σου -_-

Εύρεση έκφρασης, όχι ελαχιστοποίηση.