forum.math.uoa.gr

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

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




Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 10 δημοσιεύσεις ] 
Συγγραφέας Μήνυμα
 Θέμα δημοσίευσης: Βοήθεια-Ομαλές Γλώσσες(Αυτόματα)
ΔημοσίευσηΔημοσιεύτηκε: 11 Οκτ 2013, 20:28 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 02 Σεπ 2012, 18:29
Δημοσ.: 118
Καλησπέρα!

Πώς μπορώ να δείξω ότι η γλώσσα L={λ ε {α,β}*:η λέξη δεν περιέχει ούτε την (υπο)λέξη ααα ούτε την ββ} είναι ομαλή, χωρίς να σχεδιάσω διάγραμμα?? :?


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Βοήθεια-Ομαλές Γλώσσες(Αυτόματα)
ΔημοσίευσηΔημοσιεύτηκε: 11 Οκτ 2013, 21:05 
Χωρίς σύνδεση
Forum Moderator
Άβαταρ μέλους

Εγγραφη: 09 Φεβ 2012, 22:03
Δημοσ.: 619
Ορισμός της ομαλής γλώσσας?


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Βοήθεια-Ομαλές Γλώσσες(Αυτόματα)
ΔημοσίευσηΔημοσιεύτηκε: 13 Οκτ 2013, 00:34 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 02 Σεπ 2012, 18:29
Δημοσ.: 118
Ως ομαλή γραμματική ορίζουμε μια τετράδα <Σ,Σ_{k},Ι,Δ>, όπου
Σ το αλφάβητο,ένα πεπερασμένο σύνολο συμβόλων
Σ_{k} τα παραγωγικά σύμβολα/οι καταστάσεις, ένα πεπερασμένο σύνολο συμβόλων
Ι ένα αρχικό παραγωγικό σύμβολο
Δ ένα σύνολο κανόνων


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Βοήθεια-Ομαλές Γλώσσες(Αυτόματα)
ΔημοσίευσηΔημοσιεύτηκε: 13 Οκτ 2013, 12:04 
Χωρίς σύνδεση
Forum Moderator
Άβαταρ μέλους

Εγγραφη: 09 Φεβ 2012, 22:03
Δημοσ.: 619
Έστω L_1 = \{λ ε {α,β}*:η λέξη δεν περιέχειτην (υπο)λέξη ααα\} και L_2 = \{λ ε {α,β}*:η λέξη δεν περιέχει την (υπο)λέξη ββ\}.

Τότε έχεις ότι: L=L_1∩L_2

Αν μπορείς να δείξεις ότι οι L_1, L_2 είναι ομαλές, τότε έχεις την λύση από τα θεωρήματα κλειστότητας.


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Βοήθεια-Ομαλές Γλώσσες(Αυτόματα)
ΔημοσίευσηΔημοσιεύτηκε: 13 Οκτ 2013, 12:50 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 02 Σεπ 2012, 18:29
Δημοσ.: 118
Και πώς μπορώ να δείξω ότι μία γλώσσα είναι ομαλή??


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Βοήθεια-Ομαλές Γλώσσες(Αυτόματα)
ΔημοσίευσηΔημοσιεύτηκε: 13 Οκτ 2013, 13:04 
Χωρίς σύνδεση
Forum Moderator
Άβαταρ μέλους

Εγγραφη: 09 Φεβ 2012, 22:03
Δημοσ.: 619
Κατασκευάζοντας μία μηχανή που θα αποδέχεται τις λέξεις που ανήκουν στην γλώσσα και θα απορρίπτει όλες τις άλλες.

EDIT: Δηλαδή, πρέπει να δημιουργήσεις έναν κανόνα διαλογής.


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Βοήθεια-Ομαλές Γλώσσες(Αυτόματα)
ΔημοσίευσηΔημοσιεύτηκε: 13 Οκτ 2013, 20:25 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 02 Σεπ 2012, 18:29
Δημοσ.: 118
Έχω κολλήσει...Μπορείς να μου το εξηγήσεις???


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Βοήθεια-Ομαλές Γλώσσες(Αυτόματα)
ΔημοσίευσηΔημοσιεύτηκε: 13 Οκτ 2013, 20:47 
Χωρίς σύνδεση
Forum Moderator
Άβαταρ μέλους

Εγγραφη: 09 Φεβ 2012, 22:03
Δημοσ.: 619
Μπορείς να το λύσεις με διάγραμμα?


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Βοήθεια-Ομαλές Γλώσσες(Αυτόματα)
ΔημοσίευσηΔημοσιεύτηκε: 16 Οκτ 2013, 23:55 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 02 Σεπ 2012, 18:29
Δημοσ.: 118
Για το L_1 = \{λ ε {α,β}*:η λέξη δεν περιέχει την (υπο)λέξη ααα\}

Ο πίνακας με τις ματαβάσεις είναι:
___| |_a__|_b_
___| |____|___
Q_0 | | Q_1 | Q_0
Q_1 | | Q_2 | Q_0
Q_2 | | Q_3 | Q_0
Q_3 | | Q_3 | Q_3

με τελικές τις καταστάσεις Q_0, Q_1, Q_2.

Αντίστοιχα, για το L_2 = \{λ ε {α,β}*:η λέξη δεν περιέχει την (υπο)λέξη ββ\}

Ο πίνακας με τις ματαβάσεις είναι:
___| |_a__|_b_
___| |____|___
Q_0 | | Q_0 | Q_1
Q_1 | | Q_0 | Q_2
Q_2 | | Q_2 | Q_2

με τελικές τις καταστάσεις Q_0, Q_1.

Σωστά??


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Βοήθεια-Ομαλές Γλώσσες(Αυτόματα)
ΔημοσίευσηΔημοσιεύτηκε: 17 Οκτ 2013, 22:35 
Χωρίς σύνδεση
Forum Moderator
Άβαταρ μέλους

Εγγραφη: 09 Φεβ 2012, 22:03
Δημοσ.: 619
Σωστό μου φαίνεται!

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


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

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


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

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


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

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