KIT Library
suchen
KIT-Bibliothek
KIT Library Media Portal

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

Author

Hartmut Schmeck

Participating institute

KIT-Bibliothek (BIB)

Genre

Vorlesung

Description

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.

Duration (hh:mm:ss)

01:07:49

Series

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

Published on

24.10.2013

Subject area

Computer science

License

KITopen Licence

Resolution 1024 x 768 Pixel
Aspect ratio 4:3
Audio bitrate 31998 bps
Audio channels 1
Audio Codec aac
Audio Sample Rate 22050 Hz
Total Bitrate 102046 bps
Color Space yuv420p
Container mov,mp4,m4a,3gp,3g2,mj2
Media Type video/mp4
Duration 4069 s
Filename 2013-721_cam.mp4
File Size 4.096 byte
Frame Rate 25
Video Bitrate 64911 bps
Video Codec h264
Resolution 1024 x 768 Pixel
Aspect ratio 4:3
Audio bitrate 32000 bps
Audio channels 1
Audio Codec mp3
Audio Sample Rate 22050 Hz
Total Bitrate 918406 bps
Color Space bgr24
Container avi
Media Type video/x-msvideo
Duration 4069 s
Filename 2013-721_download.avi
File Size 4.096 byte
Frame Rate 25
Video Codec camtasia

Media URL

Embed Code

100 Übungsaufgaben zu Grundlagen der Informatik : Band I: Theoretische Informatik Episodes 1-20 of 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