KIT-Bibliothek

100 Übungsaufgaben zu Grundlagen der Informatik, Bd. I - Kap. 9: Kontextsensitive und monotone Grammatiken

Author

Hartmut Schmeck

Participating institute

KIT-Bibliothek (BIB)

Genre

Vorlesung

Description

Der vorliegende Vorlesungszuschnitt beschäftigt sich mit kontextsensitiven und monotonen Grammatiken (Typ-1-Grammatiken). Kontextsensitive und monotone Grammatiken sind in ihrer Sprachmächtigkeit zueinander äquivalent und entsprechen der von linear beschränkten Automaten. Eine kontextsensitive Grammatik enthält nur Produktionen, bei denen ein einzelnes Nonterminalsymbol auf eine beliebige Kombination von Nonterminal- und Terminalsymbolen abgebildet wird (mit Ausnahme des leeren Wortes), wobei aber ein gewisser ?Kontext? betrachtet werden muss, in dem sich das Nonterminalsymbol befindet, also einige der Zeichen, die in dem abgeleiteten Wort direkt vor oder hinter dem zu ersetzenden Nonterminalsymbol auftreten. Eine monotone Grammatik ist nur dadurch eingeschränkt, dass die rechte Seite nicht kürzer werden darf als die linke Seite. Es wird gezeigt, dass die beiden Grammatik-Typen dem Typ 1 der Chomsky-Hierarchie entsprechen, und anhand von Beispielen wird die formale Definition einiger Typ-1-Sprachen dargestellt.

Duration (hh:mm:ss)

00:27:56

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 32001 bps
Audio channels 1
Audio Codec aac
Audio Sample Rate 22050 Hz
Total Bitrate 100535 bps
Color Space yuv420p
Container mov,mp4,m4a,3gp,3g2,mj2
Media Type video/mp4
Duration 1676 s
Filename 2013-723_cam.mp4
File Size 4.096 byte
Frame Rate 25
Video Bitrate 63394 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 925371 bps
Color Space bgr24
Container avi
Media Type video/x-msvideo
Duration 1676 s
Filename 2013-723_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