THMMY.gr

Μαθήματα Κύκλου Ηλεκτρονικής & Υπολογιστών => Θεωρία Υπολογισμών και Αλγορίθμων => Topic started by: dim on July 19, 2005, 01:30:58 am



Title: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: dim on July 19, 2005, 01:30:58 am
Εδώ μπορείτε να σχολιάζετε τα θέματα και
να συζητάτε τις όποιες απορίες σας πάνω σε παλιά θέματα της
Θεωρίας Υπολογισμών και Αλγορίθμων.
(Τα παλιά θέματα υπάρχουν εδώ (http://www.thmmy.gr/index.php?option=com_docman&task=cat_view&gid=179&Itemid=45)).


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Ariel on February 20, 2010, 15:20:46 pm
Έχει λύσει κανείς το θέμα 3 του Φεβρουαρίου 2008?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: vasso on February 05, 2011, 21:08:49 pm
Ta themata fetos itan teleia :)

agapame Ntelo!


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: lpool on February 06, 2011, 00:07:27 am
Ta themata fetos itan teleia :)

agapame Ntelo!

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: vasso on February 06, 2011, 00:13:08 am
Ta themata fetos itan teleia :)

agapame Ntelo!

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

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


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



Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Sage on February 17, 2013, 10:49:58 am
Πιάνοντας τα πρώτα μου θέματα(Σεπτέμβρη 2003).. μου δημιουργήθηκαν κάποιες απορίες.

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

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

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



Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: aggalitsas on February 17, 2013, 15:30:50 pm
Πιάνοντας τα πρώτα μου θέματα(Σεπτέμβρη 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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Sage on February 17, 2013, 16:43:39 pm
Πιάνοντας τα πρώτα μου θέματα(Σεπτέμβρη 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.. αυτο δεν νομίζω οτι είναι κ μεγάλο πρόβλημα. Οπότε και να μην διευκρινιστεί δεν υπάρχει θέμα. ;)


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: aggalitsas on February 17, 2013, 17:33:09 pm
μπορέι κάποιος να λύσει το  θεμα 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

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





Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: nikos912000 on February 17, 2013, 22:07:57 pm
Στο θέμα 3 Ιανουάριος 2002 υπάρχει απλός τρόπος για το β (ΜΑΠΑ->ΑΠΑ); Γιατί ο αλγόριθμος γενικά θέλει δουλειά!


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: soso on February 17, 2013, 23:21:11 pm
-Ιανουάριος 2003 Θέμα 1ο είναι Λ,Σ,Σ,Λ,Σ,Σ?

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

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

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

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: nikos912000 on February 17, 2013, 23:30:33 pm

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


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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Sage on February 18, 2013, 01:17:03 am
Στο θέμα 3 Ιανουάριος 2002 υπάρχει απλός τρόπος για το β (ΜΑΠΑ->ΑΠΑ); Γιατί ο αλγόριθμος γενικά θέλει δουλειά!
Έχω στο συνημμένο την λύση(πιστεύω οτι είναι σωστή)..

-Ιανουάριος 2003 Θέμα 1ο είναι Λ,Σ,Σ,Λ,Σ,Σ?
Λ,Σ,Σ,Λ,Λ,Λ Τα έβαλα, χωρίς να είμαι απόλυτος.
Πάντως αν ίσχυε το v) τότε δε θα καθόταν να αποδείξει στο βιβλίο σε τόσες σελίδες πως η έκφραση anbn δεν είναι κανονική.

-Σεπτέμβριος 2003 Θέμα 2ο (vi)?
Και γω το χω απορία..

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

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

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

-Φεβρουάριος 2009, Θέμα 3ο, (δ) τί εννοεί αν είναι σαφής?
Δεν ασχολήθηκα ακόμα με τα καινούρια θέματα, μόνο με του 11(τα παλούκια).
Αύριο πρωί με τα υπόλοιπα..


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Sage on February 18, 2013, 10:54:56 am
μπορέι κάποιος να λύσει το  θεμα 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

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: τσαι-borg on February 18, 2013, 11:09:52 am
Μια ερώτηση μιας και το έγραψες, αφού S->e και X->e, S1->SX δεν είναι προς το κενό?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Sage on February 18, 2013, 11:27:54 am
Μια ερώτηση μιας και το έγραψες, αφού S->e και X->e, S1->SX δεν είναι προς το κενό?
Και 'γω έτσι το σκεφτόμουν στην αρχή, αλλά νομίζω είναι λάθος γιατί S και Χ μεταβαίνουν και σε άλλες καταστάσεις και αν το κάνεις αυτό λογικά θα χαθούν. Αν δεις και στο παράδειγμα στις διαφάνειες, S->SS αλλά S->e παρόλα αυτά η πρώτη μετάβαση παραμένει.. ;)
Καλύτερα, αν υπάρχει άτομο που πατούσε στα μαθήματα, να μας το πεί αν το εξήγησε ο Ντελο.


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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: τσαι-borg on February 18, 2013, 11:37:47 am
https://www.thmmy.gr/smf/index.php?topic=47966.msg849220#msg849220 (https://www.thmmy.gr/smf/index.php?topic=47966.msg849220#msg849220)


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: nikos912000 on February 18, 2013, 12:00:58 pm

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


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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Sage on February 18, 2013, 12:17:18 pm
Νομίζω πως η λύση του α είναι Όχι,Ναι,Ναι,Όχι,
Γιατί αυτή η έκφραση, στο εσωτερικό της σημαίνει ή θα έχουμε μόνο ένα α ή κενό(λόγω β) ή παράθεση του β. Και ότι προκύψει σε παράθεση.. άρα, δέχεται μόνο κενό ή α(παράθεση) ή β(παράθεση).

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: nikos912000 on February 18, 2013, 12:27:59 pm
Δε νομίζω... Μπορεί να γραφτεί ούτως ή άλλως (a*ένωσηb*)*... Η παράθεση πάει σε ολόκληρη την ένωση... :(


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: DoomGuard on February 18, 2013, 12:31:33 pm

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

Νομίζω έχεις ένα λαθάκι (εκεί που βγάζεις q1,q3 είναι q1,q2)... Αλλά και 'γω με αυτή τη λογική το λύνω...

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

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

Δε νομίζω... Μπορεί να γραφτεί ούτως ή άλλως (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)


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: nikos912000 on February 18, 2013, 12:49:52 pm

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

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


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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: DoomGuard on February 18, 2013, 12:58:59 pm

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

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


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

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: nikos912000 on February 18, 2013, 13:03:57 pm
Αν μιλάμε για το ίδιο θέμα (θέμα 3 Ιανουάριος 02), η q1 πηγαίνει και στη 2 και στην 3 με b (έχεις διπλή μετάβαση)... Anyway, καταλαβαίνω τι λες και όντως σε αρκετά προβλήματα μπορείς να δουλέψεις έτσι...Thnx!
Κάτι πιο θεωρητικό, στον αλγόριθμο ΜΑΠΑ->ΑΠΑ τις καταστάσεις που βγαίνουν "κενές" (από τα δ που υπολογίζουμε) τις βάζουμε κανονικά στο διάγραμμα και τις μετράμε σαν καταστάσεις (μπορούν βέβαια να συμπτυχθούν σε μία κενή);


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: DoomGuard on February 18, 2013, 13:15:13 pm
Ουπς.. Τα μπέρδεψα.

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

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: nikos912000 on February 18, 2013, 14:08:09 pm
Κάτι τελευταίο... Στο θέμα 3 του 11 η wcw θα είναι συμμετρική, ή πχ μπορεί να είναι aacbb (μάλλον το πρώτο βέβαια); Για το α ερώτημα τι μπορούμε να πούμε;


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: DoomGuard on February 18, 2013, 14:15:30 pm
Κάτι τελευταίο... Στο θέμα 3 του 11 η wcw θα είναι συμμετρική, ή πχ μπορεί να είναι aacbb (μάλλον το πρώτο βέβαια); Για το α ερώτημα τι μπορούμε να πούμε;

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: nikos912000 on February 18, 2013, 14:19:13 pm
Ok...thnx και πάλι...


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: cav on February 07, 2014, 17:24:41 pm
Έχει λύσει κανείς το 2ο Θέμα Γενάρη '12?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Chester on February 07, 2014, 18:20:54 pm
τα θεματα που λυνετε βασίζονται πανω σε παραδείγματα του βιβλιου; γιατι δεν εχω βρει πουθενα ασκησεις λυμμενες. εκτος αν εχει κανει τιποτα μεσα στην αιθουσα.


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Ragnar on February 01, 2015, 20:39:33 pm
παιδιά τι παίζει με το θέμα 2 του 2/2013?  :D


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Exomag on February 01, 2015, 20:51:36 pm
παιδιά τι παίζει με το θέμα 2 του 2/2013?  :D

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Ragnar on February 01, 2015, 21:57:56 pm
βασικα αφου στο αυτόματο που μας έδωσε δεν μπορούμε να επισκεφθούμε όλες τις καταστάσεις! αρα δεν ειναι αιτοκρατικό νμζ δλδ. πχ εκεί που λέει κανονική έκφραση ποία είναι? η  βααβ? τετοιο εννοεί? και επίσης στο τελευταίο για το αυτόματο δημιουργούμε δικία μας συμβολοσειρά? δεν ξέρω με έχει μπερδέψει λίγο αυτή .....


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: SolidSNK on February 01, 2015, 22:04:31 pm
παιδιά τι παίζει με το θέμα 2 του 2/2013?  :D
Το α) δεν είναι τόσο προφανές. Γενικά αν τυχαίνει κάποιου είδους άρνηση από το FSA, όπως εδώ που σου λέει: "μετά το ba δε θα δεχτώ αμέσως κι άλλο ba" τα πράγματα περιπλέκονται (π.χ. βιβλίο σελ. 82). Εμένα μου βγήκε κάτι σε a*(a*baa)*((ba)Ua*). Το 3ο θέμα είναι πιο ενδιαφέρον (άμα θες να κάνεις αυστηρά σωστές αποδείξεις).

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: τσαι-borg on February 01, 2015, 23:42:11 pm
παιδιά τι παίζει με το θέμα 2 του 2/2013?  :D
Το α) δεν είναι τόσο προφανές. Γενικά αν τυχαίνει κάποιου είδους άρνηση από το FSA, όπως εδώ που σου λέει: "μετά το ba δε θα δεχτώ αμέσως κι άλλο ba" τα πράγματα περιπλέκονται (π.χ. βιβλίο σελ. 82). Εμένα μου βγήκε κάτι σε a*(a*baa)*((ba)Ua*). Το 3ο θέμα είναι πιο ενδιαφέρον (άμα θες να κάνεις αυστηρά σωστές αποδείξεις).


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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: SolidSNK on February 02, 2015, 00:00:41 am
παιδιά τι παίζει με το θέμα 2 του 2/2013?  :D
Το α) δεν είναι τόσο προφανές. Γενικά αν τυχαίνει κάποιου είδους άρνηση από το FSA, όπως εδώ που σου λέει: "μετά το ba δε θα δεχτώ αμέσως κι άλλο ba" τα πράγματα περιπλέκονται (π.χ. βιβλίο σελ. 82). Εμένα μου βγήκε κάτι σε a*(a*baa)*((ba)Ua*). Το 3ο θέμα είναι πιο ενδιαφέρον (άμα θες να κάνεις αυστηρά σωστές αποδείξεις).


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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Ex_Mechanus on February 02, 2015, 01:05:55 am
Επίσης το a*(a*baa)*((ba)Ua*) δεν μπορεί να παράξει το baabaaaabaaaa πχ το οποίο κάνει δεκτό το αυτόματο. a*(a*baa)*(((baaa*)*)Ua*) μήπως?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: SolidSNK on February 02, 2015, 01:10:36 am
Επίσης το a*(a*baa)*((ba)Ua*) δεν μπορεί να παράξει το baabaaaabaaaa πχ το οποίο κάνει δεκτό το αυτόματο. a*(a*baa)*(((baaa*)*)Ua*) μήπως?
Τι λες, μια χαρά μπορεί. Χαζέ.

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: SolidSNK on February 02, 2015, 01:11:57 am
1ον αυτό. Και 2ον εσύ δέχεσαι συμβολοσειρές που τελειώνουν σε ba (που θα έπρεπε)?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: SolidSNK on February 02, 2015, 01:16:34 am
Μμμ νομίζω τώρα καλύτερα: a*(a*baaa*)*((ba)Ua*)



Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Ex_Mechanus on February 02, 2015, 01:23:13 am
Σωστός αυτό σκεφτόμουν, μαλακία έγραψα.


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: τσαι-borg on February 02, 2015, 23:20:39 pm
Εκτιμητέα οποιαδήποτε ιδέα για Φεβρουάριο 2014, θέμα 2, ερώτημα β.


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: SolidSNK on February 03, 2015, 00:26:09 am
Το γενικό πρόβλημα της ασάφειας μιας γραμματικής είναι άλυτο, αλλά στην περίπτωση μας ο Ντελό μπορεί να καλύπτεται από το παρακάτω.

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Lord on February 03, 2015, 04:33:22 am
Εμένα μου βγήκε κάτι σε a*(a*baa)*((ba)Ua*). Το 3ο θέμα είναι πιο ενδιαφέρον (άμα θες να κάνεις αυστηρά σωστές αποδείξεις).


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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: SolidSNK on February 03, 2015, 05:24:14 am
Εμένα μου βγήκε κάτι σε a*(a*baa)*((ba)Ua*). Το 3ο θέμα είναι πιο ενδιαφέρον (άμα θες να κάνεις αυστηρά σωστές αποδείξεις).


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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Tracy_McGrady on February 03, 2015, 13:15:41 pm
Μμμ νομίζω τώρα καλύτερα: a*(a*baaa*)*((ba)Ua*)


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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: princess_of_the_dawn on February 03, 2015, 16:59:53 pm
στα θέματα 2/2011 στο θέμα 3β-πώς κατασκευάζουμε τη μηχανή;
γενικά μπορεί κάποιος να πει έτσι πρόχειρα πώς κατασκευάζουμε τη μηχανή;


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: SolidSNK on February 03, 2015, 17:03:15 pm
Μμμ νομίζω τώρα καλύτερα: a*(a*baaa*)*((ba)Ua*)


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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Tracy_McGrady on February 03, 2015, 17:08:48 pm
Μμμ νομίζω τώρα καλύτερα: a*(a*baaa*)*((ba)Ua*)


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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Niobe on September 23, 2015, 14:13:09 pm
Γιατι ετσι σημερα?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: L on September 23, 2015, 14:45:26 pm
Γιατι ετσι σημερα?
Βατά θέματα, λίγος χρόνος. Ξύπνησε στραβά ο Ντελό;


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Niobe on September 23, 2015, 14:56:01 pm
Γιατι ετσι σημερα?
Βατά θέματα, λίγος χρόνος. Ξύπνησε στραβά ο Ντελό;
Υποθετω... Και η αλλαγη θεματος στο μισαωρο ηταν καλη φαση


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: TrueForce on September 23, 2015, 15:24:52 pm
Τα θεματα ηταν βατα, ναι. Γενικα τα θυα ειναι ευκολο μαθημα αλλά ήταν πιο δυσκολα απο αλλες φορες. Ή καλύτερα, ΠΟΛΥ πιο χρονοβόρα από άλλες χρονιές.

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Dealan on September 23, 2015, 15:27:28 pm

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Niobe on September 23, 2015, 15:33:59 pm
Πραγματικα με ενα μισαωρο παραπανω θα ηταν μια χαρα...
Δε μπορω να καταλαβω τη λογικη πραγματικα..


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: L on September 23, 2015, 15:46:52 pm
Δε μπορω να καταλαβω τη λογικη πραγματικα..
Ο Ντελό είναι ΜΑΠΑ  :D


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: megali mpougatsa on September 23, 2015, 15:50:35 pm
ΑΑΑ λίγα τα λόγια σου για τον θεούλη!!  :D  Είναι ΑΠΑ και βάλε !!!  :D


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Exomag on September 23, 2015, 15:51:10 pm
Μηχανή Turing ρε! ;D


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: L on September 23, 2015, 15:51:32 pm
ΑΑΑ λίγα τα λόγια σου για τον θεούλη!!  :D  Είναι ΑΠΑ και βάλε !!!  :D
Μα κάθε ΑΠΑ είναι ΜΑΠΑ  :P


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Exomag on September 23, 2015, 15:54:27 pm
ΑΑΑ λίγα τα λόγια σου για τον θεούλη!!  :D  Είναι ΑΠΑ και βάλε !!!  :D
Μα κάθε ΑΠΑ είναι ΜΑΠΑ  :P

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Niobe on September 23, 2015, 15:59:56 pm
ΑΑΑ λίγα τα λόγια σου για τον θεούλη!!  :D  Είναι ΑΠΑ και βάλε !!!  :D
Μα κάθε ΑΠΑ είναι ΜΑΠΑ  :P

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: RFed the King on February 01, 2016, 13:27:46 pm
Πως βρησκουμε οτι μια γραμματικη ειναι ασαφης?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: RFed the King on February 01, 2016, 13:30:06 pm
Πως βρησκουμε οτι μια γραμματικη ειναι ασαφης?

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: AckermanMik on February 01, 2016, 13:40:41 pm
Ακριβώς!


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: greekoo on February 06, 2016, 17:48:45 pm
Πως βρησκουμε οτι μια γραμματικη ειναι ασαφης?

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: antoniat on February 06, 2016, 19:42:46 pm
δεν μπορουμε απλα να δειξουμε οτι υπαρχουν δυο παραγωγες που δεν ειναι ομοιες μεταξυ τους για την ασαφεια??


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Exomag on February 06, 2016, 19:43:41 pm
δεν μπορουμε απλα να δειξουμε οτι υπαρχουν δυο παραγωγες που δεν ειναι ομοιες μεταξυ τους για την ασαφεια??

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: antoniat on February 06, 2016, 19:48:14 pm
δεν μπορουμε απλα να δειξουμε οτι υπαρχουν δυο παραγωγες που δεν ειναι ομοιες μεταξυ τους για την ασαφεια??

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: mapalo on February 07, 2016, 02:08:00 am
Πως αποδεικνύουμε ότι μια γραμματική είναι σαφής? (βλ. θέμα 2β, Σεπτ. 2015)


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: antoniat on February 07, 2016, 18:45:15 pm
μπορεί κάποιος να μου εξηγήσει το θέμα 3 φεβρουάριος του 11??


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: AckermanMik on February 07, 2016, 18:47:55 pm
μπορεί κάποιος να μου εξηγήσει το θέμα 3 φεβρουάριος του 11??

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: antoniat on February 07, 2016, 20:00:01 pm
μπορεί κάποιος να μου εξηγήσει το θέμα 3 φεβρουάριος του 11??

Ουσιαστικά στο πρώτο ερώτημα σου λέει να δείξεις ότι η γλώσσα είναι αναδρομικά απαριθμήσιμη. Τρέχα γύρευε δηλαδή. Απλά φτιάξε τη μηχανή τιουρινγκ κατευθειαν και έχεις αποδείξει και το πρώτο ερώτημα.
απλα ξερεις τι δεν καταλαβαινω...λεει y=wcw ..αυτο το w ειναι ιδιο πριν και μετα το c? δηλαδη εχει μνημη η μηχανη??η καθε φορα ειναι διαφορετικο πριν και μετα το c??ελπίζω να έγινα κατανοητη..


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: AckermanMik on February 07, 2016, 20:02:35 pm
μπορεί κάποιος να μου εξηγήσει το θέμα 3 φεβρουάριος του 11??

Ουσιαστικά στο πρώτο ερώτημα σου λέει να δείξεις ότι η γλώσσα είναι αναδρομικά απαριθμήσιμη. Τρέχα γύρευε δηλαδή. Απλά φτιάξε τη μηχανή τιουρινγκ κατευθειαν και έχεις αποδείξει και το πρώτο ερώτημα.
απλα ξερεις τι δεν καταλαβαινω...λεει y=wcw ..αυτο το w ειναι ιδιο πριν και μετα το c? δηλαδη εχει μνημη η μηχανη??η καθε φορα ειναι διαφορετικο πριν και μετα το c??ελπίζω να έγινα κατανοητη..

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: antoniat on February 07, 2016, 20:17:03 pm
μπορεί κάποιος να μου εξηγήσει το θέμα 3 φεβρουάριος του 11??

Ουσιαστικά στο πρώτο ερώτημα σου λέει να δείξεις ότι η γλώσσα είναι αναδρομικά απαριθμήσιμη. Τρέχα γύρευε δηλαδή. Απλά φτιάξε τη μηχανή τιουρινγκ κατευθειαν και έχεις αποδείξει και το πρώτο ερώτημα.
απλα ξερεις τι δεν καταλαβαινω...λεει y=wcw ..αυτο το w ειναι ιδιο πριν και μετα το c? δηλαδη εχει μνημη η μηχανη??η καθε φορα ειναι διαφορετικο πριν και μετα το c??ελπίζω να έγινα κατανοητη..

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: AckermanMik on February 07, 2016, 20:18:03 pm
μπορεί κάποιος να μου εξηγήσει το θέμα 3 φεβρουάριος του 11??

Ουσιαστικά στο πρώτο ερώτημα σου λέει να δείξεις ότι η γλώσσα είναι αναδρομικά απαριθμήσιμη. Τρέχα γύρευε δηλαδή. Απλά φτιάξε τη μηχανή τιουρινγκ κατευθειαν και έχεις αποδείξει και το πρώτο ερώτημα.
απλα ξερεις τι δεν καταλαβαινω...λεει y=wcw ..αυτο το w ειναι ιδιο πριν και μετα το c? δηλαδη εχει μνημη η μηχανη??η καθε φορα ειναι διαφορετικο πριν και μετα το c??ελπίζω να έγινα κατανοητη..

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: antoniat on February 07, 2016, 20:21:26 pm
μπορεί κάποιος να μου εξηγήσει το θέμα 3 φεβρουάριος του 11??

Ουσιαστικά στο πρώτο ερώτημα σου λέει να δείξεις ότι η γλώσσα είναι αναδρομικά απαριθμήσιμη. Τρέχα γύρευε δηλαδή. Απλά φτιάξε τη μηχανή τιουρινγκ κατευθειαν και έχεις αποδείξει και το πρώτο ερώτημα.
απλα ξερεις τι δεν καταλαβαινω...λεει y=wcw ..αυτο το w ειναι ιδιο πριν και μετα το c? δηλαδη εχει μνημη η μηχανη??η καθε φορα ειναι διαφορετικο πριν και μετα το c??ελπίζω να έγινα κατανοητη..

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: SolidSNK on February 07, 2016, 21:24:48 pm
μπορεί κάποιος να μου εξηγήσει το θέμα 3 φεβρουάριος του 11??

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: antoniat on February 07, 2016, 22:34:04 pm
μπορεί κάποιος να μου εξηγήσει το θέμα 3 φεβρουάριος του 11??

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: κύριος Φασόλης on February 09, 2016, 12:14:29 pm
απο τα θεματα του φεβρουαριου του 2015:

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: et3rn1ty on February 09, 2016, 12:39:28 pm
απο τα θεματα του φεβρουαριου του 2015:

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

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

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: κύριος Φασόλης on February 09, 2016, 12:52:54 pm
απο τα θεματα του φεβρουαριου του 2015:

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

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

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

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

thanks :)

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Λήσταρχος Γιαγκούλας on February 09, 2016, 13:14:10 pm
Καλημέρα,
έχει δει κανείς το ερώτημα β του 2ου θέματος Σεπτ15;

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: κύριος Φασόλης on February 09, 2016, 14:17:42 pm
ΦΕΒ 2014

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: nvog1993 on February 09, 2016, 14:23:02 pm
Καλημέρα,
έχει δει κανείς το ερώτημα β του 2ου θέματος Σεπτ15;

Yποψιάζομαι πως η γραμματική είναι ΣΑΦΗΣ αλλα δεν ξέρω πως να το αποδείξedit :
Mαλλον ΑΣΑΦΗΣ είναι.Βασίζομαι στην υπόθεση ότι το +ab μπορεί να προέλθει είτε από +SX είτε από +XS τα οποία έρχονται από +SS.
Σωστά;
Δεν νομίζω, γιατί αν κάνεις το δέντρο πάλι και τα δύο S πρέπει να καταλήξουν σε Χ σε κάποια φάση. Το ότι η γραμμή από το S μέχρι το Χ θα είναι μεγαλύτερη μια στο ένα S, μια στο άλλο, δεν έχει σημασία. Πάλι το ίδιο δέντρο θα έχεις. Πιστεύω είναι ΣΑΦΗΣ αλλά το πως το αποδεικνύεις, δεν έχω ίδεα :/


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Λήσταρχος Γιαγκούλας on February 09, 2016, 14:27:39 pm
Καλημέρα,
έχει δει κανείς το ερώτημα β του 2ου θέματος Σεπτ15;

Yποψιάζομαι πως η γραμματική είναι ΣΑΦΗΣ αλλα δεν ξέρω πως να το αποδείξedit :
Mαλλον ΑΣΑΦΗΣ είναι.Βασίζομαι στην υπόθεση ότι το +ab μπορεί να προέλθει είτε από +SX είτε από +XS τα οποία έρχονται από +SS.
Σωστά;
Δεν νομίζω, γιατί αν κάνεις το δέντρο πάλι και τα δύο S πρέπει να καταλήξουν σε Χ σε κάποια φάση. Το ότι η γραμμή από το S μέχρι το Χ θα είναι μεγαλύτερη μια στο ένα S, μια στο άλλο, δεν έχει σημασία. Πάλι το ίδιο δέντρο θα έχεις. Πιστεύω είναι ΣΑΦΗΣ αλλά το πως το αποδεικνύεις, δεν έχω ίδεα :/
To σκέφτομαι όπως στην σελ.177(lewis-παπαδημητρίου).Εκεί φαίνεται να έχει σημασία η σειρά των αλλαγών δεξιά αριστερά.Ας δώσει και κάποιος άλλος τα φώτα του.


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Λήσταρχος Γιαγκούλας on February 09, 2016, 14:28:56 pm
Επιπλεόν απ'ότι βλέπω σε άλλα τοπικ'σ φαίνεται να τους έχει δώσει κάποια διόρθωση στο θέμα αυτό.Αναμένουμε αν κάποιος που το έδωσε θυμάται.


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: κύριος Φασόλης on February 09, 2016, 14:46:21 pm
Καλημέρα,
έχει δει κανείς το ερώτημα β του 2ου θέματος Σεπτ15;

Yποψιάζομαι πως η γραμματική είναι ΣΑΦΗΣ αλλα δεν ξέρω πως να το αποδείξedit :
Mαλλον ΑΣΑΦΗΣ είναι.Βασίζομαι στην υπόθεση ότι το +ab μπορεί να προέλθει είτε από +SX είτε από +XS τα οποία έρχονται από +SS.
Σωστά;
Δεν νομίζω, γιατί αν κάνεις το δέντρο πάλι και τα δύο S πρέπει να καταλήξουν σε Χ σε κάποια φάση. Το ότι η γραμμή από το S μέχρι το Χ θα είναι μεγαλύτερη μια στο ένα S, μια στο άλλο, δεν έχει σημασία. Πάλι το ίδιο δέντρο θα έχεις. Πιστεύω είναι ΣΑΦΗΣ αλλά το πως το αποδεικνύεις, δεν έχω ίδεα :/
To σκέφτομαι όπως στην σελ.177(lewis-παπαδημητρίου).Εκεί φαίνεται να έχει σημασία η σειρά των αλλαγών δεξιά αριστερά.Ας δώσει και κάποιος άλλος τα φώτα του.

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Λήσταρχος Γιαγκούλας on February 09, 2016, 14:48:38 pm

                                                 S                                  S
                                                 |                                    |
                                               S+S                              S + S
                                               |    |                               /      \
                                               a+S+S                       S+S + S
                                               |   |    |                        |    |      |
                                               a + b  + a                   a+b   + a
Ελα ρε παιχταρα,στο α ερώτημα και γω το ίδιο έκανα  :D


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: κύριος Φασόλης on February 09, 2016, 14:55:33 pm

                                                 S                                  S
                                                 |                                    |
                                               S+S                              S + S
                                               |    |                               /      \
                                               a+S+S                       S+S + S
                                               |   |    |                        |    |      |
                                               a + b  + a                   a+b   + a
Ελα ρε παιχταρα,στο α ερώτημα και γω το ίδιο έκανα  :D

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: greekoo on February 09, 2016, 17:54:37 pm
απο τα θεματα του φεβρουαριου του 2015:

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

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

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

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

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: κύριος Φασόλης on February 09, 2016, 18:02:06 pm
απο τα θεματα του φεβρουαριου του 2015:

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

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

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

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

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

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: greekoo on February 09, 2016, 18:14:20 pm
Mπορεί κάποιος μια και καλή να απαντήσει στις ερωτήσεις του τύπου: "Να αποδείξετε ότι το σύνολο των αναδρομικa απαριθμήσιμο γλωσσών είναι κλειστό ως προς ένωση,παράθεση κλπ;; " 

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: κύριος Φασόλης on February 09, 2016, 18:52:42 pm
Mπορεί κάποιος μια και καλή να απαντήσει στις ερωτήσεις του τύπου: "Να αποδείξετε ότι το σύνολο των αναδρομικa απαριθμήσιμο γλωσσών είναι κλειστό ως προς ένωση,παράθεση κλπ;; " 

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

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

+1


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Λήσταρχος Γιαγκούλας on February 09, 2016, 22:53:00 pm
+@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))


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: isitsou on February 09, 2016, 23:53:38 pm
Έγινε μια συζήτηση για αυτό το ερώτημα στο "[Θ.Υ.Α.] Γενικές απορίες και ανακοινώσεις/επικαιρότητα 2015-2016". Ρίξε μια ματιά εκεί αν θες, νομίζω ότι αυτό που έγραψα στα λυμένα θέματα είναι τελικά σωστό.


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: isitsou on February 10, 2016, 00:00:31 am

                                                 S                                  S
                                                 |                                    |
                                               S+S                              S + S
                                               |    |                               /      \
                                               a+S+S                       S+S + S
                                               |   |    |                        |    |      |
                                               a + b  + a                   a+b   + a
Ελα ρε παιχταρα,στο α ερώτημα και γω το ίδιο έκανα  :D

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

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Andromedas on February 10, 2016, 00:01:28 am
Έγινε μια συζήτηση για αυτό το ερώτημα στο "[Θ.Υ.Α.] Γενικές απορίες και ανακοινώσεις/επικαιρότητα 2015-2016". Ρίξε μια ματιά εκεί αν θες, νομίζω ότι αυτό που έγραψα στα λυμένα θέματα είναι τελικά σωστό.
Είναι σωστό βάση του θεωρήματος  myhill Nerode σελ 138 και επειδή το απα που σχεδιάσαμε είναι το ελάχιστο άρα κλάσεις ισοδυναμίας της L είναι οι καταστάσεις του Μ   (αφού είναι οι ελάχιστες).
Νομίζω ότι το έχω καταλάβει σωστά αν δεν ισχύει πείτε τπτ


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Eilex on February 10, 2016, 11:08:08 am
μπορεί κάποιος να μου εξηγήσει το θέμα 3 φεβρουάριος του 11??


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

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Niobe on February 10, 2016, 12:47:03 pm
Εχει κανεις τελειωμενο το θεμα 2 φλεβαρης '15??

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Κηπουρίδης on February 10, 2016, 13:03:14 pm
Mπορεί κάποιος μια και καλή να απαντήσει στις ερωτήσεις του τύπου: "Να αποδείξετε ότι το σύνολο των αναδρομικa απαριθμήσιμο γλωσσών είναι κλειστό ως προς ένωση,παράθεση κλπ;; "  

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

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

+1

Οι συγκεκριμενες ερωτησεις ειναι οι πιο δυσκολες ερωτησεις κλειστοτητας που μπορουν να πεσουν, κι αυτο γιατι ειναι πιθανο η αντιστοιχη 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 θα αποδεχομασταν, αλλιως δε θα αποδεχομασταν.


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: SolidSNK on February 10, 2016, 13:13:33 pm
μπορεί κάποιος να μου εξηγήσει το θέμα 3 φεβρουάριος του 11??


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

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

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: SolidSNK on February 10, 2016, 13:21:52 pm
Mπορεί κάποιος μια και καλή να απαντήσει στις ερωτήσεις του τύπου: "Να αποδείξετε ότι το σύνολο των αναδρομικa απαριθμήσιμο γλωσσών είναι κλειστό ως προς ένωση,παράθεση κλπ;; "  

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

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

+1

Οι συγκεκριμενες ερωτησεις ειναι οι πιο δυσκολες ερωτησεις κλειστοτητας που μπορουν να πεσουν, κι αυτο γιατι ειναι πιθανο η αντιστοιχη 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 θα αποδεχομασταν, αλλιως δε θα αποδεχομασταν.

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

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

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



Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Κηπουρίδης on February 10, 2016, 13:27:15 pm

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

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

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


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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Andromedas on February 10, 2016, 13:27:39 pm
Εχει κανεις τελειωμενο το θεμα 2 φλεβαρης '15??

Επισης αν μπορει να εξηγησει καποιος την εξαλειψη κοντων κανονων  για ΚΜC
Με επιφύλαξη για το α)
θεμα 2 φλεβαρης '15


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Κηπουρίδης on February 10, 2016, 13:30:16 pm
Εχει κανεις τελειωμενο το θεμα 2 φλεβαρης '15??

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Niobe on February 10, 2016, 13:33:26 pm
Ποσο περηφανος θα ηταν ο Turing για σας ρε μαγκες...  ;D ;D


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Andromedas on February 10, 2016, 13:38:42 pm
Η λογική μου φαίνεται σωστή. Αρκεί όμως για όλο το σύνολο των αναδρομικά απαριθμησιμων γλωσσών; Η εννοεί για τις αναδ απαρ από το συγκεκριμένο Σ;
Αν γίνεται να ανεβάσεις τις ΜΤ που χρησιμοποιριε για κάθε μια ενωση, παραθεση, Kleene  συγκεκριμένα θα βοηθούσε.

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Κηπουρίδης on February 10, 2016, 13:46:14 pm
Η λογική μου φαίνεται σωστή. Αρκεί όμως για όλο το σύνολο των αναδρομικά απαριθμησιμων γλωσσών; Η εννοεί για τις αναδ απαρ από το συγκεκριμένο Σ;
Αν γίνεται να ανεβάσεις τις ΜΤ που χρησιμοποιριε για κάθε μια ενωση, παραθεση, Kleene  συγκεκριμένα θα βοηθούσε.

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

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

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: SolidSNK on February 10, 2016, 13:52:20 pm

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

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

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


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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Andromedas on February 10, 2016, 13:55:21 pm
πχ   2014 φεβρουαριος θεμα 2 διαισθάνομαι ότι είναι σαφής αλλά δεν μπορώ να το πω με κάποια διατύπωση
Υ.Γ.: Δεν καταλαβα τι ειπες με τις διαφανειες, δε νομιζω να εχει ανεβασμενο κατι σχετικο ο Ντελο.
είπα για διαφάνειες κάτι;


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Κηπουρίδης on February 10, 2016, 14:01:59 pm
Όχι, δεν προυποθέτω ότι τα ΤΜ θα τερματίσουν.

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: SolidSNK on February 10, 2016, 14:24:55 pm
Όχι, δεν προυποθέτω ότι τα ΤΜ θα τερματίσουν.

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Κηπουρίδης on February 10, 2016, 14:31:21 pm
πχ   2014 φεβρουαριος θεμα 2 διαισθάνομαι ότι είναι σαφής αλλά δεν μπορώ να το πω με κάποια διατύπωση
Υ.Γ.: Δεν καταλαβα τι ειπες με τις διαφανειες, δε νομιζω να εχει ανεβασμενο κατι σχετικο ο Ντελο.
είπα για διαφάνειες κάτι;
Απλως παιρνουμε το κειμενο που θελουμε να ελεγξουμε αν ανηκει στη γραμματικη, βλεπουμε το πρωτο γραμμα του, και αντικαθιστουμε το S με τη μοναδικη παραγωγη που γενναει σαν πρωτο γραμμα αυτο που θελουμε (ευκολη η αποδειξη οτι μονο αυτη η επιλογη στεκει). Συνεχιζουμε με αυτο τον τροπο και αποδεχομαστε μονο εαν τελειωσουμε το κειμενο ΚΑΙ τελειωσουμε και τα S ταυτοχρονα.

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Andromedas on February 10, 2016, 15:17:29 pm
Θεμα 3 φλεβαρης 13
Τσεκάρετε άμα ισχύει η λύση μου ,ο τύπος για τις κλάσεις κανονικών γλωσσών είναι στην σελ 83 παπα
Πλσ ποστ για διορθώσεις. Ευχαριστώ!


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Niobe on February 10, 2016, 15:32:49 pm
Το θεμα 2β του Φλεβαρη '14 ειναι ιδιο με το 2β του Σεπτεμβρη '15

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Andromedas on February 10, 2016, 15:37:23 pm
Το θεμα 2β του Φλεβαρη '14 ειναι ιδιο με το 2β του Σεπτεμβρη '15

Εχει κανεις καμια ιδεα για το πως λυνονται?? Γενικα πως εξεταζω οτι μια γραμματικη ειναι ασαφης
Φλεβαρη '14 ειναι ιδιο με το 2β του Σεπτεμβρη '15 ειναι το ιδιο
Απαντήθηκε παραπάνω.


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Niobe on February 10, 2016, 16:21:52 pm
Το θεμα 2β του Φλεβαρη '14 ειναι ιδιο με το 2β του Σεπτεμβρη '15

Εχει κανεις καμια ιδεα για το πως λυνονται?? Γενικα πως εξεταζω οτι μια γραμματικη ειναι ασαφης
Φλεβαρη '14 ειναι ιδιο με το 2β του Σεπτεμβρη '15 ειναι το ιδιο
Απαντήθηκε παραπάνω.

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Andromedas on February 10, 2016, 16:27:19 pm

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Niobe on February 10, 2016, 16:33:32 pm

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

GG

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: MrsHofstadter on September 08, 2016, 15:51:18 pm
Παιδιά, στο θέμα 2/Φεβρουάριος 2013, όταν ζητάει να σχεδιάσουμε αυτόματο στοίβας που αποδέχεται τη γλώσσα L και μας έχει δώσει και το ΜΑΠΑ για την L, πώς βρίσκουμε το αυτόματο στοίβας; Υπάρχει κάπου συγκεκριμένα στη θεωρία ο τρόπος;


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: WatchDog on September 30, 2016, 13:29:35 pm
Παίδες μήπως μπορεί να βοηθήσει κανείς με το 1ο θέμα της εξέτασης του ιουλίου που  μας πέρασε?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: jimPster on September 30, 2016, 13:45:37 pm
αμα  ανεβασεις το θεμα μπορει...


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: WatchDog on September 30, 2016, 13:52:22 pm
Αυτό ειναι το θέμα το οποίο δυσκόλεψε πολλα παιδιά στην εξέταση


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: jimPster on September 30, 2016, 14:00:37 pm
ωραια μιας κ θ ασχοληθω απο αυριο περιγραμματικα απ αυτα που θυμαμαι:

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: verisign on September 30, 2016, 14:10:44 pm
Καλό θα ήταν τα θέματα που έχετε (και δεν υπάρχουν ήδη ανεβασμένα) να τα ανεβάζετε στα downloads  ;)  8))


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: nvog1993 on September 30, 2016, 14:15:22 pm
@WatchDog, αν έχεις τα θέματα ολοκληρωμένα, ανέβασε τα πλζ.


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: WatchDog on September 30, 2016, 14:38:16 pm
Μέχρι να ανέβουν στα downloads


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: nvog1993 on October 01, 2016, 12:46:46 pm
Παίδες μήπως μπορεί να βοηθήσει κανείς με το 1ο θέμα της εξέτασης του ιουλίου που  μας πέρασε?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: nvog1993 on October 01, 2016, 15:37:56 pm
Θέμα 2ο και 3ο Ιουνιου 2016


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Maylo on October 01, 2016, 18:18:09 pm
Παιδιά έχουμε λύση για το θέμα 2ο Φλεβάρης 2002 ? κυρίως για το β)


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: WatchDog on October 02, 2016, 13:43:50 pm


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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: nvog1993 on October 02, 2016, 13:56:21 pm
Μου βγαίνουν 2 καταστάσεις παραπάνω . Είσαι σίγουρος για τη λύση?
Αρκετά σίγουρος. Έλεγξα ποιες λέξεις διαβάζει και ποιες όχι και μου φάνηκε σωστό. Αν θες, ανέβασε και το δικό σου να δω μηπως όντως έχω κάποιο λάθος.


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: RFed the King on October 02, 2016, 14:10:48 pm
ιουλιος 2016 και απο εμενα το εχω κανει λιγο πιο γρηγορα το πρωτο θεμα και θελω να μου πειτε αμα σασ φαινεται αυθαιρετο
Συμφωνα με μια φιλη μου που το εκανε καπως ετσι (η οποια το ειχε σωστο) εβγαινε σε αυτην κατευθειαν ελαχιστο


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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: RFed the King on October 02, 2016, 15:42:25 pm
θεμα 2ο 2005?
θεμα 3ο  β 2005?????
Θεμα 4ο 2005 β ολοοοο?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: nvog1993 on October 02, 2016, 16:18:44 pm
θεμα 2ο 2005?
θεμα 3ο  β 2005?????
Θεμα 4ο 2005 β ολοοοο?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: giwrgosbg on October 03, 2016, 08:30:21 am
2/2013 θεμα 3ο το γ κανεις; κάποιος που έχει γράψει ολοκληρωμένη λυση ας το ανεβασει αν μπορεί


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: nvog1993 on October 03, 2016, 11:31:10 am
2/2013 θεμα 3ο το γ κανεις; κάποιος που έχει γράψει ολοκληρωμένη λυση ας το ανεβασει αν μπορεί
Πρέπει να αποδείξεις ότι ξεκινώντας με δύο αναδρομικά απαριθμήσιμες γλώσσες και εφαρμόζοντας τις σχέσεις Ενωση, Παραθεση και Kleene Star, θα καταλήξεις πάλι σε αναδρομικά απαριθμήσιμη γλώσσα. Γενικά οι αποδείξεις αυτές βγαίνουν βρίσκοντας μηχανές Turing που (ημι)αποφασίζουν την εκάστοτε γλώσσα. Για παράδειγμα, για τη γλώσσα (L1 Ένωση L2) , μπορούμε να πούμε ότι η μηχανή που την αποφασίζει είναι μια η οποία ξεκινάει με την μηχανή της L1. Αν δεν τερματίσει αυτή, πηγαίνει πίσω την ταινία στην αρχή της λέξης με μια βασική μηχανή L και συνεχίζει με τη μηχανή της L2. Άρα και η ένωση αναδρομικά απαριθμήσιμων γλωσσών παράγει αναδρομικά απαριθμήσιμη γλώσσα.

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

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: WatchDog on October 03, 2016, 15:05:51 pm
Σεπτέμβριος 12 Θέμα 3 το έχει λύσει κάποιος ?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: nvog1993 on October 03, 2016, 15:33:30 pm
Σεπτέμβριος 12 Θέμα 3 το έχει λύσει κάποιος ?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: WatchDog on October 03, 2016, 16:25:28 pm


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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: nvog1993 on October 03, 2016, 16:32:07 pm
Αυτή η λύση πως σου φαίνεται?
Νομίζω το 2ο είναι λάθος. Η γλώσσα ουσιαστικα δέχεται οποιαδήποτε λέξη, αρκεί να αρχίζει με α, αφού κάθε λέξη είναι παραθεση των λέξεων, {α, αβ, αββ..} κλπ. Από τη στιγμή που έχει αρχίσει με α, μετά μπορείς να βάλεις ας πουμε οσα β θες και όσα α, αφού η α ανήκει στη γλώσσα και όλα τα β θα ακολουθούνται πάντα από τουλάχιστον ένα α.


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Λήσταρχος Γιαγκούλας on October 03, 2016, 16:37:43 pm
Αυτή η λύση πως σου φαίνεται?

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: WatchDog on October 03, 2016, 16:46:33 pm
Έχεις δίκιο , μη το κοιτάς . Όπως έιπε  nvog1993 ειναι λάθος το β'.Δες τη λύση του παιδιού καλύτερα.


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: nvog1993 on October 03, 2016, 17:24:18 pm
Στο β' μπορείς να εξηγήσεις λίγο τις καταστάσεις  S2,q0,q1?

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Kthulu on February 07, 2017, 23:22:17 pm
{w / w = anbn , n μη αρνητικός ακέραιος} ⊆ L( (a*b*) )

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: TrueForce on February 07, 2017, 23:33:11 pm
Χωρίς να είμαι σίγουρη, παίζει να ισχύει επειδή στην L ανήκουν οι εκφράσεις του στυλ aaabbbbb με όλους τους πιθανούς συνδυασμούς για το ποσα a και b έχεις. Στην anbn έχεις ίδιο αριθμό a και b. Βέβαια νομίζω το anbn δεν ειναι κανονική έκφραση, δεν ξέρω αν έχει να κάνει αυτό. Σκατα, μαλλον πιο πολυ σε μπέρδεψα, αλλα τα ΣΛ του ντελο ειναι πολύ tricky.


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Kthulu on February 07, 2017, 23:37:00 pm
Χωρίς να είμαι σίγουρη, παίζει να ισχύει επειδή στην L ανήκουν οι εκφράσεις του στυλ aaabbbbb με όλους τους πιθανούς συνδυασμούς για το ποσα a και b έχεις. Στην anbn έχεις ίδιο αριθμό a και b. Βέβαια νομίζω το anbn δεν ειναι κανονική έκφραση, δεν ξέρω αν έχει να κάνει αυτό. Σκατα, μαλλον πιο πολυ σε μπέρδεψα, αλλα τα ΣΛ του ντελο ειναι πολύ tricky.
Γι αυτο ακριβως το λεω. το προφανες θα ηταν το σωστο. Αλλα αυτη η εκφραση προυποθετει να εχουμε μνημη. ή δε μας νοιαζει;


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: TrueForce on February 07, 2017, 23:40:13 pm
Γι αυτο ακριβως το λεω. το προφανες θα ηταν το σωστο. Αλλα αυτη η εκφραση προυποθετει να εχουμε μνημη. ή δε μας νοιαζει;
Η λογική μου μου λέει ότι ρωτάει καθαρά αν αυτή η έκφραση είναι υποσύνολο της άλλης. Εγώ θα απάνταγα σωστό, γιατί να μας νοιάζει το ότι πρέπει να έχουμε μνήμη; Αλλά ναι, δεν είμαι καθόλου σίγουρη...


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: TrueForce on February 08, 2017, 00:14:41 am
Που διαβάζετε αυτά τα περίεργα σχετικά με αν μια γλώσσα είναι κανονική. Ξέρω ότι μπορώ να ψάξω τα slides αλλά θα μου γλίτωνε χρόνο αν κάποιος που θυμάται μου έλεγε που βρίσκονται.


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Vlassis on February 08, 2017, 00:16:43 am
Που διαβάζετε αυτά τα περίεργα σχετικά με αν μια γλώσσα είναι κανονική. Ξέρω ότι μπορώ να ψάξω τα slides αλλά θα μου γλίτωνε χρόνο αν κάποιος που θυμάται μου έλεγε που βρίσκονται.
1ο μέρος, σελ. 21 αυτα δε λες;


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: TrueForce on February 08, 2017, 00:19:48 am
1ο μέρος, σελ. 21 αυτα δε λες;
Many thanks bretha, η πρώτη μου γρήγορη απόπειρα να το βρω απέτυχε άσχημα μάλλον. Αυτα ελεγα. ;)


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: raptalex on February 08, 2017, 00:31:29 am
{w / w = anbn , n μη αρνητικός ακέραιος} ⊆ L( (a*b*) )

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: DarkPassenger on February 08, 2017, 01:23:06 am
Στα λυμένα θέματα του Σεπτ 2014, κατα πόσο σωστή πιστεύετε είναι η ασκ 1β και ποια είναι η μεθοδολογία επίλυσης της??


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: nikos1 on February 08, 2017, 10:24:47 am
Καλημερα, γνωριζετε πως ελεγχουμε αν δυο συμβολοσειρες ειναι ισοδυναμες ? (π.χ. να ελεγξω αν abb = Lbba)


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: matzaris on February 08, 2017, 11:50:35 am
Καλημερα, γνωριζετε πως ελεγχουμε αν δυο συμβολοσειρες ειναι ισοδυναμες ? (π.χ. να ελεγξω αν abb = Lbba)
Αν καταλήξουν σε ισοδύναμες καταστάσεις, τότε είναι και αυτές ισοδύναμες.


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: dimikara on July 01, 2017, 14:41:31 pm
έχει κανείς λύσεις από τα θέματα φλεβάρη '17?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: dimikara on July 01, 2017, 18:04:00 pm
Νομίζω εδώ είναι πιο σωστό να ρωτήσω.... Έχει κανείς λύσεις από Φλεβάρη '17?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: raptalex on July 19, 2017, 14:28:16 pm
Κάποιος τα θέματα του Ιουνίου 17;;


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: TrueForce on July 19, 2017, 17:51:37 pm
Κάποιος τα θέματα του Ιουνίου 17;;
ειχε λιγο κοσμο, μιση Α5 με σειρα παρα σειρα.
εκτιμώ ότι αφού δεν ανέβηκαν ήδη δεν προγδφγ δφγδφγδ-----------

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Vlassis on September 16, 2017, 18:07:42 pm
ποια ειναι η διαφορα οταν μας ζηταει μια μηχανη turing να αποφασιζει μια γλωσσα και οταν ζηταει να ημιαποφασιζει τη γλωσσα; π.χ. Ιουνιου '17 , γιατι δεν εχω βρει παρομοιο λυμένο


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: SemAn on September 16, 2017, 18:33:29 pm
ποια ειναι η διαφορα οταν μας ζηταει μια μηχανη turing να αποφασιζει μια γλωσσα και οταν ζηταει να ημιαποφασιζει τη γλωσσα; π.χ. Ιουνιου '17 , γιατι δεν εχω βρει παρομοιο λυμένο

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: raptalex on September 16, 2017, 22:51:26 pm
Αποφασίζει σημαίνει ότι η μηχανη σου έχει δυο halting states (yes or no) που τερματιζει στην κατασταση yes αν η γλώσσα ειναι αποδεκτή και no αν δεν ειναι.

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: stavridisdim on September 17, 2017, 11:54:44 am
Ξερει κανεις πως χρησιμοποιουμε το θεωρημα της αντλησης για τις κανονικες γλωσσες??


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: raptalex on September 17, 2017, 12:13:18 pm
Ξερει κανεις πως χρησιμοποιουμε το θεωρημα της αντλησης για τις κανονικες γλωσσες??

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Vlassis on September 17, 2017, 17:50:16 pm
εχει λυσει κανεις το 3ο θεμα απο Σεπτεμβριο 2016;


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: raptalex on September 17, 2017, 18:03:07 pm
εχει λυσει κανεις το 3ο θεμα απο Σεπτεμβριο 2016;

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Aristos on September 17, 2017, 19:05:43 pm
Ξερει κανεις πως χρησιμοποιουμε το θεωρημα της αντλησης για τις κανονικες γλωσσες??

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: τεκίλα_αλάτι_λεμόνι on September 18, 2017, 12:18:34 pm
Έχει σχεδιάσει κανείς την turing του ιουνιου 2017? και αν ναι μπορει να το εξηγήσει?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: raptalex on September 18, 2017, 12:28:39 pm
Μια προσπάθεια είναι αυτη..


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: thanospr on September 18, 2017, 18:05:44 pm
Θεμα 2ο Ιουνιου 17 το ελυσε καποιος?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: raptalex on September 18, 2017, 20:48:15 pm
Θεμα 2ο Ιουνιου 17 το ελυσε καποιος?
Μόνο εμένα δεν με αφήνει να  την περιστρέψω;;  :o


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: raptalex on September 18, 2017, 20:54:59 pm
Στο 1ο θέμα  του Φεβ 14 που λέει το (γ) πως το απαντάμε;;

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: ori0ngel on September 18, 2017, 22:32:08 pm
φεβρουαριος 2017, θεμα 2ο.
Για να δειξω στο α ερωτημα οτι ειναι ασαφης μπορω να το κανω με δεντρα.

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: BADBANE on September 18, 2017, 23:54:36 pm
Σε ερωτήσεις τύπου: ''Πόσες καταστάσεις έχει το ελάχιστο ΑΠΑ που είναι ισοδύναμο προς Μ'', τι απαντάμε ;


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: raptalex on September 19, 2017, 11:50:16 am
φεβρουαριος 2017, θεμα 2ο.
Για να δειξω στο α ερωτημα οτι ειναι ασαφης μπορω να το κανω με δεντρα.

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

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

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

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



Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: dimikara on September 19, 2017, 13:01:57 pm
Σε ερωτήσεις τύπου: ''Πόσες καταστάσεις έχει το ελάχιστο ΑΠΑ που είναι ισοδύναμο προς Μ'', τι απαντάμε ;

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Vlassis on September 19, 2017, 13:26:01 pm
Στο 1ο θέμα  του Φεβ 14 που λέει το (γ) πως το απαντάμε;;

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: ori0ngel on September 19, 2017, 14:43:20 pm
Εχει λυσει κανενας Σεπτεμβριο 2016?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: raptalex on September 19, 2017, 14:57:41 pm
Εχει λυσει κανενας Σεπτεμβριο 2016?
Μόνο το β..
νομιζω οτι αφου και με την w1 και με την w2 καταληγεις στην ιδια κατασταση, θα ισχυει η σχεση αυτη

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: ori0ngel on September 19, 2017, 14:59:59 pm
Ποια ειναι η Chomsky που βγαζεις?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: raptalex on September 19, 2017, 15:10:20 pm
Ποια ειναι η Chomsky που βγαζεις?

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: alex_95_ on September 19, 2017, 15:57:37 pm
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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: raptalex on September 19, 2017, 20:03:30 pm
Στο S-> XS1 | XX | Xb | bS1 | bΧ | bb | ab μηπως θα επρεπε να λειπει το ab

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: dimikara on January 28, 2018, 20:03:30 pm
Υπάρχουν λύσεις από τα θέματα 2017?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Vlassis on February 05, 2018, 21:02:23 pm
Σεπτεμβριος 2017, θεμα 3 καταλαβε κανεις τι παιζει;  :o


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: ori0ngel on February 05, 2018, 22:20:54 pm
Αρκει να αποδειξεις οτι υπαρχει μηχανη turing που την ημιαποφασιζει


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Vlassis on February 05, 2018, 22:37:33 pm
ωχ θεμα 2 ηθελα να ρωτησω, μπερδευτηκα!
thanks για την απαντηση ομως  ;)


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Kthulu on February 05, 2018, 22:52:09 pm
ωχ θεμα 2 ηθελα να ρωτησω, μπερδευτηκα!
thanks για την απαντηση ομως  ;)
Δες 3ο pdf διαφανειών, σελ 14, 2η διαφάνεια. Με παρόμοιο τρόπο λες R1=R0 U (S1 -> S0S0) και  V1=V0 U S1


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Vlassis on February 06, 2018, 21:26:55 pm
Δες 3ο pdf διαφανειών, σελ 14, 2η διαφάνεια. Με παρόμοιο τρόπο λες R1=R0 U (S1 -> S0S0) και  V1=V0 U S1
μηπως θα επρεπε να κοιταξουμε την πρωτη διαφανεια που ειναι Παραθεση και οχι το Kleene star?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Argirios on February 06, 2018, 23:38:54 pm
στο δυναμικό προγραμματισμό δεν έχω καταλάβει πως ακριβώς βάζουμε τιμή σε ένα κελί. Πρέπει όλη η συμβολοσειρά που ξεκινάει από αριστερά και τελειώνει πάνω, συνεχόμενα, να μπορεί να παραχθεί, ή μία από τις δύο συμβολοσειρές(αριστερή και πάνω)?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Argirios on February 07, 2018, 00:18:01 am
Κοιτας μονο το πρωτο συμβολο που συναντας οταν πας απο το τετραγωνο που εισαι προς τα αριστερα και προς τα πανω. Μετα βλεπεις απο ποιο συμβολο παραγεται ο συνδιασμος τους (πχ αν εχεις A αριστερα, Β πανω και υπαρχει κανονας S->AB, τοτε βαζεις S).
αχαααα, ευχαριστώ!  :)


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: manoulia on February 07, 2018, 00:29:23 am
Εχει κανεις ιδεα πως βρισκουμε τομη 2 γλωσσων L(Μ) ? Σεπτεμβριος του 2016 1ο θεμα ελυσε κανεις;


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: tardsuck on February 07, 2018, 00:52:05 am
Νομίζω τομή δυο γλωσσών είναι απλά οι εκφράσεις που γίνονται αποδεκτές και από τις δύο γλώσσες. Άρα για το θέμα που λες το ερώτημα β φαντάζομαι είναι σωστό.


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: ori0ngel on February 07, 2018, 00:58:07 am
Φεβρουαριος 2017, 1ο θεμα πρωτα δυο ερωτηματα τι απανταμε?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Vlassis on February 07, 2018, 01:25:42 am
Φεβρουαριος 2017, 1ο θεμα πρωτα δυο ερωτηματα τι απανταμε?
δεν εχω ακριβως την απαντηση, αλλα στο βιβλιο σελ 128 το 2.4.2 μπορει να βοηθησει νομιζω


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Kthulu on February 07, 2018, 01:27:22 am
1ο ερώτημα λες πως δεν είναι κανονική, αφού το m εμφανίζεται 2 φορές, δηλαδή χρειάζεται να έχουμε μνήμη.
στο 2ο λες πως είναι κανονική, αφού είναι παράθεση 2 κανονικών εκφράσεων, των L[a*] και L[b*]


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: HAL 9000 on February 07, 2018, 02:08:58 am
Φεβρουαριος 2017, 1ο θεμα πρωτα δυο ερωτηματα τι απανταμε?

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: kaspas on June 02, 2018, 19:49:20 pm
Μπορεί κάποιος να ανεβάσει λύσεις για τα θέματα του Φεβρουαρίου 2018;


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Argirios on June 20, 2018, 21:18:24 pm
Έχει λύσει κανείς το 2ο Φεβρουαρίου 2018?  :???:
Τί εννοεί τη μέγιστη τιμή Μ?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Spiro on June 20, 2018, 22:32:28 pm
δεν το έλυσα ακόμη, όμως πρέπει να σχετίζεται με το λήμμα 3.5.1 σελ. 198 Παπαδημητρίου και τη μορφή του δέντρου όταν η γλώσσα είναι σε KMC


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Kthulu on June 21, 2018, 17:19:35 pm
Έχει λύσει κανείς το 2ο Φεβρουαρίου 2018?  :???:
Τί εννοεί τη μέγιστη τιμή Μ?
Σχεδιάζεις το δέντρο για να το καταλάβεις οπτικά.
Την ελάχιστη τιμή έχουμε όταν το δέντρο έχει τα λιγότερα δυνατά κλαδιά δηλαδή n+1 , όπου το n είναι το ύψος του δένδρου.
Τη μέγιστη τιμή την έχεις όταν το δέντρο είναι πλήρες και αυτή η τιμή είναι 2n


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Argirios on June 21, 2018, 17:25:29 pm
Σχεδιάζεις το δέντρο για να το καταλάβεις οπτικά.
Την ελάχιστη τιμή έχουμε όταν το δέντρο έχει τα λιγότερα δυνατά κλαδιά δηλαδή n+1 , όπου το n είναι το ύψος του δένδρου.
Τη μέγιστη τιμή την έχεις όταν το δέντρο είναι πλήρες και αυτή η τιμή είναι 2n
ααα, θένξ! ;)


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: mpotstyl on August 26, 2018, 11:53:26 am
λύσεις θεμάτων φεβρουαρίου 2018 κανείς??


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: squawker on September 16, 2018, 18:05:57 pm
λύσεις θεμάτων φεβρουαρίου 2018 κανείς??
+1


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: ΒruteΦorce_attack on January 22, 2019, 19:49:39 pm
Μία πρώτη προσπάθεια για τα θέματα Φεβρουαρίου 2018
ό,τι ενστάσεις υπάρχουν, καλοδεχούμενες (κυρίως για το πρώτο θέμα)!


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: ΒruteΦorce_attack on January 23, 2019, 17:14:39 pm
θέματα Σεπτεμβρίου 2018
δώστε φιντμπακ στο λαό!


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: link97 on February 03, 2019, 14:17:08 pm
θέματα Σεπτεμβρίου 2018

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: ΒruteΦorce_attack on February 03, 2019, 16:01:08 pm
Θεμα1
α) (i)  e σωστό αφού χωρίς καμία μετάβαση μπορώ να παραμείνω στο qo
Θεμα2
Η γλώσσα είναι ασαφής. Για να'ναι σαφής οι παρενθέσεις θα έπρεπε να ήταν κάπως έτσι S=> (S + S) | (S -S) | κτλ. 
ή τα πρόσημα να ήταν μπροστά S=>+ S S | - S S | κτλ.

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: link97 on February 04, 2019, 00:56:42 am
Φεβρουαριος 2018


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: ΒruteΦorce_attack on February 05, 2019, 19:46:16 pm
παίζει να είναι βλακεία αυτό που ρωτάω αλλά.. στο θέμα 3 του Φεβρουαρίου 2017 ζητάει να κατασκευάσουμε μηχανή turing και δίνει δύο γλώσσες:

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Κονσερβοκούτης on February 05, 2019, 19:46:33 pm
Σεπτεμβριος 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)



Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: ΒruteΦorce_attack on February 05, 2019, 20:10:32 pm
Σεπτεμβριος 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 μου βγήκε όπως το συνημμένο .. δυναμικό προγραμματισμό δεν έκανα γιατί μου βγαίνει τεράστιο


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Κονσερβοκούτης on February 05, 2019, 20:37:18 pm
η μετατροπή σε KMC μου βγήκε όπως το συνημμένο .. δυναμικό προγραμματισμό δεν έκανα γιατί μου βγαίνει τεράστιο
Κι εγώ αυτό έβγαλα. αλλά δεν μου βγήκε. υπαρχει κανενα άτομο αρκετά γενναίο να κάνει τον πίνακα;  ;D


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: link97 on February 05, 2019, 23:33:59 pm
Ενδεικτικά κάποια θεματα από τις παρακάτω χρονιές:

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: kokkinos drakos ths zhxal on June 22, 2019, 19:53:03 pm
εχει κανεις λυμμενο τον δυναμικο προγραμματισμο του φλεβαρη 19?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: asteridp on June 23, 2019, 21:24:46 pm
Ποτε μια μηχ turing αποφασιζει κ ποτε ημιαποφασιζει μια γλωσσα;;


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: pesto80 on June 23, 2019, 22:08:28 pm
Αποφασίζει όταν παράγει no για μη αποδεκτή w ενώ όταν απλά "κρεμάει" για μη αποδεκτη w, Δηλαδή καταλήγει σε κάποιο ατέρμων βρόγχο πχ σημαίνει ότι ημιαποφασιζει την γλώσσα. Εννοείται και στις δύο περιπτώσεις καταλήγει σε halting state όταν το w είναι αποδεκτό


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: dinis on June 24, 2019, 09:41:57 am
εχει κανεις λυμμενο τον δυναμικο προγραμματισμο του φλεβαρη 19?

+1


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: pesto80 on June 24, 2019, 10:31:41 am
+1



Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: dinis on June 24, 2019, 13:35:43 pm


Ευχαριστώ  ;)


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: pesto80 on June 24, 2019, 14:13:06 pm
Yπάρχει κάποιος που να ξέρει με σιγουριά όταν φτιάχνουμε μηχανη turing απο ένα ΑΠΑ τι διαφορα εχει το αποφασιζει απο ημιαποφασιζει επάνω στην μηχανη turing ??

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: spoun on June 24, 2019, 22:15:52 pm
Φεβρουάριος 2019 θέμα 2ο ερώτημα 'β' το έχει λύσει κανείς?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: pesto80 on June 24, 2019, 22:57:49 pm
Φεβρουάριος 2019 θέμα 2ο ερώτημα 'β' το έχει λύσει κανείς?


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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: ilektraem on June 25, 2019, 10:36:10 am
Θέμα 3ο του 2019?!


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: spoun on June 25, 2019, 12:52:51 pm
Θέμα 3ο του 2019?!

+1


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: ChampionsNet on June 25, 2019, 12:56:00 pm
Θέμα 3ο του 2019?!

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: pesto80 on June 25, 2019, 13:42:19 pm
Θέμα 3ο του 2019?!


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: ChampionsNet on June 25, 2019, 14:03:14 pm
Τόσο απλό είναι; Να σαι καλά φίλε μου!


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: pesto80 on June 25, 2019, 14:19:37 pm
Τόσο απλό είναι; Να σαι καλά φίλε μου!

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: kokkinos drakos ths zhxal on June 25, 2019, 14:22:39 pm
το οτι η L(G) δεν μπορει να υλοποιηθει απο ΑΠΑ πως το κανουμε?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: duchess on September 17, 2019, 02:27:15 am
Κανείς θέμα 3ο, Ιούνιος 2019; Ή πώς κατασκευάζεται ΜΤ που ημιαποφασιζει; Κάποια έγκυρη απάντηση;  ^beg^


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: pesto80 on September 17, 2019, 11:16:34 am
Κανείς θέμα 3ο, Ιούνιος 2019; Ή πώς κατασκευάζεται ΜΤ που ημιαποφασιζει; Κάποια έγκυρη απάντηση;  ^beg^

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: kokkinos drakos ths zhxal on September 17, 2019, 16:51:16 pm
Αν πουμε να γινει χωρις διαγραμμα καταστασεων,δεν μπορω να πω οτι διαβαζω κενο παω δεξια, αν διαβασω α ή β παω δεξια, αν διαβασω + η * επιστρεφω στο προηγουμενο σταδιο ή αν διαβασω κενο παω σε halt?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: nggianno on September 17, 2019, 20:28:08 pm
Απορία: Στον συμβολισμό L=(((ab)Ub)*a), σημαίνει ότι μπορώ να παραθέσω όπως θέλω τα σύμβολα ab και b σε μία συμβολοσειρά απλά πρέπει να κλείνει πάντα με το α. Σωστα?

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



Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: KG8 on September 17, 2019, 21:14:29 pm
Απορία: Στον συμβολισμό L=(((ab)Ub)*a), σημαίνει ότι μπορώ να παραθέσω όπως θέλω τα σύμβολα ab και b σε μία συμβολοσειρά απλά πρέπει να κλείνει πάντα με το α. Σωστα?

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: pesto80 on September 17, 2019, 21:37:11 pm
Αν πουμε να γινει χωρις διαγραμμα καταστασεων,δεν μπορω να πω οτι διαβαζω κενο παω δεξια, αν διαβασω α ή β παω δεξια, αν διαβασω + η * επιστρεφω στο προηγουμενο σταδιο ή αν διαβασω κενο παω σε halt?

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: nggianno on September 17, 2019, 23:17:17 pm
Ναι στην πρώτη ερώτηση και όχι στη δεύτερη γιατί αναγκαστικά πρέπει να τελειώνει με a.

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Mr Xaxas on September 18, 2019, 13:36:37 pm
95% ειναι σωστο. ισως υπαρχουν μικρολαθακια στις οριακες περιπτωσεις γτ δεν τα θυμαμαι ακριβως αλλα η φιλοσοφια ειναι ακριβως αυτη.
Σε τετοια θεματα δεν πρεπει να σχεδιασουμε και την μηχανη ???Δηλαδη να κανουμε την   αναπαρασταση της με τις καταστασεις και που πηγαινει σε καθε περιπτωση;;;(οπως την μηχανη αντγραφης συμβολοσειρας που υπαρχει μεσα στις διαφανειες )


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: pesto80 on September 18, 2019, 15:38:10 pm
Σε τετοια θεματα δεν πρεπει να σχεδιασουμε και την μηχανη ???Δηλαδη να κανουμε την   αναπαρασταση της με τις καταστασεις και που πηγαινει σε καθε περιπτωση;;;(οπως την μηχανη αντγραφης συμβολοσειρας που υπαρχει μεσα στις διαφανειες )

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: allstarabey on September 18, 2019, 16:22:49 pm
φεβρουαριος_19
λυσεις , αν καποιος εχει αντιρρηση για κατι καλοδεχουμενο , ειδικα για την 1


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: potirikolonato on September 18, 2019, 16:37:58 pm
φεβρουαριος_19
λυσεις , αν καποιος εχει αντιρρηση για κατι καλοδεχουμενο , ειδικα για την 1
Για το θέμα 1


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: allstarabey on September 18, 2019, 16:45:33 pm
Για το θέμα 1

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: potirikolonato on September 18, 2019, 16:47:45 pm
Έχω παρατηρήσει ότι όταν χρησιμοποιείς τον αλγόριθμο ΜΑΠΑ-ΑΠΑ σου προκύπτει (πάντα??) ελάχιστο ΑΠΑ. Δεν ξέρω αν ισχύει σίγουρα αυτο που λέω, αλλα βοηθάει για επαλήθευση.


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: allstarabey on September 18, 2019, 16:50:23 pm
Έχω παρατηρήσει ότι όταν χρησιμοποιείς τον αλγόριθμο ΜΑΠΑ-ΑΠΑ σου προκύπτει (πάντα??) ελάχιστο ΑΠΑ. Δεν ξέρω αν ισχύει σίγουρα αυτο που λέω, αλλα βοηθάει για επαλήθευση.
ισχυει
πιστευεις εχει μια λυση το θεμα 1 ή προτεινουμε ο καθενας καποια που να λειτουργεί?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: potirikolonato on September 18, 2019, 16:57:55 pm
Η λύση σου είναι σίγουρα λάθος, δοκίμασε να βάλεις συμβολοσειρές και θα το δεις. Είναι συγκεκριμένη η μεθοδολογία νομίζω, χρησιμοποιώντας ε μεταβάσεις κλπ. Εχει κατι βιντεάκια στο youtube απτη ΠΛΗ30 του  Ψούνη, δε θυμαμαι ποια βιντεο είναι ομως.


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: jaime on September 19, 2019, 11:24:38 am
 Ξέρει κανείς πως υπολογίζεις τον αριθμό καταστάσεων του ελάχιστου ισοδύναμου ΑΠΑ? :-[


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: koukoutek on September 19, 2019, 12:52:58 pm
Ξέρει κανείς πως υπολογίζεις τον αριθμό καταστάσεων του ελάχιστου ισοδύναμου ΑΠΑ? :-[

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: eftymak on September 19, 2019, 14:37:25 pm
Στα θέματα Ιουνίου 2019, στο Θεμα 1i) και στο Θέμα 1iv),ποια είναι η εξήγηση;


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Bojack Horseman on January 29, 2020, 14:27:28 pm
Φλεβάρης '19, θέμα 2ο, υποερώτημα δεύτερο. Πώς δείχνουμε ότι μια γραμματική G δεν μας δίνει L[G] που είναι κανονική;
Στη συγκεκριμένη περίπτωση έχουμε R = {S -> aAa | bAb | e, A -> SS}.


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: πανωλεθρία on January 29, 2020, 17:59:32 pm
Φλεβάρης '19, θέμα 2ο, υποερώτημα δεύτερο. Πώς δείχνουμε ότι μια γραμματική G δεν μας δίνει L[G] που είναι κανονική;
Στη συγκεκριμένη περίπτωση έχουμε R = {S -> aAa | bAb | e, A -> SS}.


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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: πανωλεθρία on January 29, 2020, 18:16:23 pm
Για το θέμα 1

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: lckp on January 29, 2020, 22:14:21 pm
στην κανονικη μορφη chomsky  στις λυσεις του φεβ 16 στα downloads δεν θα επρεπε αφου το Ο->+|x ειναι κοντοι κανονες και δεν μενει αλλος κανονας για να κρατησει το Ο(της μορφης Ο->ΑΒ) στους τελικους κανονες για το Sενα δεν θα επρεπε να φυγουν ολοι οι κανονες που το περιεχουν?.Παρομοιο και το παραδειγμα για chomsky σελ 83 απο τις σημειωσεις 2017-2018


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: πανωλεθρία on January 30, 2020, 10:15:55 am
στην κανονικη μορφη chomsky  στις λυσεις του φεβ 16 στα downloads δεν θα επρεπε αφου το Ο->+|x ειναι κοντοι κανονες και δεν μενει αλλος κανονας για να κρατησει το Ο(της μορφης Ο->ΑΒ) στους τελικους κανονες για το Sενα δεν θα επρεπε να φυγουν ολοι οι κανονες που το περιεχουν?.Παρομοιο και το παραδειγμα για chomsky σελ 83 απο τις σημειωσεις 2017-2018

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Bojack Horseman on January 30, 2020, 12:06:32 pm
Δεν κατάλαβα ακριβώς τι ρωτάς αλλά εγώ θα το πήγαινα έτσι: Αν δείξεις πως η Γραμματική από την οποία παράγεται είναι κανονική, τότε είναι και η Γλώσσα κανονική. Για να δείξεις πως μια Γραμματική είναι κανονική νομίζω πως πρέπει να έχεις στις μεταβάσεις σου ένα μη τερματικό σύμβολο αριστερά και το πολύ ένα μη τερματικό σύμβολο δεξιά. Αν στο θέμα αυτό είναι Σ = {a,b} (που μου μοιαζει και πιο νορμαλ) αντί για S = {a,b}, τότε τα μη τερματικά σου είναι το Α και το S. Άρα αφού στις μεταβάσεις, έχεις Α ->SS, δηλαδή 2 μη τερματικά στα δεξιά, νομίζω δεν είναι κανονική η γλώσσα.

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: τόνγκα on January 30, 2020, 15:13:22 pm
εχει κανεις καποια ιδεα ? και αν στην ουσια ρωταει το ιδιο ?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: twil on January 30, 2020, 16:37:52 pm
εχει κανεις καποια ιδεα ? και αν στην ουσια ρωταει το ιδιο ?

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: τόνγκα on January 30, 2020, 16:50:57 pm
Στο pdf με της σημειώσεις 2017-2018 στα downloads εχεί αυτό

Ευχαριστω!


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Numb3rs on January 30, 2020, 18:22:48 pm
Στο Θεμα 4 Ιουνιου-Ιουλιου 2015, ζητειται να βρεθουν οι σχεσεις (Μ=(Κ,Σ,δ,s,H)) μιας ΜΤ που εχει 2 καταχωρητες. Πως πρεπει να φτιαξουμε τις σχεσεις σε αυτη την περιπτωση; Αν φτιαξω μια ισοδυναμη ΜΤ χωρις καταχωρητες, γίνεται πολυ πολυπλοκο...


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: leukosaraphs! on May 26, 2020, 18:37:22 pm
έχει κανείς λύσεις για Ιούνη 2019? τα ΣΛ κυρίως και το 3ο θέμα

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: A Caster on May 26, 2020, 20:36:12 pm

ii) Σ, αν αναλύσεις το κάθε σύνολο είναι τα ίδια άρα η διαφορά τους είναι το κενό σύνολο.


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


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


Συμφωνω



Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: leukosaraphs! on May 26, 2020, 20:39:53 pm
Ισως υπερ-αναλύω, αλλά δεν σου λέει οτι Σ = {α,β}. Αν ειναι Σ = {α,β,c}, τότε ειναι Λ. Σκεφτόμενος κυρίως ότι χρησιμοποιεί και c,d πιο μετά νομίζω ίσως ήταν σκόπιμη παγίδα.

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

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: A Caster on May 26, 2020, 20:43:06 pm
ωχ νόμιζα το έγραψα ::)

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

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: leukosaraphs! on July 14, 2020, 12:30:48 pm
Η προσπάθεια μου για τον Φεβρουάριο (2020). Για πείτε καμιά γνώμη, να τα συζητήσουμε :D

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: boone on August 07, 2020, 17:33:44 pm
Παιδια, κανεις που μπορει να ανεβασει τις λυσεις της τωρινης εξεταστικης;


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: leukosaraphs! on August 07, 2020, 22:38:23 pm
Παιδια, κανεις που μπορει να ανεβασει τις λυσεις της τωρινης εξεταστικης;

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: leukosaraphs! on August 28, 2020, 10:30:19 am
Έχουμε ένα θέμα με τα Downloads και το αρχείο δεν ανεβαίνει. Το ανεβάζω στο mega και όταν φτιάξει θα το μεταφέρω στα Downloads. Ουσιαστικά είναι τα θέματα που έλυσα, ενώ διάβαζα για να δώσω τον Ιούνη. Παίζει να υπάρχουν λάθη, καταναλώστε με δική σας ευθύνη :P ^beer^

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: savvaska on September 16, 2020, 18:57:24 pm
Καλησπέρα παιδιά, έχω την εξής απορία: Όταν εφαρμόζω τον αλγόριθμο δυναμικού προγραμματισμού (σε ΓΧΣ στη KMC) και το αποτέλεσμα σε ένα κελί του πίνακα περιέχει παραπάνω από ένα σύμβολο, τότε τις πράξεις που εμπεριέχεται αυτό το κελί τις υπολογίζω για όλα τα σύμβολα ή διαλέγω ένα με κάποιο κριτήριο;


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: lazkonvas on September 16, 2020, 20:37:15 pm
Νομίζω τις υπολογίζεις όλες. Αρκεί στο τέλος να έχεις το S κάτω γωνία. Κυκλοφορεί κι ένα λυμένο τέτοιο.


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: laserscout on September 17, 2020, 08:49:13 am
Καλησπέρα παιδιά, έχω την εξής απορία: Όταν εφαρμόζω τον αλγόριθμο δυναμικού προγραμματισμού (σε ΓΧΣ στη KMC) και το αποτέλεσμα σε ένα κελί του πίνακα περιέχει παραπάνω από ένα σύμβολο, τότε τις πράξεις που εμπεριέχεται αυτό το κελί τις υπολογίζω για όλα τα σύμβολα ή διαλέγω ένα με κάποιο κριτήριο;

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: leukosaraphs! on September 17, 2020, 09:15:25 am
Μπορεί σε κάποια από τα κελιά να βγουν 2 σύμβολα. αυτό σημαίνει ότι η γραμματική είναι ασαφής.
αν χρειαστεί το ΣΔ χρησιμοποιείς μόνο το 1 που οδηγεί στο S
sent from mTHMMY (https://play.google.com/store/apps/details?id=gr.thmmy.mthmmy) 


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: laserscout on September 17, 2020, 09:20:49 am
Βγάζει νόημα αυτό, σωστά.

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Xplicit on September 17, 2020, 10:46:56 am
Το ΣΔ το βγάζουμε απο τον πίνακα με κάποια μεθοδολογία;


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: πανωλεθρία on September 17, 2020, 11:05:04 am
Το ΣΔ το βγάζουμε απο τον πίνακα με κάποια μεθοδολογία;

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Xplicit on September 17, 2020, 11:11:12 am
Ξεκινάς από το S που εχει προκυψει στο κάτω δεξιά κελί σου και βάζεις ως παιδιά του στο δέντρο τα σύμβολα από τα οποία προέκυψε. Πχ αν είχες κανόνα S -> +S1 | xS1 και το S κατω δεξια προέκυψε από + και S1 αντίχτοιχα, θα βάλεις αυτά και πάει λέγοντας.

Ευχαριστώ!


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: savvaska on September 17, 2020, 12:21:48 pm
Μπορεί σε κάποια από τα κελιά να βγουν 2 σύμβολα. αυτό σημαίνει ότι η γραμματική είναι ασαφής.
αν χρειαστεί το ΣΔ χρησιμοποιείς μόνο το 1 που οδηγεί στο S
sent from mTHMMY (https://play.google.com/store/apps/details?id=gr.thmmy.mthmmy) 

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: kostas145 on September 17, 2020, 15:16:56 pm
υπάρχει κανα καλο tutorial για τον δυναμικο προγραμματισμο που θελει και βαζει συνηθως μια ερωτηση; γτ απο τις σημειωσεις του δεν βγαζω ακρη


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: laserscout on September 17, 2020, 15:47:53 pm
υπάρχει κανα καλο tutorial για τον δυναμικο προγραμματισμο που θελει και βαζει συνηθως μια ερωτηση; γτ απο τις σημειωσεις του δεν βγαζω ακρη

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: achariso on September 17, 2020, 16:00:59 pm
παιδιά έχει μπει κανένας?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: savvaska on September 17, 2020, 16:01:39 pm
εμένα δε με έχει βάλει ακόμα


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: achariso on September 17, 2020, 16:02:24 pm
και εμένα.. λες να γεμίσει πάλι όπως σε άλλα μαθήματα?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: savvaska on September 17, 2020, 16:04:32 pm
αν κάποιος μπει ας μας ενημερώσει αν είναι εύκολο


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: achariso on September 17, 2020, 16:05:25 pm
άντε να δούμε.. του στειλα πάντως ένα μέιλ γιατι είμαι κανα 14λεπτο στο περίμενε για να τον ενημερώσω


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Elina97 on February 10, 2021, 19:03:51 pm
Σεπτέμβριος 20, Θέμα 2α, δε θα έπρεπε να προστεθούν και κανόνες της μορφής  S-->ΒC για κάθε Α που ανήκει στο D(S)-{S} με A-->BC??

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: tasosl on February 10, 2021, 19:12:27 pm
έχεις δίκιο κι εγώ όπως το λες το έλυσα
sent from mTHMMY (https://play.google.com/store/apps/details?id=gr.thmmy.mthmmy) 


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Sarge on February 10, 2021, 22:50:33 pm
Σεπτέμβριος 20, Θέμα 2α, δε θα έπρεπε να προστεθούν και κανόνες της μορφής  S-->ΒC για κάθε Α που ανήκει στο D(S)-{S} με A-->BC??

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: The Audacious AI on February 11, 2021, 14:32:04 pm
Θέμα jul_sept_20 στα downloads Θέμα 1ο ερώτημα iii φωτογραφία στο link  (http://prntscr.com/z3bpg1).

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: tasosl on February 11, 2021, 14:43:57 pm
Θέμα jul_sept_20 στα downloads Θέμα 1ο ερώτημα iii φωτογραφία στο link  (http://prntscr.com/z3bpg1).

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

λάθος είναι η τομη είναι το αβ
sent from mTHMMY (https://play.google.com/store/apps/details?id=gr.thmmy.mthmmy) 


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: The Audacious AI on February 11, 2021, 14:46:35 pm
λάθος είναι η τομη είναι το αβ
sent from mTHMMY (https://play.google.com/store/apps/details?id=gr.thmmy.mthmmy) 

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: fuzzywuzzy on February 11, 2021, 15:07:45 pm
α σωστά. Άρα είναι {a,b,ab} η σωστή απάντηση;

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: tasosl on February 11, 2021, 15:27:19 pm
νομίζω μόνο ab είναι
sent from mTHMMY (https://play.google.com/store/apps/details?id=gr.thmmy.mthmmy) 


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Patatompataria on February 11, 2021, 15:40:38 pm
Σεπτέμβριος 20, Θέμα 2α, δε θα έπρεπε να προστεθούν και κανόνες της μορφής  S-->ΒC για κάθε Α που ανήκει στο D(S)-{S} με A-->BC??

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

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

νομίζω μόνο ab είναι
sent from mTHMMY (https://play.google.com/store/apps/details?id=gr.thmmy.mthmmy) 
κι εγω αυτό νομίζω, επειδή το 'a' δεν το δέχεται η πρώτη γλώσσα που θέλει να τελειώνει με b, και το 'b' δε το δέχεται η 2η γλώσσα


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: fuzzywuzzy on February 11, 2021, 15:55:32 pm
Δεν είναι {αβ, ε}?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: tasosl on February 11, 2021, 15:58:14 pm
νομίζω πως όχι δεν πρέπει να ανήκει η κενή συμβολοσειρά σε αυτές τις δύο γλώσσες πάντα θα έχεις ένα α η β αντίστοιχα
sent from mTHMMY (https://play.google.com/store/apps/details?id=gr.thmmy.mthmmy) 


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: fuzzywuzzy on February 11, 2021, 16:20:48 pm
Αα οκ, προσπαθούσα να εκφράσω το γεγονός ότι μπορεί να μην έχουν τομή αλλά μπερδεύτηκα με το L[Ø*]={ε}(εδώ δεν έχουμε *). Ευχαριστώ


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Elina97 on February 11, 2021, 18:40:47 pm
Υποχρεωτικά πρέπει να γίνει και το βήμα που λες για να καταλήξουμε στην KMC για τον ΔΠ.

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: The Audacious AI on February 11, 2021, 22:23:11 pm
Θέμα 1ο Σεπτέμβριος 20 το (iii) είναι αποδεκτό σωστά; Μόνο εμένα μου πήρε μια σελίδα πράξεις για να το αποδείξω; Και όλα αυτά για μισή μονάδα!

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: koumanas on February 11, 2021, 22:29:31 pm
Θέμα 1ο Σεπτέμβριος 20 το (iii) είναι αποδεκτό σωστά; Μόνο εμένα μου πήρε μια σελίδα πράξεις για να το αποδείξω; Και όλα αυτά για μισή μονάδα!

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

Είναι αποδεκτό; Πχ για ν=2, βγαίνει; Διότι πρέπει να είναι για κάθε ν
sent from mTHMMY (https://play.google.com/store/apps/details?id=gr.thmmy.mthmmy) 


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: The Audacious AI on February 11, 2021, 22:32:54 pm
Εγώ αυτό έκανα. Είμαι αρκετά πτώμα αλλά νομίζω δουλεύει


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Patatompataria on February 11, 2021, 22:40:18 pm
χμμ ναι αλλά η q0 δεν είναι τελική κατάσταση

Είναι αποδεκτό; Πχ για ν=2, βγαίνει; Διότι πρέπει να είναι για κάθε ν
sent from mTHMMY (https://play.google.com/store/apps/details?id=gr.thmmy.mthmmy) 
ούτε εγώ μπόρεσα να το κάνω για ν=2


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: The Audacious AI on February 11, 2021, 22:41:47 pm
χμμ ναι αλλά η q0 δεν είναι τελική κατάσταση

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: tasosl on February 11, 2021, 22:46:49 pm
εγώ έβγαλα μόνο ότι για ν περιττό δουλεύει και για άρτιο όχι
sent from mTHMMY (https://play.google.com/store/apps/details?id=gr.thmmy.mthmmy)  


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Patatompataria on February 11, 2021, 22:53:31 pm
άρα απλώς έπρεπε να κάνεις και άλλα τόσα (όλες τις δυνατές περιπτώσεις) για να δείξεις πως δεν είναι αποδεκτό; Αυτό δεν βγαίνει!
τουλάχιστον αρκεί να βρεις ένα ν που δεν αποδέχεται.. αλλά για να το αποδείξεις (ότι δεν αποδέχεται) κανονικά πρέπει να εξετάσεις όλα τα μονοπάτια... ναι, ριπ

εγώ έβγαλα μόνο ότι για ν περιττό δουλεύει και για άρτιο όχι
sent from mTHMMY (https://play.google.com/store/apps/details?id=gr.thmmy.mthmmy) 
αυτό φαίνεται να ισχύει, αλλά για να κάνεις κανονική απόδειξη και για τα 2, θα θες πολύ χρόνο


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: The Audacious AI on February 11, 2021, 23:01:20 pm
μόνο εγώ νομίζω πως τα θέματα του Σεπτέμβρη θέλανε άπειρη ώρα;


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: fuzzywuzzy on February 11, 2021, 23:10:33 pm
Εγώ αυτό έκανα. Είμαι αρκετά πτώμα αλλά νομίζω δουλεύει

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: koumanas on February 12, 2021, 08:59:38 am
Εν τέλει στο Θέμα 1ο Σεπτέμβριος 20 βρήκα τα (ii) (iv) αποδεκτά. Δε ξέρω αν μου ξέφυγε κάτι.
sent from mTHMMY (https://play.google.com/store/apps/details?id=gr.thmmy.mthmmy) 


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Elina97 on February 12, 2021, 11:56:33 am
Εν τέλει στο Θέμα 1ο Σεπτέμβριος 20 βρήκα τα (ii) (iv) αποδεκτά. Δε ξέρω αν μου ξέφυγε κάτι.
sent from mTHMMY (https://play.google.com/store/apps/details?id=gr.thmmy.mthmmy) 

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

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Xplicit on February 12, 2021, 11:57:48 am
μόνο εγώ νομίζω πως τα θέματα του Σεπτέμβρη θέλανε άπειρη ώρα;

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Elina97 on February 12, 2021, 12:03:29 pm
πωωωωω τζάμπα τόσος κόπος... άρα απλώς έπρεπε να κάνεις και άλλα τόσα (όλες τις δυνατές περιπτώσεις) για να δείξεις πως δεν είναι αποδεκτό; Αυτό δεν βγαίνει!

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



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

ΑΣΤΑ ΝΑ ΠΑΝΕ


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Xplicit on February 12, 2021, 12:41:46 pm
Και εγω αποδεκτό το βγάζω το 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)


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Elina97 on February 12, 2021, 12:58:36 pm
Και εγω αποδεκτό το βγάζω το 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 . Χαχαχαχα σορρυυυυυυυ. Αυτά είναι τα δικά μου


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Elina97 on February 12, 2021, 13:00:18 pm
Απλά μπορείς να πεις οτι διαβάζοντας έστω ένα b αυτό σημαίνει οτι είσαι στην q1 ή στην q3. Από αυτές τις καταστάσεις δεν μπορείς να οδηγηθείς στην q3 με 2α.
Και κάνεις από κάτω και τις πιθανές διαδρομες και καθάρισες. Μου πήρε 5 σειρές  ::)


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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: The Audacious AI on February 12, 2021, 13:35:53 pm
Έστω έχω ένα Πεπερασμένο Αυτόματο (πχ Φεβρ 18 θέμα 1ο) και έχω μια κατάσταση όπου μόνο πας και δεν φεύγεις και δεν είναι τελική (πχ q3).  Τι κάνω τότε; Αφού δεν είναι τελική κατάσταση δεν μπορεί να τελειώνει εκεί. Άρα να πάει εκεί θα μπλέξει σε ατέρμονο βρόχο??!!


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Elina97 on February 12, 2021, 13:46:30 pm
Έστω έχω ένα Πεπερασμένο Αυτόματο (πχ Φεβρ 18 θέμα 1ο) και έχω μια κατάσταση όπου μόνο πας και δεν φεύγεις και δεν είναι τελική (πχ q3).  Τι κάνω τότε; Αφού δεν είναι τελική κατάσταση δεν μπορεί να τελειώνει εκεί. Άρα να πάει εκεί θα μπλέξει σε ατέρμονο βρόχο??!!

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: mikalaki on June 19, 2021, 15:55:07 pm
Στο θέμα 1ο του Σεπτεμβριου 2020, στο iii για n=0, βγάζω ότι δεν ισχύει, επομένως μπορώ να πω ότι καθώς δεν ισχύει για n=0, η συμβολοσειρά δεν είναι αποδεκτή σωστά?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Asclepias tuberosa on June 23, 2021, 14:19:45 pm
Στο θέμα 1ο του Σεπτεμβριου 2020, στο iii για n=0, βγάζω ότι δεν ισχύει, επομένως μπορώ να πω ότι καθώς δεν ισχύει για n=0, η συμβολοσειρά δεν είναι αποδεκτή σωστά?
Την είχα κι εγω αυτήν την απορία. Δεν ξέρω αν ειναι αυτονοητο το πού οριζεται το n, αν και λογικα για να μην το οριζει μαλλον θα περιλαμβανεται και το 0. Παντως ουτε για 2 ισχυει, οποτε μπορεις να το δειξεις και μ αυτο.


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Mandalorian on June 23, 2021, 15:33:36 pm
Στο 2ο θέμα του Ιουλίου 2020 στο α' ερώτημα εγώ έβγαλα την εξής μορφή:

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


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

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


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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Traxius on June 23, 2021, 16:24:31 pm
Στο 2ο θέμα του Ιουλίου 2020 στο α' ερώτημα εγώ έβγαλα την εξής μορφή:

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


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

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


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


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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Asclepias tuberosa on June 23, 2021, 20:26:33 pm
Σε θέματα όπως το 3ο του Φεβρουαρίου 2021, που ζητάει να κατασκευάσουμε Μ Turing αλλά δίνοντας τη συνάρτηση μετάβασης δ, χρειάζεται να καλύψουμε όλες τις περιπτώσεις στη συνάρτηση; Πχ αν επιλέξω δ(s,_) = (q0, ->), ( _ = κενό) οπότε κατευθείαν φεύγω από την κατάσταση s, πρέπει να συμπεριλάβω και ποια θα είναι τα δ(s,a), δ(s,b), δ(s,|>), (|> = το τρίγωνο) στα οποία πρακτικά δεν θα χρησιμοποιήσω ποτέ;


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: fuzzywuzzy on June 23, 2021, 20:33:41 pm
Τι εννοείς δεν θα τα χρησιμοποιήσεις ποτέ? Πως είσαι σίγουρος ότι δεν θα γίνει δ(s,a) ?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Asclepias tuberosa on June 23, 2021, 20:56:39 pm
Τι εννοείς δεν θα τα χρησιμοποιήσεις ποτέ? Πως είσαι σίγουρος ότι δεν θα γίνει δ(s,a) ?
Γιατί θεωρώ για δομή της ταινιας |> _ w  (w η συμβολοσειρα).
Ξεκιναω λοιπον απο το κενο διπλα απο το τριγωνο και το πρωτο βημα ειναι να παω δεξια αλλαζοντας κατασταση ταυτοχρονα, γι αυτο και δ(s,_)=(qo,->). Το πηρα αυτο απο τις σημειωσεις 2019 στα downloads σελιδα 79, μια ασκηση που εκαναν στην ταξη. Σε αυτην την ασκηση, στις υπολοιπες περιπτωσεις για το s εχει διπλα  στις δ xxxx και αναρωτιομουν αν οντως ειναι σωστο να μην τα ορισουμε. Με βαση τον ορισμο που επελεξε στην ασκηση, παντως, δεν βγαζει και νοημα να τα ορισεις καπως, μιας και μοιαζουν αχρηστες περιπτωσεις.

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Nickgian on February 05, 2022, 12:56:05 pm
Φεβ 2018 μπορει καποιος να μου εξηγηση πως λυνεται το θεμα 1ο ερωτημα β και στην περιπτωσει που δεν ειναι ειδη ελαχιστο τι κανουμε?
Δηλαδη ολη την διαδικασια.


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: fuzzywuzzy on February 05, 2022, 13:25:06 pm
Νομίζω απλά θα κάνεις τη διαδικασία για να βρεις το ελάχιστο ΑΠΑ και λογικά να συμπεράνεις ότι ήδη είναι ελάχιστο.


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Nickgian on February 05, 2022, 13:38:50 pm
Νομίζω απλά θα κάνεις τη διαδικασία για να βρεις το ελάχιστο ΑΠΑ και λογικά να συμπεράνεις ότι ήδη είναι ελάχιστο.

Μπορείς να μου την περιγράψεις με κάποιο παράδειγμα όπως αυτό παραπάνω και ένα διαφορετικό που θέλει περισσότερη ανάλυση.
sent from mTHMMY (https://play.google.com/store/apps/details?id=gr.thmmy.mthmmy) 


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: fuzzywuzzy on February 05, 2022, 15:08:13 pm
https://www.thmmy.gr/smf/index.php?action=tpmod;dl=item5781

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


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Nickgian on February 05, 2022, 21:55:47 pm
https://www.thmmy.gr/smf/index.php?action=tpmod;dl=item5781

Μπες στις σημειώσεις εδώ σελ 42 λέει για ελάχιστο ΑΠΑ και σελ45 έχει παράδειγμα, τα έχει πιο αναλυτικά απ'όσο θα μπορέσω να στο εξηγήσω εγώ. Αν έχεις πάλι θέμα στείλε πμ
Τελεια με καλυψε
Οσον αφορα το θεμα 3ο τον φεβ 2018 που θελουμε την ΓΧΣ να την κανουμε σε Κανονικη  μορφη Chomsky οταν παμε να διωξουμε τα κενα δεν καταλαβα ετσι οπως το εξηγει με το Ε .. και πως απαλείφονται και τι προσθετο στο τελος του 2ου βηματος.
Μπορεις να με βοηθησεις;


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Πατερ Ημμυων on February 05, 2022, 23:06:18 pm
Ίσως βοηθήσει αυτό. Το έχω όπως το καταλαβαίνω ίσως να μην είναι και σωστά  :D


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Nickgian on February 07, 2022, 15:23:05 pm
Τελεια σε ευχαριστω πολυ.
Στα θεματα Σεπτ. 2018 θεμα 2ο ερωτημα β μπορει να λυθει με Δ.Π. κανοντας το πινακι και βλεποντας αν στο n[1,Ν] = S οπου Ν = |w|  , μπορουμε να πουμε οτι ανηκει στην Γλωσσα L(G)?
Η πρεπει πρωτα να το κανουμε σε κανονικη μορφη Chmosky και μετα τα υπολοιπα?


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Πατερ Ημμυων on February 07, 2022, 15:29:29 pm
Αν θες να το κάνεις με δυναμικό προγραμματισμό αναγκαστικά θες chomsky . Το συγκεκριμενο πιστευω αρκεί να βρεις ένα συντακτικό δεντρο να το φτιάχνει . Το ξεκινάς απο κάτω αφού πρακτικά η συμβολοσειρά είναι τα φύλλα του δέντρου και το χτίζεις προς τα πάνω μεχρι να φτάσεις σε ένα S


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Nickgian on February 07, 2022, 15:45:27 pm
Ναι οντως
Σε ευχαριστω πολυ


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Nickgian on February 10, 2022, 21:17:11 pm
Φεβ 17
Θεμα 3ο εχει κανεις λυσης


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Nickgian on February 10, 2022, 21:42:05 pm
Υπαρχει διαφορα μεταξυ R1 = ab και R1 = {(a)U (b) }


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Πατερ Ημμυων on February 10, 2022, 22:01:02 pm
Υπαρχει διαφορα μεταξυ R1 = ab και R1 = {(a)U (b) }
τεράστια .  Το  πρώτο έχει πρώτα α και μετά β , μήκος 2 , ενω στο δεύτερο έχει ή σκέτο α ή σκέτο β , μηκος 1. Με χειροπιαστό παράδειγμα το πρώτο είναι σαν να λες θα φάω πρώτα κυρίως πιάτο και μετά επιδόρπιο ενώ το δεύτερο θα φας μόνο ένα.


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Nickgian on February 10, 2022, 22:14:14 pm
τεράστια .  Το  πρώτο έχει πρώτα α και μετά β , μήκος 2 , ενω στο δεύτερο έχει ή σκέτο α ή σκέτο β , μηκος 1. Με χειροπιαστό παράδειγμα το πρώτο είναι σαν να λες θα φάω πρώτα κυρίως πιάτο και μετά επιδόρπιο ενώ το δεύτερο θα φας μόνο ένα.
Σωστος ειχα κολλησει
Σε ευχαριστω πολυ!


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Τζουμ τριαλαρέι on June 13, 2022, 17:46:44 pm
εχει λυσει κανεις τα θεματα του Φλεβαρη (2022);


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Τζουμ τριαλαρέι on June 19, 2022, 11:36:09 am
Μπορεί κανείς να μου εξηγήσει πως βρίσκει τους κανονες και το επεκτεταμενο αλφάβητο στο 2ο θεμα του Φλεβαρη του 2021; Ποια βήματα ακολουθεί;


Title: Re: [Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες
Post by: Limpolits on June 28, 2024, 15:25:36 pm
Πως αποδεικνύουμε ότι μια γραμματική G είναι σαφής;