KIT-Bibliothek
suchen
KIT-Bibliothek
KIT-Bibliothek Medienportal

100 Übungsaufgaben zu Grundlagen der Informatik, Bd. I - Kap. 7: Pumping Lemma

Autor

Hartmut Schmeck

Beteiligtes Institut

KIT-Bibliothek (BIB)

Genre

Vorlesung

Beschreibung

Der vorliegende Vorlesungszuschnitt beschäftigt sich mit dem Pumping-Lemma (PPL) für reguläre Sprachen und dem PPL für kontextfreie Sprachen. Das PPL ist eine Eigenschaft, die alle Sprachen der jeweiligen zugehörigen Sprachklasse besitzen. Es macht Aussagen über Sprachen, deren Wörter strukturell nach einfachen Prinzipen definiert werden können. Für solche Sprachen gilt, dass sie, wenn sie Wörter einer bestimmten Mindestlänge enthalten, automatisch eine unendliche Menge weiterer Wörter enthalten müssen, die sich durch das ?Aufpumpen? der vorhandenen Wörter ergeben. Dabei orientiert sich die Vorlesung bei der Formulierung des PPLs bei regulären Sprachen an endlichen Automaten, bei kontextfreien Sprachen werden kontextfreie Grammatiken betrachtet. Es wird erklärt, wie anhand des entsprechenden PPLs Nachweise der Nicht-Regularität bzw. Nicht-Kontextfreiheit einer Sprache durchgeführt werden können.

Laufzeit (hh:mm:ss)

01:07:49

Serie

100 Übungsaufgaben zu Grundlagen der Informatik : Band I: Theoretische Informatik

Publiziert am

24.10.2013

Fachgebiet

Informatik

Lizenz

KITopen-Lizenz

Auflösung 1024 x 768 Pixel
Seitenverhältnis 4:3
Audiobitrate 31998 bps
Audio Kanäle 1
Audio Codec aac
Audio Abtastrate 22050 Hz
Gesamtbitrate 102046 bps
Farbraum yuv420p
Container mov,mp4,m4a,3gp,3g2,mj2
Medientyp video/mp4
Dauer 4069 s
Dateiname 2013-721_cam.mp4
Dateigröße 4.096 byte
Bildwiederholfrequenz 25
Videobitrate 64911 bps
Video Codec h264
Auflösung 1024 x 768 Pixel
Seitenverhältnis 4:3
Audiobitrate 32000 bps
Audio Kanäle 1
Audio Codec mp3
Audio Abtastrate 22050 Hz
Gesamtbitrate 918406 bps
Farbraum bgr24
Container avi
Medientyp video/x-msvideo
Dauer 4069 s
Dateiname 2013-721_download.avi
Dateigröße 4.096 byte
Bildwiederholfrequenz 25
Video Codec camtasia

Mediathek-URL

Embed-Code

100 Übungsaufgaben zu Grundlagen der Informatik : Band I: Theoretische Informatik Folgen 1-20 von 20
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. I - Kap. 3: Minimierung endlicher Automaten
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. I - Kap. 3: Minimierung endlicher Automaten
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. I - Kap. 0: Einführung in formale Sprachen und grundlegende Notationen
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. I - Kap. 0: Einführung in formale Sprachen und grundlegende Notationen
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. II - Kap. 9: Dateiorganisation
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. II - Kap. 9: Dateiorganisation
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. II - Kap. 8: Betriebssysteme
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. II - Kap. 8: Betriebssysteme
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. II - Kap. 7: Programmierung
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. II - Kap. 7: Programmierung
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. II - Kap. 6: Rechnerarchitektur, Speicherorganisation und Internettechnologien
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. II - Kap. 6: Rechnerarchitektur, Speicherorganisation und Internettechnologien
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. II - Kap. 5: Darstellung von Ziffern und Zahlen
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. II - Kap. 5: Darstellung von Ziffern und Zahlen
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. II - Kap. 4: Fehlerbehandlung, Huffman-Kodierung und Verschlüsselung
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. II - Kap. 4: Fehlerbehandlung, Huffman-Kodierung und Verschlüsselung
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. II - Kap. 3: Binary Decision Diagram (BDD)
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. II - Kap. 3: Binary Decision Diagram (BDD)
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. II - Kap. 2: Complementary Metal Oxide Semiconductor (CMOS)
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. II - Kap. 2: Complementary Metal Oxide Semiconductor (CMOS)
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. II - Kap. 1: Schaltnetze und Schaltwerke
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. II - Kap. 1: Schaltnetze und Schaltwerke
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. I - Kap. 10: Berechenbarkeits- und Komplexitätstheorie
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. I - Kap. 10: Berechenbarkeits- und Komplexitätstheorie
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. I - Kap. 9: Kontextsensitive und monotone Grammatiken
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. I - Kap. 9: Kontextsensitive und monotone Grammatiken
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. I - Kap. 8: Turingmaschinen
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. I - Kap. 8: Turingmaschinen
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. I - Kap. 7: Pumping Lemma
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. I - Kap. 7: Pumping Lemma
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. I - Kap. 6: Kontextfreie Grammatiken
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. I - Kap. 6: Kontextfreie Grammatiken
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. I - Kap. 5: Kellerautomaten
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. I - Kap. 5: Kellerautomaten
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. I - Kap. 4: Rechtslineare Grammatiken und Reguläre Ausdrücke
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. I - Kap. 4: Rechtslineare Grammatiken und Reguläre Ausdrücke
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. I - Kap. 2: Endliche Automaten ohne Ausgabe
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. I - Kap. 2: Endliche Automaten ohne Ausgabe
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. I - Kap. 1: Endliche Automaten mit Ausgabe
100 Übungsaufgaben zu Grundlagen der Informatik, Bd. I - Kap. 1: Endliche Automaten mit Ausgabe