[Θ.Υ.Α] Παλιά θέματα - Σχολιασμός και απορίες

[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 με προσοχή στα ονόματα των αρχείων!

Για οποιοδήποτε πρόβλημα με register/login, στείλτε email στο contact@thmmy.gr.

[giwrgosbg]

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

[nvog1993]

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

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

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

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

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

[WatchDog]

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

[nvog1993]

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

[WatchDog]

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

[nvog1993]

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

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

[Λήσταρχος Γιαγκούλας]

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

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

[WatchDog]

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

[nvog1993]

Στο β' μπορείς να εξηγήσεις λίγο τις καταστάσεις  S2,q0,q1?

Για είσοδο κενό στην S2 δε θα έπρεπε να απορρίπτει?

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

[Kthulu]

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

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

[TrueForce]

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

[Kthulu]

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

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

[TrueForce]

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

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

[TrueForce]

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

[Vlassis]

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

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