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

preview_player
Показать описание
Κανονικές Γλώσσες
=================
Λήμμα Άντλησης για Κανονικές Γλώσσες
  1. Δημήτρης Ψούνης
  2. ΕΑΠ
  3. ΠΛΗ30
  4. ΚΑΡΤΑ
Рекомендации по теме
ΚΑΡΤΑ - ΛΗΜΜΑ 0:04:14

ΚΑΡΤΑ - ΛΗΜΜΑ ΑΝΤΛΗΣΗΣ ΓΙΑ Γ.Χ.Σ.

ΚΑΡΤΑ - ΛΗΜΜΑ 0:08:30

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

ΚΑΡΤΑ - ΤΟ 0:05:00

ΚΑΡΤΑ - ΤΟ ΛΗΜΜΑ ΤΗΣ ΧΕΙΡΑΨΙΑΣ

ΚΑΡΤΑ - ΤΟ 0:08:04

ΚΑΡΤΑ - ΤΟ 3SAT ΕΙΝΑΙ NP-ΠΛΗΡΕΣ

6.1 Μη Κανονικές 0:05:28

6.1 Μη Κανονικές Γλώσσες και το Λήμμα Άντλησης

ΚΑΡΤΑ - ΝΤΕΤΕΡΜΙΝΙΣΤΙΚΑ 0:10:25

ΚΑΡΤΑ - ΝΤΕΤΕΡΜΙΝΙΣΤΙΚΑ ΑΥΤΟΜΑΤΑ ΣΤΟΙΒΑΣ

ΚΑΡΤΑ - Το 0:06:22

ΚΑΡΤΑ - Το CLIQUE είναι NP-πλήρες

ΚΑΡΤΑ - ΜΗ 0:06:48

ΚΑΡΤΑ - ΜΗ ΝΤΕΤΕΡΜΙΝΙΣΤΙΚΑ ΠΕΠΕΡΑΣΜΕΝΑ ΑΥΤΟΜΑΤΑ ΣΤΟΙΒΑΣ...

6.2 Παραδείγματα Εφαρμογής 0:25:17

6.2 Παραδείγματα Εφαρμογής του Λήμματος Άντλησης για την Απόδειξη Μη Κανονικών Γλωσσών...

ΚΑΡΤΑ - ΙΔΙΟΤΗΤΕΣ 0:06:48

ΚΑΡΤΑ - ΙΔΙΟΤΗΤΕΣ σε ΝΤΕΤΕΡΜΙΝΙΣΤΙΚΑ ΑΥΤΟΜΑΤΑ ΣΤΟΙΒΑΣ

ΚΑΡΤΑ - ΚΛΕΙΣΤΟΤΗΤΕΣ 0:09:41

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

ΚΑΡΤΑ - ΘΕΩΡΗΜΑ 0:09:16

ΚΑΡΤΑ - ΘΕΩΡΗΜΑ ΚΥΡΙΑΡΧΙΑΣ

ΚΑΡΤΑ - ΚΑΝΟΝΙΚΕΣ 0:05:06

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

ΚΑΡΤΑ - ΜΗ 0:08:38

ΚΑΡΤΑ - ΜΗ ΝΤΕΤΕΡΜΙΝΙΣΤΙΚΑ ΠΕΠΕΡΑΣΜΕΝΑ ΑΥΤΟΜΑΤΑ (ΜΠΑ)

ΚΑΡΤΑ - ΓΡΑΜΜΑΤΙΚΕΣ 0:08:41

ΚΑΡΤΑ - ΓΡΑΜΜΑΤΙΚΕΣ ΧΩΡΙΣ ΣΥΜΦΡΑΖΟΜΕΝΑ

ΚΑΡΤΑ - ΜΑΘΗΜΑΤΙΚΟ 0:07:14

ΚΑΡΤΑ - ΜΑΘΗΜΑΤΙΚΟ ΥΠΟΒΑΘΡΟ ΑΝΑΛΥΣΗΣ ΑΛΓΟΡΙΘΜΩΝ

ΚΑΡΤΑ - ΚΛΑΣΕΙΣ 0:04:22

ΚΑΡΤΑ - ΚΛΑΣΕΙΣ ΠΟΛΥΠΛΟΚΟΤΗΤΑΣ

ΚΑΡΤΑ - Η 0:05:38

ΚΑΡΤΑ - Η ΚΛΑΣΗ ΤΩΝ NP-COMPLETE ΠΡΟΒΛΗΜΑΤΩΝ

11η διάλεξη 0:42:51

11η διάλεξη

ΚΑΡΤΑ - ΚΛΕΙΣΤΟΤΗΤΕΣ 0:07:33

ΚΑΡΤΑ - ΚΛΕΙΣΤΟΤΗΤΕΣ ΓΛΩΣΣΩΝ ΧΩΡΙΣ ΣΥΜΦΡΑΖΟΜΕΝΑ

ΚΑΡΤΑ - Μετατροπή 0:06:44

ΚΑΡΤΑ - Μετατροπή Κανονικής Έκφρασης σε ΜΠΑ-ε

ΚΑΡΤΑ - ΑΠΟΔΕΙΞΕΙΣ 0:04:22

ΚΑΡΤΑ - ΑΠΟΔΕΙΞΕΙΣ NP-ΠΛΗΡΟΤΗΤΑΣ

ΠΛΗ30 - ΔΙΑΓΩΝΙΣΜΑ 0:13:52

ΠΛΗ30 - ΔΙΑΓΩΝΙΣΜΑ 1 - ΑΣΚΗΣΗ 4.1

ΚΑΡΤΑ - Μετατροπή 0:04:50

ΚΑΡΤΑ - Μετατροπή ΜΠΑ σε ΝΠΑ

Комментарии
Автор

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

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