[Θ.Υ.Α.] Απορίες στις ασκησεις 2014-2015

[Thmmy.gr portal]

  Thmmy.gr portal
   Forum
   Downloads
   Ενεργ. Λογαριασμού
   Επικοινωνία
  
  Χρήσιμα links
   Σελίδα τμήματος
   Βιβλιοθήκη Τμήματος
   Elearning
   Φοιτητικά fora
   Πρόγραμμα Λέσχης
   Πρακτική Άσκηση
   Ηλεκτρονική Εξυπηρέτηση Φοιτητών
   Διανομή Συγγραμμάτων
   Ψηφιακό Καταθετήριο Διπλωματικών
   Πληροφορίες Καθηγητών
   Instagram @thmmy.gr
   mTHMMY
  
  Φοιτητικές Ομάδες
   ACM
   Aristurtle
   ART
   ASAT
   BEAM
   BEST Thessaloniki
   EESTEC LC Thessaloniki
   EΜΒ Auth
   IAESTE Thessaloniki
   IEEE φοιτητικό παράρτημα ΑΠΘ
   SpaceDot
   VROOM
   Panther
  

THMMY.gr Web

Helios_MultiScribbles2SMF Default ThemeSMFone_Blue

[Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads]

Είσαι πρωτοετής;... Καλώς ήρθες! Μπορείς να βρεις πληροφορίες εδώ. Βοήθεια για τους καινούργιους μέσω χάρτη.

Κατεβάστε εδώ το Android Application για εύκολη πρόσβαση στο forum.

Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads με προσοχή στα ονόματα των αρχείων!

[12:00-13:30]

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

[princess_of_the_dawn]

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

[christineL]

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

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

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

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

[christineL]

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

[SolidSNK]

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

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

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

[christineL]

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

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

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

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

[et3rn1ty]

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

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

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

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

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

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

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

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

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

[SolidSNK]

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

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

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

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

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



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

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

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

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

What he said.

[christineL]

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

[christineL]

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

[et3rn1ty]

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

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


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

[christineL]

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

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


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

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

[xaris]

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

[Noldireth]

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

[isitsou]

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

[SolidSNK]

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

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