forum.math.uoa.gr

Forum του Τμήματος Μαθηματικών
Ημερομηνία 15 Νοέμ 2018, 03:53

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]




Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 4 δημοσιεύσεις ] 
Συγγραφέας Μήνυμα
 Θέμα δημοσίευσης: 2 ασκήσεις με αυτόματα.
ΔημοσίευσηΔημοσιεύτηκε: 22 Μάιος 2018, 21:20 
Χωρίς σύνδεση

Εγγραφη: 10 Ιαν 2010, 19:14
Δημοσ.: 65
Γειά σας, θα ήθελα βοήθεια με τις παρακάτω ασκήσεις:
Να βρεθεί αυτόματο που να αναγνωρίζει όλους τους φυσικούς που είναι πολλαπλάσια του 3.
Να αποδειχθεί οτι το σύνολο των πρώτων αριθμών δεν αποτελεί αναγνωρίσιμη γλώσσα.


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: 2 ασκήσεις με αυτόματα.
ΔημοσίευσηΔημοσιεύτηκε: 27 Μάιος 2018, 17:33 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 11 Φεβ 2007, 21:13
Δημοσ.: 638
1.Κοίτα αυτό το σχήμα

https://en.wikipedia.org/wiki/Determini ... _automaton

ουσιαστικά χρησιμοποιείς αλγόριθμο modulo 3

Η ιδέα...Έχεις 3 περιπτώσεις...Διαιρείς τον αριθμό με το 3 και έχεις υπόλοιπο 0, 1,ή 2. Το S_0 αντιστοιχεί στην περίπτωση που το υπόλοιπο είναι 0...τα S_1 και S_2 αντίστοιχα 1 και 2. Κάθε φορά που τερματίζει στο S_0 ή έχεις λύση ή όχι...ανάλογα με το υπόλοιπο.

2.Αυτό εἰναι απόρροια του γεγονότος ότι το σύνολο των πρώτων αριθμών περιέχει ακανόνιστα διαστήματα δηλ, μεταξύ δύο διαδοχικών πρώτων αριθμών μπορούν να υπάρξουν οσοδήποτε μεγάλα κενά. (Αν το Pumping Lemma πχ. ήταν αληθές τότε θα ήταν αυτά τα διαστήματα άνω φραγμένα απο κάποια σταθερά, κάτι που αντιβαίνει το θεώρημα των πρώτων αριθμών)
Η συνήθης απόδειξη για τα διαστήματα:
Παίρνουμε έναν τυχαίο αριθμό πχ. τον 1.000.000...Μπορούμε τότε να αποδείξουμε ότι κάπου ανάμεσα στούς φυσικούς αριθμούς υπάρχουν δύο πρώτοι αριθμοί α και β ενδιάμεσα των οποίων δεν υπάρχει άλλος πρώτος και η απόστασή τους είναι μεγαλύτερη απο 1.000.000.
Αυτό το κάνουμε ως εξής. Έστω m τυχαίος φυσικός αριθμός. Θεωρούμε τώρα τούς

m!+2
m!+3
m!+4
………..
m!+m-1
m!+m

Όλοι αυτοί δεν είναι πρώτοι αριθμοί, διότι ο
m! διαιρείται απο το 2 (άρα και ο m!+2)
m! διαιρείται και απο το 3 (άρα και ο m!+3)
και τελικά ο
m!+m διαιρείται απο το m


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: 2 ασκήσεις με αυτόματα.
ΔημοσίευσηΔημοσιεύτηκε: 28 Μάιος 2018, 17:40 
Χωρίς σύνδεση

Εγγραφη: 10 Ιαν 2010, 19:14
Δημοσ.: 65
Υποθέτω οτι δεν μιλάς για τη γλώσσα L=(p/p πρώτος αριθμός), όπου η πράξη μεταξύ των ψηφίων είναι η παράθεση, αλλά για την L=(a^p/a γράμμα και p πρώτος αριθμός), όπου η πράξη μεταξύ των ψηφίων είναι η πρόσθεση.
Αν κατάλαβα καλά σύμφωνα με την απόδειξη σου παίρνουμε το δεκαδικό ανάπτυγμα ενός πρώτου εφαρμόζουμε το pumping lemma οπότε αναγνωρίζεται κάθε αριθμός της μορφής xy^kz με x=Σαι*10^ι με i<=n, y=Σαι*10^ι με n<i<=m, z= Σαι*10^ι με m<ι<=s. Το x(y^k)z αυξάνει εκθετικά με βήμα μεγαλύτερο του [10^(m-n)]*y όμως το διάστημα μεταξυ δυο τέτοιων αριθμών μπορεί να αυξηθεί οσοδήποτε.


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: 2 ασκήσεις με αυτόματα.
ΔημοσίευσηΔημοσιεύτηκε: 29 Μάιος 2018, 18:47 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 11 Φεβ 2007, 21:13
Δημοσ.: 638
Κάπως έτσι δουλεύει:

Θέλουμε να αποδείξουμε ότι η L :{a^p | p πρώτος αριθμός} δέν είναι pumpable
Απόδειξη
Ειδ‘ άλλως κάθε pumping αριθμός k θα μπορούσε να γραφτεί σαν άθροισμα u+v+w με n>=1, u+v<=k έτσι ώστε u + iv + w για κάθε i να είναι πρώτος αριθμός. (x = a^u a^v a^w)

Στην περίπτωση που i = (u+w ) θα ήταν u+ (u+w)v + w = (u+w)(v+1) πρώτος αριθμός, που δεν ισχύει.
( u+w και v+1 είναι μεγαλύτεροι του 1)


Κορυφή
 Προφίλ  
 
Τελευταίες δημοσιεύσεις:  Ταξινόμηση κατά  
Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 4 δημοσιεύσεις ] 

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]


Μελη σε συνδεση

Μέλη σε αυτή την Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 3 επισκέπτες


Δεν μπορείτε να δημοσιεύετε νέα θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να απαντάτε σε θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να επεξεργάζεστε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να διαγράφετε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση

Αναζήτηση για:
Μετάβαση σε:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group