ΚΑΡΤΑ - ΛΗΜΜΑ ΑΝΤΛΗΣΗΣ ΓΙΑ ΚΑΝΟΝΙΚΕΣ ΓΛΩΣΣΕΣ

preview_player
Показать описание
Κανονικές Γλώσσες
=================
Λήμμα Άντλησης για Κανονικές Γλώσσες
Рекомендации по теме
Комментарии
Автор

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

fullface
Автор

Στην τελευταία γλώσσα κάτω κάτω αριστερά στην καρτέλα, όπου λέει διάζευξη συμβολοσειρών, μπορούμε να αποδείξουμε ότι δεν είναι κανονική με τη συμβολοσειρά a^pb^pc^p; Αφού μετά την ύψωση στη δύναμη θα προκύψει a^(p+j)b^pc^p η οποία ανήκει στη γλώσσα αφού ο εκθέτης του b είναι ίσος με τον εκθέτη του c. Ωστόσο, αν επιλέγαμε την a^pb^pc^(p+1) η απόδειξη θα δούλευε κανονικά. Έχω καταλάβει κάτι λάθος;

panos
Автор

Δε θα μπορουσαμε να πουμε οτι η 0^p1^p ανήκει στη γλώσσα L που έχει άρτιο μήκος και να δείξουμε ότι πάλι η uv^2w δεν ανήκει σε αυτή, οπότε δεν ισχύει το λήμμα και η γλώσσα δεν είναι κανονική; Που δε βγάζει νόημα γιατί υπάρχει ΚΕ για τη γλώσσα L.

nevwalkalone