THMMY.gr

Εδώ μπορείτε να σχολιάζετε τα θέματα και
να συζητάτε τις όποιες απορίες σας πάνω σε παλιά θέματα της
Θεωρίας Υπολογισμών και Αλγορίθμων.
(Τα παλιά θέματα υπάρχουν εδώ (http://www.thmmy.gr/index.php?option=com_docman&task=cat_view&gid=179&Itemid=45)).

Έχει λύσει κανείς το θέμα 3 του Φεβρουαρίου 2008?

Ta themata fetos itan teleia :)

agapame Ntelo!

Από ποια άποψη τέλεια? Εύκολα?

Ναι, έτσι μου φάνηκαν. 3 μονάδες για ένα ΑΠΑ... 3 μονάδες για μία μηχανή τούρινγκ... 1 μονάδα για να πεις με λόγια στο 1β ότι δεν υπάρχει λέξη από αα που να παράγεται από τη γλώσσα ή την παράθεση με τον εαυτό της... 1 μονάδα αν θυμάμαι καλά στο 1α για να γράψεις την ίδια γλώσσα με S'->SS τον μόνο νέο κανόνα...


Δεν ήταν εύκολα; (δεν ειρωνεύομαι, ρωτάω)

Πιάνοντας τα πρώτα μου θέματα(Σεπτέμβρη 2003).. μου δημιουργήθηκαν κάποιες απορίες.

Α)Το α* αφορά τις συμβολοσειρές που δημιουργούνται απο e και πλήθος α. 1)Μπορεί να ξεκινάει από e; 2)Μπορεί να είναι μόνο e;

Β)Μπορεί να λύσει και κάποιος άλλος τα Σ-Λ;

Γ)Στο 3ο θέμα, α ερώτημα, μετά από κάποια βήματα δημιουργούμε σαν τελικό σύμβολο το κενό. Αυτό το διαγράφουμε στο αμέσως επόμενο βήμα που αλλάζει το τρέχον; Ή στην τελευταία μετάβαση;

A) a*={{e},{a},{aa},{aaa}{aaa...}etc}  επομένως ναι και ναι.

Β)
1_Λ
2_ θα έλεγα σωστό αλλα δεν καταλαβάινω τη σημάνει τομή πολυπλοκότητας
3_Λ (δεν υπάρχει λέξη που να ξεκινάει με 2 ββα
4_Σ (στη καύτερη να είναι εα ΤΟΜΗ εα
5_Σ σελ7  σημειώσεις μέρος 2
6 no clue

Γ)δεν ειμαι σιγουρος τι ρωτας, αμα η δ δεν σου λεει τι  να κανεις για το κενο γιατι να το πειράξεις?

Thanks!!  ^hat^
Όσο για το Γ, επισημαίνεται μέσα στις διαφάνειες οτι σε μια ολική κατάσταση στις ΜΤ το τελευταίο στοιχείο δεν μπορεί να είναι το "κενο", εκτός αν είναι τρέχον. Και στο συγκεκριμενο παράδειγμα σε κάποια φάση, δημιουργείται(αναγκαστικά) ένα κενό επειδή ο "κερσορας" μεταβαίνει δεξιότερα απο το τελευταίο σύμβολο που είναι καταγεγραμένο. Anyway.. αυτο δεν νομίζω οτι είναι κ μεγάλο πρόβλημα. Οπότε και να μην διευκρινιστεί δεν υπάρχει θέμα. ;)

μπορέι κάποιος να λύσει το  θεμα 2α ΦΕΒ 2008 ΚΜC? δεν καταλαβαίνω πως εξαλείφουμε τους κοντούς κανόνες.

έχω
S -> XSX | X | e
X -> ab | e

εξαλείφω μακριούς κανόνες
S -> XS1 | X | e
S1-> SX
X-> ab |e

προς το κενό
S-> XS1 | X
S1-> SX|S
X-> ab|e

S->XS1 | X | S1
S1-> SX | S
X-> ab

και μετα το χάνω!

Στο θέμα 3 Ιανουάριος 2002 υπάρχει απλός τρόπος για το β (ΜΑΠΑ->ΑΠΑ); Γιατί ο αλγόριθμος γενικά θέλει δουλειά!

-Ιανουάριος 2003 Θέμα 1ο είναι Λ,Σ,Σ,Λ,Σ,Σ?

-Σεπτέμβριος 2003 Θέμα 2ο (vi)?

-Σεπτέμβριος 2002 Θέμα 3ο όταν φτάνει σε τελική κατάσταση αλλά το επόμενο στοιχείο της συμβολοσειράς δεν έχει δρόμο, θεωρείται αποδεκτή η συμβολοσειρά ή όχι? π.χ. (iv)

-Φεβρουάριος 2008 Θέμα 3ο,α) εννοεί ότι με το που ξεκινάει η ΜΤ γράφει στη πρώτη θέση το α?

-Ιανουάριος 2012 Θέμα 2ο, Α->Αα|αΒ|αα, τα | σημαίνουν  Α->Aα, Α->αΒ, Α->αα?

-Φεβρουάριος 2009, Θέμα 3ο, (δ) τί εννοεί αν είναι σαφής?

Το κενό δεν το δημιουργείς... Σκέψου απλά ότι μετά το τέλος της συμβολοσειράς σου υπάρχουν "σκουπίδια" ή αλλιώς κενά!

Έχω στο συνημμένο την λύση(πιστεύω οτι είναι σωστή)..

Λ,Σ,Σ,Λ,Λ,Λ Τα έβαλα, χωρίς να είμαι απόλυτος.
Πάντως αν ίσχυε το v) τότε δε θα καθόταν να αποδείξει στο βιβλίο σε τόσες σελίδες πως η έκφραση aⁿbⁿ δεν είναι κανονική.

Και γω το χω απορία..

Επίσης το χω απορία, γέρνω στο οτι δεν θεωρείται αποδεκτή.

Δεν ασχολήθηκα ακόμα με τα καινούρια θέματα, μόνο με του 11(τα παλούκια).
Αύριο πρωί με τα υπόλοιπα..

Ως προς το κενό νομίζω ξέχασες το S1->X..
ανεβάζω πάλι ενδεικτικά την λύση μου.

Το πρώτο θέμα το έχεις λύσει; Πως λύνεται;

Μια ερώτηση μιας και το έγραψες, αφού S->e και X->e, S1->SX δεν είναι προς το κενό?

Και 'γω έτσι το σκεφτόμουν στην αρχή, αλλά νομίζω είναι λάθος γιατί S και Χ μεταβαίνουν και σε άλλες καταστάσεις και αν το κάνεις αυτό λογικά θα χαθούν. Αν δεις και στο παράδειγμα στις διαφάνειες, S->SS αλλά S->e παρόλα αυτά η πρώτη μετάβαση παραμένει.. ;)
Καλύτερα, αν υπάρχει άτομο που πατούσε στα μαθήματα, να μας το πεί αν το εξήγησε ο Ντελο.


Υπάρχει κάποιος να μπορεί να μας εξηγήσει λίγο αναλυτικά το 4ο Θέμα Φλεβάρη 2009(ή Γενάρη 2002);;
αυτά τα "α-διαφορο του κενού" με μπερδεύουν.

https://www.thmmy.gr/smf/index.php?topic=47966.msg849220#msg849220 (https://www.thmmy.gr/smf/index.php?topic=47966.msg849220#msg849220)

Νομίζω έχεις ένα λαθάκι (εκεί που βγάζεις q1,q3 είναι q1,q2)... Αλλά και 'γω με αυτή τη λογική το λύνω...
Στο πρώτο θέμα του Ιανουαρίου 12 τί έκφραση είναι αυτή; Δεν υπάρχει κάτι που να μη δέχεται!Παίρνουμε ένα ΜΑΠΑ πχ με e κατάσταση (που δε χρειάζεται ουσιαστικά) και δουλεύουμε;

Νομίζω πως η λύση του α είναι Όχι,Ναι,Ναι,Όχι,
Γιατί αυτή η έκφραση, στο εσωτερικό της σημαίνει ή θα έχουμε μόνο ένα α ή κενό(λόγω β) ή παράθεση του β. Και ότι προκύψει σε παράθεση.. άρα, δέχεται μόνο κενό ή α(παράθεση) ή β(παράθεση).

Υ.Γ.Όλα αυτά που λέω είναι απλά το πως τα καταλαβαίνω εγώ.. μην τα πάρετε σίγουρα σωστά. :P Δεν το κατάλαβα και γω πλήρως το μάθημα.

Δε νομίζω... Μπορεί να γραφτεί ούτως ή άλλως (a*ένωσηb*)*... Η παράθεση πάει σε ολόκληρη την ένωση... :(

Για να βρείτε το ελάχιστο ΑΠΑ πρέπει να το μετατρέψετε πρώτα σε ΑΠΑ από ΜΑΠΑ.

Για να γίνει αυτό χρειάζεστε μια ακόμα κατάσταση στο αρχικό αυτόματο και μετά να γίνει η ελαχιστοποίηση.


Ναι, δίκιο έχεις όλα σωστά είναι.

Το μέγεθος του (ελάχιστου) αυτόματου εξαρτάται αν το αλφάβητο  έχει μόνο τα γράμματα α,β ή περιέχει πχ και ένα γράμμα c

http://regexpal.com/?flags=g&regex=((a)%7C(b*))*&input=abaaaaa%20a%20aaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbababa (http://regexpal.com/?flags=g&regex=((a)%7C(b*))*&input=abaaaaa%20a%20aaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbababa)

Όταν λες μία ακόμα κατάσταση στο αρχικό; Δε θα πάρουμε το αρχικό όπως δίνεται, μετά ΜΑΠΑ->ΑΠΑ και μετά ελαχιστοποίηση;

Για το 2ο έχεις δίκιο... Υπάρχει και αυτή η περίπτωση...

Εννοώ ότι ναι μπορεί να γίνει και με τον αλγόριθμο λογικά. Αλλά μπορείτε αρχικά αφού λείπουν από το αρχικό μεταβάσεις που οδηγούν σε απόρριψη να τις προσθέσετε κατευθείαν. Τότε έχεις αμέσως ένα ΑΠΑ αφού δεν έχει μεταβάσεις με το e ούτε διπλές μεταβάσεις. (Και προφανώς δέχεται την ίδια γλώσσα) Αυτό γίνεται όμως μόνο σε πολύ απλές περιπτώσεις

Αν μιλάμε για το ίδιο θέμα (θέμα 3 Ιανουάριος 02), η q1 πηγαίνει και στη 2 και στην 3 με b (έχεις διπλή μετάβαση)... Anyway, καταλαβαίνω τι λες και όντως σε αρκετά προβλήματα μπορείς να δουλέψεις έτσι...Thnx!
Κάτι πιο θεωρητικό, στον αλγόριθμο ΜΑΠΑ->ΑΠΑ τις καταστάσεις που βγαίνουν "κενές" (από τα δ που υπολογίζουμε) τις βάζουμε κανονικά στο διάγραμμα και τις μετράμε σαν καταστάσεις (μπορούν βέβαια να συμπτυχθούν σε μία κενή);

Ουπς.. Τα μπέρδεψα.


Δεν ξέρω. Αφού K'=2^K δεν περιλαμβάνει και το {}? Δυστυχώς δεν το διευκρινίζει κάπου στο βιβλίο. Εγώ θα τον ρώταγα εκείνη την στιγμή.

Αλλά το {} είναι μοναδική κατάσταση δηλαδή αν εμφανιστεί παραπάνω από μια φορά αναφέρεσαι στην ίδια λογικά.

Κάτι τελευταίο... Στο θέμα 3 του 11 η wcw θα είναι συμμετρική, ή πχ μπορεί να είναι aacbb (μάλλον το πρώτο βέβαια); Για το α ερώτημα τι μπορούμε να πούμε;

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

όχι ακριβώς συμμετρική π.χ aabbcaabb,   abbbabcabbbab

Ok...thnx και πάλι...

Έχει λύσει κανείς το 2ο Θέμα Γενάρη '12?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Όταν βρεθούμε στην q0 είναι σα να βρισκόμαστε σε τελική δηλαδή? Γιατί με αυτό το τύπο γίνεται δεκτη και η ααα ....

Αντίστοιχα Σεπτέμβριος 14' θέμα 1 β) Κ.Ε  (α*(ββα)*U ββ(αUββ)* U βα)* ???

στα θέματα 2/2011 στο θέμα 3β-πώς κατασκευάζουμε τη μηχανή;
γενικά μπορεί κάποιος να πει έτσι πρόχειρα πώς κατασκευάζουμε τη μηχανή;

Ναι, αφού υπάρχει μετάβαση e από την q0 στην q2. Η συμβολοσειρά αυτή είναι από τις αποδεκτές του αυτομάτου, το βλέπεις έτσι;

Ναι οκ,,απλά στο μάθημα όσες ΚΕ βρίσκαμε ήταν απο ΑΠΑ για αυτό μπερδεύομαι με την e. thx!!

Γιατι ετσι σημερα?

Βατά θέματα, λίγος χρόνος. Ξύπνησε στραβά ο Ντελό;

Υποθετω... Και η αλλαγη θεματος στο μισαωρο ηταν καλη φαση

Τα θεματα ηταν βατα, ναι. Γενικα τα θυα ειναι ευκολο μαθημα αλλά ήταν πιο δυσκολα απο αλλες φορες. Ή καλύτερα, ΠΟΛΥ πιο χρονοβόρα από άλλες χρονιές.

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

Οι επιτηρητές στ'αρχιδια τους αμα δεν ειχε τελειωσει κανενας και ζητουσαμε παραταση. Ενα τηλ τον ντελο θα μπορουσαν να παρουν. Ένα μιαωρο παραπανω νομιζω πως θα αρκουσε για όλους.

+1 και εγώ επιτόπου έκανα το αυτόματο στοίβας, μάλλον λάθος είναι αλλά δεν προλάβαινα να το κάνω προσεκτικά με το βιβλίο.

(Έχασα και ώρα γιατί πήγα να αρχίσω από το 2ο θέμα που το α) ερώτημά του δεν λυνόταν πριν την διόρθωση. :()

Πραγματικα με ενα μισαωρο παραπανω θα ηταν μια χαρα...
Δε μπορω να καταλαβω τη λογικη πραγματικα..

Ο Ντελό είναι ΜΑΠΑ  :D

ΑΑΑ λίγα τα λόγια σου για τον θεούλη!!  :D  Είναι ΑΠΑ και βάλε !!!  :D

Μηχανή Turing ρε! ;D

Μα κάθε ΑΠΑ είναι ΜΑΠΑ  :P

Ε ναι, αλλά τα ΑΠΑ είναι καλύτερα από τα ΜΑΜΑ...

Lisa Ann disapproves

Πως βρησκουμε οτι μια γραμματικη ειναι ασαφης?

Η απαντηση ειναι οτι αν μια συμβολοσειρα γεννιεται απο περισσοτερα του ενος ΣΔ τοτε εχουμε ασαφη γραμματικη?
Δηλαδη αρκει να αποδειξουμε οτι υπαρχουν τουλαχιστον δυο δρομοι που οδηγουν στην ιδια συμβολοσειρα?

Ακριβώς!

Κάπου στις σημειώσεις-ασκήσεις του Ντελόπουλου, λέει ότι αν χρησιμοποιώντας Δυναμικό Προγραμματισμό, σε ένα κελί του πίνακα εμφανισθούν δυο διαφορετικοί συνδυασμοί για μια συγκεκριμένη συμβολοσειρά, τότε αυτό σημαίνει ότι έχουμε ασαφής γραμματική.
Οπότε μπορούμε να αποδείξουμε έτσι την ασάφεια ή μη ;

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

Ναι, αν βρεις έστω και ένα παράδειγμα τότε είναι αυτόματα ασαφής.

ευχαριστω!

Πως αποδεικνύουμε ότι μια γραμματική είναι σαφής? (βλ. θέμα 2β, Σεπτ. 2015)

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

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

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

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

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

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

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

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

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

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

απο τα θεματα του φεβρουαριου του 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 περιπτωσεις σε τελικη κατασταση τοτε ειναι ισοδυναμες?

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

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

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

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

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

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

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

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

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

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

ωραιος! ναι εχεις δικιο

Mπορεί κάποιος μια και καλή να απαντήσει στις ερωτήσεις του τύπου: "Να αποδείξετε ότι το σύνολο των αναδρομικa απαριθμήσιμο γλωσσών είναι κλειστό ως προς ένωση,παράθεση κλπ;; " 

Πιστεύω είναι πολύ πιθανό να πέσει κάτι τέτοιο αύριο μιας και δν έπεσε ούτε το Σεπτέμβρη ούτε πέρυσι.
(Βλέπε φωτο, για κάποιο λόγο δεν μπορω να την βάλω embedded)

http://oi64.tinypic.com/abtpic.jpg

+1

+@itsitsou

αναφορικά με τις λύσεις του 03/02/15 θέμα 1 ερώτημα γ
http://www.intelligence.tuc.gr/~theory/previous/Theory_2007/lectures/theory2007lecture04.pdf (http://www.intelligence.tuc.gr/~theory/previous/Theory_2007/lectures/theory2007lecture04.pdf)
και την σελίδα 6 μήπως το γ είναι τελικά σωστό?(abb,bba ισοδύναμα καθώς καμία δεν ανήκει στη νέα L)?

+Ευχαριστούμε πολύ για το υλικό σου.  8))

Έγινε μια συζήτηση για αυτό το ερώτημα στο "[Θ.Υ.Α.] Γενικές απορίες και ανακοινώσεις/επικαιρότητα 2015-2016". Ρίξε μια ματιά εκεί αν θες, νομίζω ότι αυτό που έγραψα στα λυμένα θέματα είναι τελικά σωστό.

Δες το παράδειγμα στην σελίδα 12 του 3ου Μέρους διαφανειών.  ;)

Είναι σωστό βάση του θεωρήματος  myhill Nerode σελ 138 και επειδή το απα που σχεδιάσαμε είναι το ελάχιστο άρα κλάσεις ισοδυναμίας της L είναι οι καταστάσεις του Μ   (αφού είναι οι ελάχιστες).
Νομίζω ότι το έχω καταλάβει σωστά αν δεν ισχύει πείτε τπτ

Η wcw δεν απαιτει μνημη;μπορει να ειναι παραθεση κανονικων γλωσσων αλλα εχει το στοιχειο οτι επαναλαμβανεται ακριβως η ιδια συμβολοσειρα!Δεν μπορει να ξερει το αυτοματο τι εχει γινει πριν το c ωστε να το επαναλαβει.

Εχει κανεις τελειωμενο το θεμα 2 φλεβαρης '15??

Επισης αν μπορει να εξηγησει καποιος την εξαλειψη κοντων κανονων  για ΚΜC

Οι συγκεκριμενες ερωτησεις ειναι οι πιο δυσκολες ερωτησεις κλειστοτητας που μπορουν να πεσουν, κι αυτο γιατι ειναι πιθανο η αντιστοιχη turing machine (TM) που ημι-αποφασιζει μια αναδρομικα απαριθμήσιμη γλώσσα να μην τελειωνει ποτε. Η τεχνικη που θα χρησιμοποιησω ξεπερναει αυτο το προβλημα, ομως αφου ο,τι αλλο και να βαλει (κανονικες γλωσσες, αναδρομικες γλωσσες) εχουμε αντιστοιχα μηχανημα που τερματιζει με σιγουρια, τα πραγματα γινονται πολυ πιο απλα.

Παραθεση : Εχουμε δηλαδη TM1 που ημιαποφασιζει L1 και TM2 που ημιαποφασιζει L2. Με μια καινουρια TM δημιουργουμε ολα τα πιθανα w1, w2 ωστε να ισχυει w1w2 = w, οπου w το input. Προφανως αν |w| = n τοτε τα πιθανα σπασιματα που θα κανουμε ειναι περιπου n (για την ακριβεια ειναι n+1 γιατι w1 μπορει να ειναι απο κενο μεχρι w).
Η δουλεια που θα κανει το TM μας κατοπιν ειναι καπως ετσι :
for (i=1; true; ++i) //Δε σταματαει ποτε
 for all possible pairs w1,w2
  simulate one step of w1 using TM1
  simulate one step of w2 using TM2
  if both accepted
   accept

Μπορουμε να αποδειξουμε ευκολα οτι ετσι ημιαποφασιζεται η L1L2. Εξ ορισμου αν το w ανηκει L1L2 τοτε υπαρχουν δυο strings w1 ανηκει L1 και w2 ανηκει L2, το καθε ενα απ τα οποια ημιαποφασιζεται απο την TM1 ή την TM2 (εστω σε x βηματα το ενα και σε y βηματα το αλλο). Οταν i=max {x,y }+1 τοτε θα εχουν ηδη γινει αρκετα βηματα και για τα δυο strings ωστε να εχουν αποδεχτει και τα δυο, κι ετσι η TM μας θα αποδεχτει.
Μπορουμε ευκολα να δουμε οτι αν δεν υπαρχουν τετοια strings (w δεν ανηκει L1L2) τοτε η TM μας δε θα σταματησει ποτε, ομως δεν ειναι καν αναγκαστικο αυτο! Αρκει αυτο που αποδειξαμε.

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

Το kleene star με την ιδια ακριβως λογικη, το σπαμε με ολους τους δυνατους τροπους που γινεται και προσομοιωνουμε μεχρι κατι απο ολους αυτους τους (παρα παρα παρα πολλους, αλλα πεπερασμενους) τροπους να αποδεχτει.

Το κλειδι ειναι δηλαδη οτι εργαζομαστε παραλληλα σε ολα, ετσι ωστε ακομα κι αν κατι μπει σε infinite loop, οι υπολοιποι να μπορουν να συνεχισουν.

Το (α) ερωτημα ειναι γελοιο, αρκει να κανουμε μια αντιστοιχη TM που θα εχει 3 καταστασεις ετσι οπως το σκεφτομαι ολες κι ολες.
Το (γ) ειναι ενδιαφερον, λεμε οτι αφου ισχυει το (α) (base case), και μπορουμε να εφαρμοσουμε καθε πραξη που εφαρμοζεται στις κανονικες εκφρασεις, αρα μπορουμε να ημι-αποφασισουμε καθε γλωσσα που οριζεται απο κανονικη εκφραση. Εξ ορισμου αυτες ειναι οι κανονικες γλωσσες.

Παρατηρηση 1 :
Το γεγονος οτι δε γνωριζουμε τα x και y που εγραψα δε μας πειραζει, αφου η επαναληψη μας τρεχει επ απειρον, οποτε σιγουρα (αν υπαρχουν x και y, δηλαδη αν ανηκει το w στην L1L2) καποια στιγμη θα τα πετυχει.
Παρατηρηση 2:
Τα πραγματα θα γινονταν δραματικα ευκολοτερα αν μας ζητουσε το ιδιο πραγμα για αναδρομικες γλωσσες. Τοτε υπαρχει TM που σιγουρα τερματιζει, οποτε δε χρειαζεται το κολπο της (σειριακης) παραλληλοποιησης. Απλως θα τρεχαμε ολα τα ζευγαρια μεχρι να τελειωσουν κι αν εστω κι ενα ζευγαρι ειχε δυο YES θα αποδεχομασταν, αλλιως δε θα αποδεχομασταν.

Αν η εκφώνηση αναφέρεται στο ίδιο, αυτούσιο w πριν και μετά το c τότε δε μιλάμε για παράθεση κανονικών γλωσσών και ναι δεν είναι regular αλλά context-free. Για να αποδειχθεί αναδρομικότητα εδώ θα κατασκεύαζα την αντίστοιχη context-free grammar (άρα υπάρχει αυτόματο στοίβας και άρα υπάρχει Τ.Μ.).

Δεν το σκέφτηκα ότι αναφέρεται στο ίδιο string. Αν ισχύει, good spot!

Ρίξτε και μια ματιά και σε παλαιότερη απόπειρα μου.

Εχει λαθος αυτο που εγραψες στο (β). Κι αυτο επειδη λεγοντας να παρεις το OR δυο πραγματων χωρις να πεις τον τροπο με τον οποιο θα το παρεις μπορει να πεσεις σε infinite loop (προυποθετεις εσωτερικα χωρις να το εχεις πει οτι τα TM θα τερματισουν, χωρις αυτο απαραιτητα να ισχυει ομως). Πρεπει οπωσδηποτε να γινει η (σειριακη) παραλληλοποιηση ωστε ακομα κι αν ενα σπασιμο w1w2 ειναι αποτυχημενο, να μην επηρεασει τα υπολοιπα σπασιματα που μπορει να τερματισουν.

Με επιφύλαξη για το α)
θεμα 2 φλεβαρης '15

Η λογικη ειναι οτι απλως τους αφαιρεις, και μετα κοιτας που μπορει να ειχαν συνεισφερει.
Πχ αν εχεις S->AB και A->k τοτε αυτο θα μπορουσε να συνεισφερει στον S ως S->kB (απλη αντικατασταση). Πας και ενημερωνεις ολους οσους μπορει να επηρεαστηκαν απο την αφαιρεση του κοντου κανονα με αμεση αντικατασταση και θα εισαι τζετ στα πλαισια της εξετασης.

Ποσο περηφανος θα ηταν ο Turing για σας ρε μαγκες...  ;D ;D

Η λογική μου φαίνεται σωστή. Αρκεί όμως για όλο το σύνολο των αναδρομικά απαριθμησιμων γλωσσών; Η εννοεί για τις αναδ απαρ από το συγκεκριμένο Σ;
Αν γίνεται να ανεβάσεις τις ΜΤ που χρησιμοποιριε για κάθε μια ενωση, παραθεση, Kleene  συγκεκριμένα θα βοηθούσε.

2 Ερώτημα έχουμε βρει κάνα τρόπο με να ελέγχουμε εάν μια ΓΧΣ είναι σαφής;

Για ολες, δε χρησιμοποιησα κατι σχετικο με το Σ για την αποδειξη  ;).

Γενικα το προβλημα που αναφερεις ειναι undecidable (με αναγωγη απ το PCP αν σε ενδιαφερει περα απ τους σκοπους της εξετασης).
Αυτο δεν ειναι κατι τρομακτικο βεβαια. Σημαινει απλως οτι δεν υπαρχει συστηματικος τροπος να το βρουμε για οποιαδηποτε ΓΧΣ.
Μπορουμε ομως για την συγκεκριμενη ΓΧΣ που θα δωσει να βγαλουμε συμπερασματα, μονο που δεν υπαρχει μεθοδολογια (και δε μπορει να υπαρξει μαλιστα, σε τετοιες αποδειξεις ειναι η ομορφια ολου του μαθηματος). Προσπαθεις να το αποδειξεις μονος σου. ΠΧ μπορει να δεις οτι μονο ενα συγκεκριμενο non-terminal symbol μπορει να παραξει καποιο γραμμα, και να πατησεις σε αυτο το γεγονος για να χτισεις την αποδειξη σου. Αν στειλεις συγκεκριμενο θεμα μπορω να σου απαντησω, αλλα οπως ξαναειπα μπορει αυτο να μη βοηθησει καθολου αφου δεν μπορει να υπαρξει συστηματικος τροπος.

Υ.Γ.: Δεν καταλαβα τι ειπες με τις διαφανειες, δε νομιζω να εχει ανεβασμενο κατι σχετικο ο Ντελο.

Όχι, δεν προυποθέτω ότι τα ΤΜ θα τερματίσουν.

Η διαδικασία που περιέγραψες είναι το dovetailing. Όπως θα ξέρεις, χρησιμοποιείται για να αποδείξει την αναδρομική απαριθμησιμότητα ενός άλλου, πολύ σημαντικού, συνόλου (νομίζω το αναφέρει το βιβλίο του παπαδημητρίου στο 5 (?)). Δεν είναι απαραίτητη εδώ όμως. Αν το επιθυμείς, I can elaborate more.

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

Εννοειται ρε, αν υπαρχει πιο απλος τροπος πες το, εγω δε μπορεσα να σκεφτω κατι.
Αυτο που ειπα ειναι οτι η πραξη OR πρεπει να διευκρινισουμε πως θα εφαρμοστει. Αν πχ παρουμε (στην ενωση) και προσομοιωσουμε με την TM1 μεχρι να παρουμε απαντηση, κι αν παρουμε απαντηση YES (αφου εχουμε or) ενω αν δεν παρουμε συνεχιζουμε να το προσομοιωνουμε, τοτε αν το TM2 αποδεχεται ενω το TM1 μπαινει σε infinite loop δε θα παρουμε ποτε απαντηση, ενω υπαρχει.
Εν ολιγοις συμφωνω με το OR, το θεμα μου ειναι οτι πρεπει να εφαρμοστει με τροπο που να μην κολλαει σε μια αποτυχημενη προσπαθεια (στο παραδειγμα πανω προσομοιωση με TM1).

Andromedas:
Ο,τι να ναι καταλαβα, Turing Machine μαλλον εννοουσες με το MT; Ειναι παρα πολυ παιδεμα να το ορισουμε πληρως και δεν υπαρχει λογος, αφου γνωριζουμε οτι ειναι πληρως ισοδυναμα με καθε γλωσσα προγραμματισμου. + οτι ο Ντελοπουλος ειναι μορφη, αν δει οτι καταλαβες δεν υπαρχει περιπτωση να κοψει επειδη δεν ηταν αυστηρη η αποδειξη.

Ναι η αλήθεια είναι δεν έμπλεξα με αυστηρούς μηχανικούς όρους και το άφησα έτσι μετέωρο. Ουσιαστικά μίλησα για 3 μηχανές που τρέχουν παράλληλα. Από πλευράς υπολογισιμότητας δεν αλλάζει απολύτως τίποτα έτσι (http://cs.stackexchange.com/questions/42175/is-multiprocessing-possible-on-a-turing-machine), αλλά άμα ήταν να το ορίσω αυστηρά τότε... dovetailing it is hoohoo.

Απλως παιρνουμε το κειμενο που θελουμε να ελεγξουμε αν ανηκει στη γραμματικη, βλεπουμε το πρωτο γραμμα του, και αντικαθιστουμε το S με τη μοναδικη παραγωγη που γενναει σαν πρωτο γραμμα αυτο που θελουμε (ευκολη η αποδειξη οτι μονο αυτη η επιλογη στεκει). Συνεχιζουμε με αυτο τον τροπο και αποδεχομαστε μονο εαν τελειωσουμε το κειμενο ΚΑΙ τελειωσουμε και τα S ταυτοχρονα.

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

Θεμα 3 φλεβαρης 13
Τσεκάρετε άμα ισχύει η λύση μου ,ο τύπος για τις κλάσεις κανονικών γλωσσών είναι στην σελ 83 παπα
Πλσ ποστ για διορθώσεις. Ευχαριστώ!

Το θεμα 2β του Φλεβαρη '14 ειναι ιδιο με το 2β του Σεπτεμβρη '15

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

Φλεβαρη '14 ειναι ιδιο με το 2β του Σεπτεμβρη '15 ειναι το ιδιο
Απαντήθηκε παραπάνω.

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

Παιζει να ειναι και δυσκολο να πεσει αφου μπηκε το σεπτεμβρη

Απαντήθηκε, δεν υπάρχει απόδειξη...  Άρα περιγραφικά.

GG

Δεν ειχα δει την απαντηση..

Παιδιά, στο θέμα 2/Φεβρουάριος 2013, όταν ζητάει να σχεδιάσουμε αυτόματο στοίβας που αποδέχεται τη γλώσσα L και μας έχει δώσει και το ΜΑΠΑ για την L, πώς βρίσκουμε το αυτόματο στοίβας; Υπάρχει κάπου συγκεκριμένα στη θεωρία ο τρόπος;

Παίδες μήπως μπορεί να βοηθήσει κανείς με το 1ο θέμα της εξέτασης του ιουλίου που  μας πέρασε?

αμα  ανεβασεις το θεμα μπορει...

Αυτό ειναι το θέμα το οποίο δυσκόλεψε πολλα παιδιά στην εξέταση

ωραια μιας κ θ ασχοληθω απο αυριο περιγραμματικα απ αυτα που θυμαμαι:

αφου ζηταει ΠΑ και δν λεει αιτιοκρατικο η μη  θα φτιαξεις ενα ΜΑΠΑ με τη διαδικασια της ενωσης * κτλ αναβιβαστικα (σελ 8 σημειωσεις μερος 2) και απο κανα παραδειγμα απο σημειωσεις/παραδειγματα

αν το ξερεις αυτο και δν ξερεις πως γινεται , θ το λυσω αμα ειναι αυριο

Καλό θα ήταν τα θέματα που έχετε (και δεν υπάρχουν ήδη ανεβασμένα) να τα ανεβάζετε στα downloads  ;)  8))

@WatchDog, αν έχεις τα θέματα ολοκληρωμένα, ανέβασε τα πλζ.

Μέχρι να ανέβουν στα downloads

Θέμα 2ο και 3ο Ιουνιου 2016

Παιδιά έχουμε λύση για το θέμα 2ο Φλεβάρης 2002 ? κυρίως για το β)

Μου βγαίνουν 2 καταστάσεις παραπάνω . Είσαι σίγουρος για τη λύση?

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

ιουλιος 2016 και απο εμενα το εχω κανει λιγο πιο γρηγορα το πρωτο θεμα και θελω να μου πειτε αμα σασ φαινεται αυθαιρετο
Συμφωνα με μια φιλη μου που το εκανε καπως ετσι (η οποια το ειχε σωστο) εβγαινε σε αυτην κατευθειαν ελαχιστο


ps1:βασικα οκ ειμαστε λογικα ιδιοι με τον nvog1993

ps2: στο τελευταιο θεμα εχω ξεασει το ενα α

θεμα 2ο 2005?
θεμα 3ο  β 2005?????
Θεμα 4ο 2005 β ολοοοο?

2/2013 θεμα 3ο το γ κανεις; κάποιος που έχει γράψει ολοκληρωμένη λυση ας το ανεβασει αν μπορεί

Πρέπει να αποδείξεις ότι ξεκινώντας με δύο αναδρομικά απαριθμήσιμες γλώσσες και εφαρμόζοντας τις σχέσεις Ενωση, Παραθεση και Kleene Star, θα καταλήξεις πάλι σε αναδρομικά απαριθμήσιμη γλώσσα. Γενικά οι αποδείξεις αυτές βγαίνουν βρίσκοντας μηχανές Turing που (ημι)αποφασίζουν την εκάστοτε γλώσσα. Για παράδειγμα, για τη γλώσσα (L1 Ένωση L2) , μπορούμε να πούμε ότι η μηχανή που την αποφασίζει είναι μια η οποία ξεκινάει με την μηχανή της L1. Αν δεν τερματίσει αυτή, πηγαίνει πίσω την ταινία στην αρχή της λέξης με μια βασική μηχανή L και συνεχίζει με τη μηχανή της L2. Άρα και η ένωση αναδρομικά απαριθμήσιμων γλωσσών παράγει αναδρομικά απαριθμήσιμη γλώσσα.

Για την παράθεση, απλά βάζεις τη μία μηχανή δίπλα στην άλλη.

Για το Kleene Star της L1 π.χ., αυτό που σκέφτηκα είναι μια μηχανή που θα αρχίζει με τη μηχανή Μ1 της L1. Πριν φτάσει σε κατάσταση αποδοχής μιας λέξης (π.χ. μετά από κάποια βήματα, αν διαβάσει ακόμα ένα α, αποδέχεται τη λέξη της L1), σ αυτό το σημείο, βάζουμε ακόμα μια μηχανή που ελέγχει αν το επόμενο στοιχείο είναι κενό ή όχι, Αν είναι, τότε πάμε σε κατάσταση αποδοχής. Αν δεν είναι, πάμε τη ταινία ένα χαρακτήρα πίσω και πάμε πάλι στην αρχή της μηχανής. Ουσιαστικά, έτσι διαβάζουμε μία μία τις λέξεις από τις οποίες αποτελείται μια λέξη του Kleene Star. Επίσης πρέπει να βάλουμε και μια μηχανή έτσι ώστε αν διαβάσει πρώτο χαρακτήρα κενό, να κάνει αποδοχή.

Τέλος, κάθε κανονική γλώσσα αποτελείται από τις βασικές γλώσσες L[a], a ανήκει στο Σ, τη κενή γλώσσα και τους συνυδασμούς τους μέσω των πράξεων της ένωσης, της παράθεσης και του Kleene Star. Άρα, αφού έχεις αποδείξει τα παραπάνω για κάθε γλώσσα, μπορείς να ισχύριστείς ότι κάθε κανονική γλώσσα είναι και αναδρομικά απαριθμήσιμη

Σεπτέμβριος 12 Θέμα 3 το έχει λύσει κάποιος ?

Αυτή η λύση πως σου φαίνεται?

Νομίζω το 2ο είναι λάθος. Η γλώσσα ουσιαστικα δέχεται οποιαδήποτε λέξη, αρκεί να αρχίζει με α, αφού κάθε λέξη είναι παραθεση των λέξεων, {α, αβ, αββ..} κλπ. Από τη στιγμή που έχει αρχίσει με α, μετά μπορείς να βάλεις ας πουμε οσα β θες και όσα α, αφού η α ανήκει στη γλώσσα και όλα τα β θα ακολουθούνται πάντα από τουλάχιστον ένα α.

Αυτό το yes που επιστρέφει στο πρώτο R (2o σχήμα-ερώτημα β) δεν το καταλαβαίνω...γιατί το έβαλες?

Έχεις δίκιο , μη το κοιτάς . Όπως έιπε  nvog1993 ειναι λάθος το β'.Δες τη λύση του παιδιού καλύτερα.

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

{w / w = aⁿbⁿ , n μη αρνητικός ακέραιος} ⊆ L( (a*b*) )

Αυτη η προταση ισχύει ή όχι; και γιατι;

Χωρίς να είμαι σίγουρη, παίζει να ισχύει επειδή στην L ανήκουν οι εκφράσεις του στυλ aaabbbbb με όλους τους πιθανούς συνδυασμούς για το ποσα a και b έχεις. Στην anbn έχεις ίδιο αριθμό a και b. Βέβαια νομίζω το anbn δεν ειναι κανονική έκφραση, δεν ξέρω αν έχει να κάνει αυτό. Σκατα, μαλλον πιο πολυ σε μπέρδεψα, αλλα τα ΣΛ του ντελο ειναι πολύ tricky.

Γι αυτο ακριβως το λεω. το προφανες θα ηταν το σωστο. Αλλα αυτη η εκφραση προυποθετει να εχουμε μνημη. ή δε μας νοιαζει;

Η λογική μου μου λέει ότι ρωτάει καθαρά αν αυτή η έκφραση είναι υποσύνολο της άλλης. Εγώ θα απάνταγα σωστό, γιατί να μας νοιάζει το ότι πρέπει να έχουμε μνήμη; Αλλά ναι, δεν είμαι καθόλου σίγουρη...

Που διαβάζετε αυτά τα περίεργα σχετικά με αν μια γλώσσα είναι κανονική. Ξέρω ότι μπορώ να ψάξω τα slides αλλά θα μου γλίτωνε χρόνο αν κάποιος που θυμάται μου έλεγε που βρίσκονται.

1ο μέρος, σελ. 21 αυτα δε λες;

Many thanks bretha, η πρώτη μου γρήγορη απόπειρα να το βρω απέτυχε άσχημα μάλλον. Αυτα ελεγα. ;)

Νομίζω όχι. Γιατί την a^nb^n δεν μπορείς να την παράγεις με απλά αυτόματα , παρά μόνο με ΓΧΣ ( πχ S--> aSb | e ) ενώ την α*β* μπορείς, άρα η μία είναι κανονική η άλλη ΓΑΣ. Το ανάποδο πρέπει να είσαι σωστό. Με κάθε επιφύλαξη πάντα.

Στα λυμένα θέματα του Σεπτ 2014, κατα πόσο σωστή πιστεύετε είναι η ασκ 1β και ποια είναι η μεθοδολογία επίλυσης της??

Καλημερα, γνωριζετε πως ελεγχουμε αν δυο συμβολοσειρες ειναι ισοδυναμες ? (π.χ. να ελεγξω αν abb = _Lbba)

Αν καταλήξουν σε ισοδύναμες καταστάσεις, τότε είναι και αυτές ισοδύναμες.

έχει κανείς λύσεις από τα θέματα φλεβάρη '17?

Νομίζω εδώ είναι πιο σωστό να ρωτήσω.... Έχει κανείς λύσεις από Φλεβάρη '17?

Κάποιος τα θέματα του Ιουνίου 17;;

ειχε λιγο κοσμο, μιση Α5 με σειρα παρα σειρα.
εκτιμώ ότι αφού δεν ανέβηκαν ήδη δεν προγδφγ δφγδφγδ-----------

μαλακίες λέω, παίζει να τα έχω εγώ. όταν πάω σπίτι θα δω και θα τραβήξω μια φωτό.

ποια ειναι η διαφορα οταν μας ζηταει μια μηχανη turing να αποφασιζει μια γλωσσα και οταν ζηταει να ημιαποφασιζει τη γλωσσα; π.χ. Ιουνιου '17 , γιατι δεν εχω βρει παρομοιο λυμένο

Αποφασίζει σημαίνει ότι η μηχανη σου έχει δυο halting states (yes or no) που τερματιζει στην κατασταση yes αν η γλώσσα ειναι αποδεκτή και no αν δεν ειναι.

Ημιαποφασιζει σημαινει οτι η μηχανη εχει ενα halting state (yes) που τερματιζει η μηχανη σ εκεινο το state αν αποδεχεται τη γλωσσα, αλλιως δεν τερματιζει ποτε και μενει σ ενα ατερμονα βροχο για παραδειγμα.

Με τη μέθοδο της σύνθεσης όταν λέει τι παίζει;;

Ξερει κανεις πως χρησιμοποιουμε το θεωρημα της αντλησης για τις κανονικες γλωσσες??

Μπορείς να δεις στο channel του Ψούνη στο Youtube πλη 30 είναι... Αν και δεν ξέρω πως ακριβώς το θέλει ο Ντελόπουλος.. Και δεν το είδα κάπου στις σημειώσεις του αυτό είναι το παράξενο... ( ενώ σε ασκήσεις άλλων χρόνων το αναφέρει)

εχει λυσει κανεις το 3ο θεμα απο Σεπτεμβριο 2016;

Και για το 1ο Θέμα επίσης αν υπάρχει καμιά ιδέα..

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

Έχει σχεδιάσει κανείς την turing του ιουνιου 2017? και αν ναι μπορει να το εξηγήσει?

Μια προσπάθεια είναι αυτη..

Θεμα 2ο Ιουνιου 17 το ελυσε καποιος?

Μόνο εμένα δεν με αφήνει να  την περιστρέψω;;  :o

Στο 1ο θέμα  του Φεβ 14 που λέει το (γ) πως το απαντάμε;;

Γενικά όταν έχεις w1 περίπου ίσοLδείκτης   w2 πως κινούμαστε;;

φεβρουαριος 2017, θεμα 2ο.
Για να δειξω στο α ερωτημα οτι ειναι ασαφης μπορω να το κανω με δεντρα.

Για το δευτερο ερωτημα ομως, πως μπορουμε να δειξουμε αν ειναι σαφης ή ασαφης?

Σε ερωτήσεις τύπου: ''Πόσες καταστάσεις έχει το ελάχιστο ΑΠΑ που είναι ισοδύναμο προς Μ'', τι απαντάμε ;

Αν κάνεις ένα δέντρο ( οποιοδήποτε ) όταν θα πας να αντικαταστήσεις, το οποιοδήποτε τερματικό σύμβολο, αυτό θα είναι πάντα στην ίδια θέση ανεξαρτήτου πως θα κάνεις τις αντικαταστάσεις των S, O . Και αυτό γιατί το Ο βάζει τα τερματικά του τέρμα αριστερά και έχεις ένα κανόνα OSS , για τον οποίο πάλι τα SS στην ίδια θέση θα βάλουν τα τερματικά τους, άρα δεν μπορείς να φτιάξεις 2 διαφορετικά δέντρα για την ίδια συμβολοσειρά , άρα δεν είναι ασαφής... ( Πχ στο πρώτο μπορείς να βγάλεις για την ίδια συμβολοσειρά ένα δέντρο αριστερού βάρους και ένα δεξιού..) Δεν το εξήγησα και πολύ καλά, πάντως έτσι κάπως πρέπει να κινηθείς


Απλά κάνεις το ΑΠΑ Μ που σου δίνει ( αν γίνεται ) ελάχιστο ( δηλαδή αν δεν είναι ήδη) και λες πόσες καταστάσεις έχει..

Μπορείς να βρεις τις σχέσεις ισοδυναμίας (αν υπάρχουν) και να πεις πόσες είναι οι καταστάσεις, δε χρειάζεται να κάνεις όλο το ΑΠΑ.

νομιζω οτι αφου και με την w1 και με την w2 καταληγεις στην ιδια κατασταση, θα ισχυει η σχεση αυτη

Εχει λυσει κανενας Σεπτεμβριο 2016?

Μόνο το β..

Χμμ μάλιστα .. Θα πρέπει να το έχω και στην ελάχιστη μορφή το ΑΠΑ ε;; ( Στου Φεβ. 14 που έπεσε, και υπάρχει λυμμένη, βέβαια το ελάχιστο το ζητούσε στο β) Το λέω αυτό γιατί αν w1 σε πάει στο q1 και w2 σε πάει σε q2, Αν δεν είναι στην ελάχιστη μορφή, μπορεί αυτές να μπορούν να ενωθούν, και άρα ενώ τελικά φαίνεται λάθος να είναι  σωστό...

Ποια ειναι η Chomsky που βγαζεις?

S-> XS1 | XX | Xb | bS1 | bΧ | bb | ab
S1->SX | Sb | XX | Xb | bX | bb
X-> ab

Στο S-> XS1 | XX | Xb | bS1 | bΧ | bb | ab μηπως θα επρεπε να λειπει το ab

Πλέον είναι αργά το γράφω όμως για το Φεβρουάριο :D

Δεν το έχω μπροστά μου αυτή τη στιγμή
Αν θυμάμαι καλά το θες λόγο του τελευταίου τελευταίου βήματος στο Chomsky,
για κάθε Α->BC όπου ΑeD(S)-{S} προσθέτω τον S-> BC . Και αφού έχει στο D(S)e το Χ βάζεις το κανόνα S->ab αφού Χ->ab

Υπάρχουν λύσεις από τα θέματα 2017?

Σεπτεμβριος 2017, θεμα 3 καταλαβε κανεις τι παιζει;  :o

Αρκει να αποδειξεις οτι υπαρχει μηχανη turing που την ημιαποφασιζει

ωχ θεμα 2 ηθελα να ρωτησω, μπερδευτηκα!
thanks για την απαντηση ομως  ;)

Δες 3ο pdf διαφανειών, σελ 14, 2η διαφάνεια. Με παρόμοιο τρόπο λες R₁=R₀ U (S₁ -> S₀S₀) και  V₁=V₀ U S₁

μηπως θα επρεπε να κοιταξουμε την πρωτη διαφανεια που ειναι Παραθεση και οχι το Kleene star?

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

αχαααα, ευχαριστώ!  :)

Εχει κανεις ιδεα πως βρισκουμε τομη 2 γλωσσων L(Μ) ? Σεπτεμβριος του 2016 1ο θεμα ελυσε κανεις;

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

Φεβρουαριος 2017, 1ο θεμα πρωτα δυο ερωτηματα τι απανταμε?

δεν εχω ακριβως την απαντηση, αλλα στο βιβλιο σελ 128 το 2.4.2 μπορει να βοηθησει νομιζω

1ο ερώτημα λες πως δεν είναι κανονική, αφού το m εμφανίζεται 2 φορές, δηλαδή χρειάζεται να έχουμε μνήμη.
στο 2ο λες πως είναι κανονική, αφού είναι παράθεση 2 κανονικών εκφράσεων, των L[a*] και L[b*]

https://www.youtube.com/watch?v=zEPtVIV_nbY

Αυτό μπορεί επίσης να βοηθήσει!

Μπορεί κάποιος να ανεβάσει λύσεις για τα θέματα του Φεβρουαρίου 2018;

Έχει λύσει κανείς το 2ο Φεβρουαρίου 2018?  :???:
Τί εννοεί τη μέγιστη τιμή Μ?

δεν το έλυσα ακόμη, όμως πρέπει να σχετίζεται με το λήμμα 3.5.1 σελ. 198 Παπαδημητρίου και τη μορφή του δέντρου όταν η γλώσσα είναι σε KMC

Σχεδιάζεις το δέντρο για να το καταλάβεις οπτικά.
Την ελάχιστη τιμή έχουμε όταν το δέντρο έχει τα λιγότερα δυνατά κλαδιά δηλαδή n+1 , όπου το n είναι το ύψος του δένδρου.
Τη μέγιστη τιμή την έχεις όταν το δέντρο είναι πλήρες και αυτή η τιμή είναι 2ⁿ

ααα, θένξ! ;)

λύσεις θεμάτων φεβρουαρίου 2018 κανείς??

+1

Μία πρώτη προσπάθεια για τα θέματα Φεβρουαρίου 2018
ό,τι ενστάσεις υπάρχουν, καλοδεχούμενες (κυρίως για το πρώτο θέμα)!

θέματα Σεπτεμβρίου 2018
δώστε φιντμπακ στο λαό!

Θεμα1
α) (i)  e σωστό αφού χωρίς καμία μετάβαση μπορώ να παραμείνω στο q_o

Θεμα2
Η γλώσσα είναι ασαφής. Για να'ναι σαφής οι παρενθέσεις θα έπρεπε να ήταν κάπως έτσι S=> (S + S) | (S -S) | κτλ. 
ή τα πρόσημα να ήταν μπροστά S=>+ S S | - S S | κτλ.

σε υπερευχαριστώ!

παίζει να είναι βλακεία αυτό που ρωτάω αλλά.. στο θέμα 3 του Φεβρουαρίου 2017 ζητάει να κατασκευάσουμε μηχανή turing και δίνει δύο γλώσσες:

1) L[ab*]
2) {a}* ένωση {b}

παίζει ρόλο που δίνει τις γλώσσες με διαφορετικές μορφές;

Σεπτεμβριος 18 θεμα 2β το εχει δοκιμασει κανενας/καμια με δυναμικο προγραμματισμο? πρεπει να εχω καποιο λαθος στην chomsky γιατι το πινακακι βγαινει γεματο κενα. Ωστοσο ξερω οτι S -> S*S -> (S)*(S)-> (S/S)*(S/S) -> ((S)/S)*((S)/(S)) -> ((S+S)/S)*((S-S)/(S*S)) -> ((x+y)/z)*((y-z)/(y+x)),
αρα μπορει να παραχθει απο αυτη τη γραμματικη, αρα ανηκει στην L(G)

η μετατροπή σε KMC μου βγήκε όπως το συνημμένο .. δυναμικό προγραμματισμό δεν έκανα γιατί μου βγαίνει τεράστιο

Κι εγώ αυτό έβγαλα. αλλά δεν μου βγήκε. υπαρχει κανενα άτομο αρκετά γενναίο να κάνει τον πίνακα;  ;D

Ενδεικτικά κάποια θεματα από τις παρακάτω χρονιές:

Φεβρουάριος- 18,17,16
Σεπτέμβριος - 17,16
Ιούνιος - 17,16,15

Παίζει να παρέλειψα κάποιες ασκήσεις, σίγουρα υπάρχουν λάθη και σόρρυ για το μολύβι :P

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

Ποτε μια μηχ turing αποφασιζει κ ποτε ημιαποφασιζει μια γλωσσα;;

Αποφασίζει όταν παράγει no για μη αποδεκτή w ενώ όταν απλά "κρεμάει" για μη αποδεκτη w, Δηλαδή καταλήγει σε κάποιο ατέρμων βρόγχο πχ σημαίνει ότι ημιαποφασιζει την γλώσσα. Εννοείται και στις δύο περιπτώσεις καταλήγει σε halting state όταν το w είναι αποδεκτό

+1

Ευχαριστώ  ;)

Yπάρχει κάποιος που να ξέρει με σιγουριά όταν φτιάχνουμε μηχανη turing απο ένα ΑΠΑ τι διαφορα εχει το αποφασιζει απο ημιαποφασιζει επάνω στην μηχανη turing ??

Επίσης αν έχω μια καταβόθρα και μας λέει να αποφασίζει τότε στην ΜΤ θα βάζουμε στην επομενη κατάσταση να πηγαίνει δεξιά ή να τερματίζει με (n, κενό). Γιατί αν βάζουμε να πηγαίνει δεξία όπως τα λυμενα θέματα στα downloads τότε έχω την αίσθηση ότι η μηχανή κρεμάει και άρα ουσιαστικά η ΜΤ ήμιαποφασίζει. Σωστά;

Φεβρουάριος 2019 θέμα 2ο ερώτημα 'β' το έχει λύσει κανείς?

η L(G) ΔΕΝ μπορει να υλοποιηθει απο πεπερασμεο αυτοματο αρα δεν ειναι κανονικη

Θέμα 3ο του 2019?!

+1

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

Τόσο απλό είναι; Να σαι καλά φίλε μου!

φιλος που πηρε 10 μου ειπε οτι το ελυσε ετσι

το οτι η L(G) δεν μπορει να υλοποιηθει απο ΑΠΑ πως το κανουμε?

Κανείς θέμα 3ο, Ιούνιος 2019; Ή πώς κατασκευάζεται ΜΤ που ημιαποφασιζει; Κάποια έγκυρη απάντηση;  ^beg^

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

Αν πουμε να γινει χωρις διαγραμμα καταστασεων,δεν μπορω να πω οτι διαβαζω κενο παω δεξια, αν διαβασω α ή β παω δεξια, αν διαβασω + η * επιστρεφω στο προηγουμενο σταδιο ή αν διαβασω κενο παω σε halt?

Απορία: Στον συμβολισμό L=(((ab)Ub)*a), σημαίνει ότι μπορώ να παραθέσω όπως θέλω τα σύμβολα ab και b σε μία συμβολοσειρά απλά πρέπει να κλείνει πάντα με το α. Σωστα?

Και επίσης, το e συμπεριλαμβάνεται στη γλώσσα με το συγκεκριμένο συμβολισμό ή οχι?

Ναι στην πρώτη ερώτηση και όχι στη δεύτερη γιατί αναγκαστικά πρέπει να τελειώνει με a.

ετσι οπως το γραψα παντως μου το πηρε σωστο. το δικο σου σωστο μου φαινεται απλα αν διαβασεις κενο εν τελει πας σε halt ή δεξια;

Ναι θενκς, το πιασα.

Σε τετοια θεματα δεν πρεπει να σχεδιασουμε και την μηχανη ???Δηλαδη να κανουμε την   αναπαρασταση της με τις καταστασεις και που πηγαινει σε καθε περιπτωση;;;(οπως την μηχανη αντγραφης συμβολοσειρας που υπαρχει μεσα στις διαφανειες )

Αυτό έχω γράψει απλά σε αλγεβρικο τρόπο. Τις μεταβάσεις.

φεβρουαριος_19
λυσεις , αν καποιος εχει αντιρρηση για κατι καλοδεχουμενο , ειδικα για την 1

Για το θέμα 1

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

Έχω παρατηρήσει ότι όταν χρησιμοποιείς τον αλγόριθμο ΜΑΠΑ-ΑΠΑ σου προκύπτει (πάντα??) ελάχιστο ΑΠΑ. Δεν ξέρω αν ισχύει σίγουρα αυτο που λέω, αλλα βοηθάει για επαλήθευση.

ισχυει
πιστευεις εχει μια λυση το θεμα 1 ή προτεινουμε ο καθενας καποια που να λειτουργεί?

Η λύση σου είναι σίγουρα λάθος, δοκίμασε να βάλεις συμβολοσειρές και θα το δεις. Είναι συγκεκριμένη η μεθοδολογία νομίζω, χρησιμοποιώντας ε μεταβάσεις κλπ. Εχει κατι βιντεάκια στο youtube απτη ΠΛΗ30 του  Ψούνη, δε θυμαμαι ποια βιντεο είναι ομως.

 Ξέρει κανείς πως υπολογίζεις τον αριθμό καταστάσεων του ελάχιστου ισοδύναμου ΑΠΑ? :-[

https://www.youtube.com/watch?v=0XaGAkY09Wc&t=730s

Στα θέματα Ιουνίου 2019, στο Θεμα 1i) και στο Θέμα 1iv),ποια είναι η εξήγηση;

Φλεβάρης '19, θέμα 2ο, υποερώτημα δεύτερο. Πώς δείχνουμε ότι μια γραμματική G δεν μας δίνει L[G] που είναι κανονική;
Στη συγκεκριμένη περίπτωση έχουμε R = {S -> aAa | bAb | e, A -> SS}.

Δεν κατάλαβα ακριβώς τι ρωτάς αλλά εγώ θα το πήγαινα έτσι: Αν δείξεις πως η Γραμματική από την οποία παράγεται είναι κανονική, τότε είναι και η Γλώσσα κανονική. Για να δείξεις πως μια Γραμματική είναι κανονική νομίζω πως πρέπει να έχεις στις μεταβάσεις σου ένα μη τερματικό σύμβολο αριστερά και το πολύ ένα μη τερματικό σύμβολο δεξιά. Αν στο θέμα αυτό είναι Σ = {a,b} (που μου μοιαζει και πιο νορμαλ) αντί για S = {a,b}, τότε τα μη τερματικά σου είναι το Α και το S. Άρα αφού στις μεταβάσεις, έχεις Α ->SS, δηλαδή 2 μη τερματικά στα δεξιά, νομίζω δεν είναι κανονική η γλώσσα.

Στον υπολογισμό των τελικών καταστάσεων μήπως είναι 3, αντί για 2; Νομίζω πώς οι K-F σπάνε, καθώς για b τα παιδιά τους όχι μόνο ειναι διαφορετικά, αλλά δεν είναι και 0-ισοδύναμα. Για n=0, το qo ανήκει στις F, ενώ το κενό στις K-F.

στην κανονικη μορφη chomsky  στις λυσεις του φεβ 16 στα downloads δεν θα επρεπε αφου το Ο->+|x ειναι κοντοι κανονες και δεν μενει αλλος κανονας για να κρατησει το Ο(της μορφης Ο->ΑΒ) στους τελικους κανονες για το Sενα δεν θα επρεπε να φυγουν ολοι οι κανονες που το περιεχουν?.Παρομοιο και το παραδειγμα για chomsky σελ 83 απο τις σημειωσεις 2017-2018

Το D(Ο) ισούται με {Ο, +, x}. Άρα το Ο ανήκει στο D(O) και μπορείς να το αντικαταστήσεις και με τον εαυτό του στους παρακατω κανονες. Και σε ασκηση που εκανε ο Ντελοπουλος στα τελευταια μαθηματα ετσι το παει.

Αυτό συμβαίνει επειδή αν έχουμε παραπάνω από ένα μη τερματικό σύμβολο στα δεξιά θα έχουμε "άπειρες" καταστάσεις, άρα δεν μπορεί να περιγραφεί από ένα Πεπερασμένο Αυτόματο (που έχει "λίγη" μνήμη);

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

Στο pdf με της σημειώσεις 2017-2018 στα downloads εχεί αυτό

Ευχαριστω!

Στο Θεμα 4 Ιουνιου-Ιουλιου 2015, ζητειται να βρεθουν οι σχεσεις (Μ=(Κ,Σ,δ,s,H)) μιας ΜΤ που εχει 2 καταχωρητες. Πως πρεπει να φτιαξουμε τις σχεσεις σε αυτη την περιπτωση; Αν φτιαξω μια ισοδυναμη ΜΤ χωρις καταχωρητες, γίνεται πολυ πολυπλοκο...

έχει κανείς λύσεις για Ιούνη 2019? τα ΣΛ κυρίως και το 3ο θέμα

εγώ τα ΣΛ τα έβγαλα:
i) Λ, καθώς τουλάχιστον μια σσ (πχ abbab) ανήκει στην πρώτη γλώσσα και όχι στην δεύτερη (δεν μπορεί να παράξει τα συνεχόμενα bb)
ii) Σ, αν αναλύσεις το κάθε σύνολο είναι τα ίδια άρα η διαφορά τους είναι το κενό σύνολο.
iii) Λ, γιατί δεν έχει εξωτερικό kleene star, άρα το bc μπορεί να παραχθεί αλλά το ac δεν μπορεί να το ακολουθήσει
iv) Σ, γιατί ουσιαστικά ξεκινάει με α, τελειώνει με b και ενδιάμεσα το εξωτερικό αστέρι επαναλαμβάνεται 2 φορές cd*cd* και τώρα για το πρώτο d* έχω 0 επαναλήψεις και για το δεύτερο d* 1, άρα (ccd).

Ισως υπερ-αναλύω, αλλά δεν σου λέει οτι Σ = {α,β}. Αν ειναι Σ = {α,β,c}, τότε ειναι Λ. Σκεφτόμενος κυρίως ότι χρησιμοποιεί και c,d πιο μετά νομίζω ίσως ήταν σκόπιμη παγίδα.


Συμφωνω

ωχ νόμιζα το έγραψα ::)

ίδια αιτιολόγηση έχω, Σωστό μόνο αν μας δίνει το Σ = {α,β} (που συνήθως στις ασκήσεις/παραδείγματα αυτό είναι ή το {0, 1}.)

Παίζει να έκανες το θέμα 3?

Δεν έχω φτάσει καν εκεί στην ύλη :Ρ
Θα κάνω μια προσπάθεια σε 1-2 μέρες αν δεν βρεις λύση στο ενδιάμεσο.

Η προσπάθεια μου για τον Φεβρουάριο (2020). Για πείτε καμιά γνώμη, να τα συζητήσουμε :D

edit 1: + Σεπτέμβρης 2019
edit 2: + Ιούνης 2019 και απάντηση στον ευατό μου  :D
edit 3: + Φεβρουάριος 2019

Παιδια, κανεις που μπορει να ανεβασει τις λυσεις της τωρινης εξεταστικης;

Αυτές είναι οι λύσεις μου, καλά έγραψα :P 8))

Έχουμε ένα θέμα με τα Downloads και το αρχείο δεν ανεβαίνει. Το ανεβάζω στο mega και όταν φτιάξει θα το μεταφέρω στα Downloads. Ουσιαστικά είναι τα θέματα που έλυσα, ενώ διάβαζα για να δώσω τον Ιούνη. Παίζει να υπάρχουν λάθη, καταναλώστε με δική σας ευθύνη :P ^beer^

edit: ανέβηκαν στα Downloads.

Καλησπέρα παιδιά, έχω την εξής απορία: Όταν εφαρμόζω τον αλγόριθμο δυναμικού προγραμματισμού (σε ΓΧΣ στη KMC) και το αποτέλεσμα σε ένα κελί του πίνακα περιέχει παραπάνω από ένα σύμβολο, τότε τις πράξεις που εμπεριέχεται αυτό το κελί τις υπολογίζω για όλα τα σύμβολα ή διαλέγω ένα με κάποιο κριτήριο;

Νομίζω τις υπολογίζεις όλες. Αρκεί στο τέλος να έχεις το S κάτω γωνία. Κυκλοφορεί κι ένα λυμένο τέτοιο.

Εγώ γιατί νομίζω πως σε κάθε κελί πρέπει να βρίσκεις *μία και μόνο λύση*; Είσαι σίγουρος πως υπολογίζεις τις τιμές σωστά;

Μπορεί σε κάποια από τα κελιά να βγουν 2 σύμβολα. αυτό σημαίνει ότι η γραμματική είναι ασαφής.
αν χρειαστεί το ΣΔ χρησιμοποιείς μόνο το 1 που οδηγεί στο S

Βγάζει νόημα αυτό, σωστά.

Ευχαριστώ για την διόρθωση!

Το ΣΔ το βγάζουμε απο τον πίνακα με κάποια μεθοδολογία;

Ξεκινάς από το S που εχει προκυψει στο κάτω δεξιά κελί σου και βάζεις ως παιδιά του στο δέντρο τα σύμβολα από τα οποία προέκυψε. Πχ αν είχες κανόνα S -> +S1 | xS1 και το S κατω δεξια προέκυψε από + και S1 αντίχτοιχα, θα βάλεις αυτά και πάει λέγοντας.

Ευχαριστώ!

Ναι, ουσιαστικά είχα απορία για το ΣΔ. Ευχαριστώ!

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

Νομίζω οι σελίδες 20.21 από τις σημειώσεις του Ντελόπουλου είναι αρκετά εντάξει σαν παράδειγμα. Επειδή ξεκινάει εξέταση τώρα σε 10 λεπτά, αν πέσει θα σου πρότεινα εκεί να αφοσιωθείς

παιδιά έχει μπει κανένας?

εμένα δε με έχει βάλει ακόμα

και εμένα.. λες να γεμίσει πάλι όπως σε άλλα μαθήματα?

αν κάποιος μπει ας μας ενημερώσει αν είναι εύκολο

άντε να δούμε.. του στειλα πάντως ένα μέιλ γιατι είμαι κανα 14λεπτο στο περίμενε για να τον ενημερώσω

Σεπτέμβριος 20, Θέμα 2α, δε θα έπρεπε να προστεθούν και κανόνες της μορφής  S-->ΒC για κάθε Α που ανήκει στο D(S)-{S} με A-->BC??

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

έχεις δίκιο κι εγώ όπως το λες το έλυσα

Υποχρεωτικά πρέπει να γίνει και το βήμα που λες για να καταλήξουμε στην KMC για τον ΔΠ.

Θέμα jul_sept_20 στα downloads Θέμα 1ο ερώτημα iii φωτογραφία στο link  (http://prntscr.com/z3bpg1).

Σωστό δεν είναι;

λάθος είναι η τομη είναι το αβ

α σωστά. Άρα είναι {a,b,ab} η σωστή απάντηση;

Μπορεί να είναι και κενό. Σε περίπτωση που το πρώτο ειναι β και το δεύτερο α.

νομίζω μόνο ab είναι

ναι, ισχύει. Ευχαριστώ για τη διόρθωση!
Ξέρει κανένας mod αν γίνεται να επεξεργαστούμε το ανεβασμένο αρχείο; ή να το σβήσουμε και να ξαναανεβάσω;

κι εγω αυτό νομίζω, επειδή το 'a' δεν το δέχεται η πρώτη γλώσσα που θέλει να τελειώνει με b, και το 'b' δε το δέχεται η 2η γλώσσα

Δεν είναι {αβ, ε}?

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

Αα οκ, προσπαθούσα να εκφράσω το γεγονός ότι μπορεί να μην έχουν τομή αλλά μπερδεύτηκα με το L[Ø*]={ε}(εδώ δεν έχουμε *). Ευχαριστώ

Πρακτικά όμως όντως βγαίνει και χωρίς αυτό. Μάλιστα, αν όταν δεις bT₁ , αντικαταστήσεις με το S αντί για το Τ, δε βγαίνει σωστό  :P (ή τουλάχιστον δε μου βγήκε εμένα στη συνέχεια). Σε κάθε περίπτωση πιστεύω πρέπει να υπάρχει κι ας χρησιμοποιούνται οι αρχικοί κανόνες στο πινακάκι.  ;)

Θέμα 1ο Σεπτέμβριος 20 το (iii) είναι αποδεκτό σωστά; Μόνο εμένα μου πήρε μια σελίδα πράξεις για να το αποδείξω; Και όλα αυτά για μισή μονάδα!

φώτο (http://prntscr.com/z4swpt)

Είναι αποδεκτό; Πχ για ν=2, βγαίνει; Διότι πρέπει να είναι για κάθε ν

Εγώ αυτό έκανα. Είμαι αρκετά πτώμα αλλά νομίζω δουλεύει

χμμ ναι αλλά η q0 δεν είναι τελική κατάσταση

ούτε εγώ μπόρεσα να το κάνω για ν=2

πωωωωω τζάμπα τόσος κόπος... άρα απλώς έπρεπε να κάνεις και άλλα τόσα (όλες τις δυνατές περιπτώσεις) για να δείξεις πως δεν είναι αποδεκτό; Αυτό δεν βγαίνει!

εγώ έβγαλα μόνο ότι για ν περιττό δουλεύει και για άρτιο όχι

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

αυτό φαίνεται να ισχύει, αλλά για να κάνεις κανονική απόδειξη και για τα 2, θα θες πολύ χρόνο

μόνο εγώ νομίζω πως τα θέματα του Σεπτέμβρη θέλανε άπειρη ώρα;

Στην πρώτη πορτοκαλί υπογράμμιση δεν πρέπει να υπάρχει και η ε-κίνηση q0->q2?

Εν τέλει στο Θέμα 1ο Σεπτέμβριος 20 βρήκα τα (ii) (iv) αποδεκτά. Δε ξέρω αν μου ξέφυγε κάτι.

Δεν είναι αποδεκτό το (iv). Δες:
Έχοντας διαβάσει ένα b βρίσκεσαι ή στην q1 ή στην q3. Άρα διακρίνεις 2 περιπτώσεις:
1) Είσαι στην q1 -α-> q3 ε F (δηλαδή ισχύει για n=1). Όμως μετά ο μόνος τρόπος να διαβαστεί 2ο b είναι q3 -e-> q2 -b-> q3, απ' όπου με ένα α μπορείς να βρεθείς μόνο στο q0 που δεν είναι τελική.

2) Είσαι στην q3 -e-> q2 -α-> q0 όπως πριν.

Και εμεις που δώσαμε τότε το ίδιο πιστεύαμε  :'(

Απλά μπορείς να πεις οτι διαβάζοντας έστω ένα b αυτό σημαίνει οτι είσαι στην q1 ή στην q3. Από αυτές τις καταστάσεις δεν μπορείς να οδηγηθείς στην q3 με 2α.
Και κάνεις από κάτω και τις πιθανές διαδρομες και καθάρισες. Μου πήρε 5 σειρές  ::)




ΑΣΤΑ ΝΑ ΠΑΝΕ

Και εγω αποδεκτό το βγάζω το iv στο Θεμα 1 Σεπ20.

για n=0, πας (q0,a)->(q1,a)->(q3,e)
για n=1, πας (q0,a)->(q1,a)->q(2,b)->(q3,e)
για n>1, πας (q0,a)->(q1,a)->q(2,b)->(q3,e)->(q2,b)->(q3,e)

ΩΠΑ ΠΑΙΔΙΑ!!!!!

Χίλια συγγνώμη, εγώ τα έλυνα από τα θέματα που είχα κατεβάσει το Σεπτέμβρη με το ΑΕΜ μου και είναι διαφορετικά :-P . Χαχαχαχα σορρυυυυυυυ. Αυτά είναι τα δικά μου

Κι αυτό με βάση τα δικά μου είναι, το (iii)

Έστω έχω ένα Πεπερασμένο Αυτόματο (πχ Φεβρ 18 θέμα 1ο) και έχω μια κατάσταση όπου μόνο πας και δεν φεύγεις και δεν είναι τελική (πχ q3).  Τι κάνω τότε; Αφού δεν είναι τελική κατάσταση δεν μπορεί να τελειώνει εκεί. Άρα να πάει εκεί θα μπλέξει σε ατέρμονο βρόχο??!!

Όχι βρε, μη μπερδεύεσαι. Η διαδικασία τελειώνει εκεί, απλά δεν αποδέχεται τη συμβολοσειρά που έβαλες στην είσοδο. Τελική κατάσταση (ε F) σημαίνει οτι τελειώνει ΚΑΙ αποδέχεται.

Στο θέμα 1ο του Σεπτεμβριου 2020, στο iii για n=0, βγάζω ότι δεν ισχύει, επομένως μπορώ να πω ότι καθώς δεν ισχύει για n=0, η συμβολοσειρά δεν είναι αποδεκτή σωστά?

Την είχα κι εγω αυτήν την απορία. Δεν ξέρω αν ειναι αυτονοητο το πού οριζεται το n, αν και λογικα για να μην το οριζει μαλλον θα περιλαμβανεται και το 0. Παντως ουτε για 2 ισχυει, οποτε μπορεις να το δειξεις και μ αυτο.

Στο 2ο θέμα του Ιουλίου 2020 στο α' ερώτημα εγώ έβγαλα την εξής μορφή:

S -> α | β | RS | x | SS
R -> XS
X -> -

Στις λύσεις βγάζει κάτι τελείως διαφορετικό. Βγάζει το παρακάτω:

S -> - R | xR
R -> SS | Sα | Sβ | αS | αα | αβ | βS | βα | ββ

Είναι και τα δυο σωστά; Είναι και τα 2 λάθος; Κάποια γνώμη;

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

Σε θέματα όπως το 3ο του Φεβρουαρίου 2021, που ζητάει να κατασκευάσουμε Μ Turing αλλά δίνοντας τη συνάρτηση μετάβασης δ, χρειάζεται να καλύψουμε όλες τις περιπτώσεις στη συνάρτηση; Πχ αν επιλέξω δ(s,_) = (q0, ->), ( _ = κενό) οπότε κατευθείαν φεύγω από την κατάσταση s, πρέπει να συμπεριλάβω και ποια θα είναι τα δ(s,a), δ(s,b), δ(s,|>), (|> = το τρίγωνο) στα οποία πρακτικά δεν θα χρησιμοποιήσω ποτέ;

Τι εννοείς δεν θα τα χρησιμοποιήσεις ποτέ? Πως είσαι σίγουρος ότι δεν θα γίνει δ(s,a) ?

Γιατί θεωρώ για δομή της ταινιας |> _ w  (w η συμβολοσειρα).
Ξεκιναω λοιπον απο το κενο διπλα απο το τριγωνο και το πρωτο βημα ειναι να παω δεξια αλλαζοντας κατασταση ταυτοχρονα, γι αυτο και δ(s,_)=(qo,->). Το πηρα αυτο απο τις σημειωσεις 2019 στα downloads σελιδα 79, μια ασκηση που εκαναν στην ταξη. Σε αυτην την ασκηση, στις υπολοιπες περιπτωσεις για το s εχει διπλα  στις δ xxxx και αναρωτιομουν αν οντως ειναι σωστο να μην τα ορισουμε. Με βαση τον ορισμο που επελεξε στην ασκηση, παντως, δεν βγαζει και νοημα να τα ορισεις καπως, μιας και μοιαζουν αχρηστες περιπτωσεις.

Επισυναπτω την ασκηση

Φεβ 2018 μπορει καποιος να μου εξηγηση πως λυνεται το θεμα 1ο ερωτημα β και στην περιπτωσει που δεν ειναι ειδη ελαχιστο τι κανουμε?
Δηλαδη ολη την διαδικασια.

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

Μπορείς να μου την περιγράψεις με κάποιο παράδειγμα όπως αυτό παραπάνω και ένα διαφορετικό που θέλει περισσότερη ανάλυση.

https://www.thmmy.gr/smf/index.php?action=tpmod;dl=item5781

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

Τελεια με καλυψε
Οσον αφορα το θεμα 3ο τον φεβ 2018 που θελουμε την ΓΧΣ να την κανουμε σε Κανονικη  μορφη Chomsky οταν παμε να διωξουμε τα κενα δεν καταλαβα ετσι οπως το εξηγει με το Ε .. και πως απαλείφονται και τι προσθετο στο τελος του 2ου βηματος.
Μπορεις να με βοηθησεις;

Ίσως βοηθήσει αυτό. Το έχω όπως το καταλαβαίνω ίσως να μην είναι και σωστά  :D

Τελεια σε ευχαριστω πολυ.
Στα θεματα Σεπτ. 2018 θεμα 2ο ερωτημα β μπορει να λυθει με Δ.Π. κανοντας το πινακι και βλεποντας αν στο n[1,Ν] = S οπου Ν = |w|  , μπορουμε να πουμε οτι ανηκει στην Γλωσσα L(G)?
Η πρεπει πρωτα να το κανουμε σε κανονικη μορφη Chmosky και μετα τα υπολοιπα?

Αν θες να το κάνεις με δυναμικό προγραμματισμό αναγκαστικά θες chomsky . Το συγκεκριμενο πιστευω αρκεί να βρεις ένα συντακτικό δεντρο να το φτιάχνει . Το ξεκινάς απο κάτω αφού πρακτικά η συμβολοσειρά είναι τα φύλλα του δέντρου και το χτίζεις προς τα πάνω μεχρι να φτάσεις σε ένα S

Ναι οντως
Σε ευχαριστω πολυ

Φεβ 17
Θεμα 3ο εχει κανεις λυσης

Υπαρχει διαφορα μεταξυ R1 = ab και R1 = {(a)U (b) }

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

Σωστος ειχα κολλησει
Σε ευχαριστω πολυ!

εχει λυσει κανεις τα θεματα του Φλεβαρη (2022);

Μπορεί κανείς να μου εξηγήσει πως βρίσκει τους κανονες και το επεκτεταμενο αλφάβητο στο 2ο θεμα του Φλεβαρη του 2021; Ποια βήματα ακολουθεί;