Αντίφαση?????
Posted by Νατάσα Λαγού Fri, 07 Mar 2008 01:09:54 EET
Θεώρημα Άντλησης για Κανονικές Γλώσσες:
Έστω άπειρη και ΚΑΝΟΝΙΚΗ γλώσσα L. Τότε υπάρχουν λέξεις x, y και z τέτοιες ώστε:
1) y != e (e: κενή)
2) Για κάθε ακέραιο n>=0, η λέξη x(y^n)z ανήκει στη γλώσσα L.
Ως εδώ όλα καλά… Πάμε στα παρακάτω…
Εκφώνηση Άσκησης:
Θεωρούμε τη γλώσσα L = {…}.
a) Αποδείξετε ότι η L ικανοποιεί τις Συνθήκες του Θεωρήματος Άντλησης . ((Δηλαδή ότι η L είναι κανονική γλώσσα αν εκατάλαβα καλά))
b) Αποδείξετε ότι η L δεν είναι κανονική . ((!!!!!!! huh???))
Αποδείξεις του είδους γίνονται με Αντίφαση, δηλαδή πρέπει να καταλήξεις σε άτοπο…
Τωρά αν του γράψω: [Ερώτημα a) και Ερώτημα b)] = Αντίφαση, άραγε θα πιάσω πόντους?????
Ουυυυφφφφφφφφ…! Άρκεψα να πονώ τον εγκέφαλο μου… Αποδείξεις και πράσινα άλογα… Προτιμώ τα πράσινα τα άλογα…! :/
Reader's Comments
Χαίρετε. Αν θυμάμαι καλά, το ΘΑ είναι αναγκαία αλλά όχι ικανή προϋπόθεση για να είναι μια γλώσσα κανονική.
Δηλαδή, μια γλώσσα μπορεί να ικανοποιεί τις συνθήκες του ΘΑ αλλά να μην είναι κανονική. Για αυτό και το ΘΑ το χρησιμοποιούσαμε συνήθως για να αποδείξουμε ότι μια γλώσσα ΔΕΝ είναι κανονική — ποτέ όμως για να αποδείξουμε ότι μια γλώσσα είναι.
Έχεις απόλυτο δίκαιο Χρίστο!!! :-)
Ευχαριστωωωωωωώ!!! Μόλις σώθηκαν οι μισοί πόντοι!! :D
Δεν υπήρχε χειρότερο μάθημα για εμένα από τούτο. Θυμούμε τον καημένο τον Νεόφυτο που επροσπαθούσε να μας τα εξηγήσει και εβλέπαμεν τον ούλλοι όπως τα παλαβούδκια. Ακόμα και σήμερα πιστεύω πως για να καταλάβεις αυτό το μάθημα πρέπει να είσαι λίγο παράξενος. ( Με καλή έννοια πάντα ).
Ήταν το μόνο μάθημα που επαπαγάλισα τα πάντα, και στην τελική έκαμα ένα μεγαλοπρεπές copy paste και επέρασα με 7.5. Φυσικά ούτε 2 εν αξίζω όι 7.5.
Αυτό που με ενοχλεί μέχρι σήμερα είναι πως σε τέτοια μαθήματα, άχρηστα για εμένα, είχα ψηλούς βαθμούς ενώ στα μαθήματα που μου αρέσουν όπως OOP και DB είχα τους χαμηλότερους βαθμούς σε όλα τα έτη. ( 6 )
Ως τωρά, Διακριτά Μαθηματικά και Θεωρία Υπολογισμού & Πολυπλοκότητα, είναι τα χειρότερα μαθήματα που έκαμα! Με πόσα τα περνώ δεν με νοιάζει, φτάνει να μην τα ξαναδώ μπροστά μου!! ;p
Εκείνο που σκέφτομαι και γελώ, εν το ότι τούτα τα μαθήματα με τις αποδείξεις που έχουν κτλ, έχουν να κάμουν με μαθηματικά…! Κάποτε θυμούμαι που ήθελα να γίνω μαθηματικός και σήμερα μαθηματικά εν θέλω να δω μπροστά μου!
Μόλις επέρασα Πληροφορική, πολλοί εδιερωτούνταν αν θα τα παρετήσω στην πορεία..! Ε, σήμερα διερωτούμαι εγώ.. Αν επέρνουν μαθηματικός… Ήταν να άντεχα ως το δεύτερο έτος????
Πάντως στην πορεία ανακάλυψα ότι τελικά…. "Άη Λαβ ΕΠΛ!!!!" :-)