Prof. Dr. R. Laue
Dr. A. Kohnert                                                                                                                                             SS 2005
Compilerbau und formale Sprachen
                                Übungsblatt 4
                              

URL:         /axel/compiler_ss05_blatt4.html

 Dieses Blatt wird am 11.5.2005 besprochen. Danach wird lex und evtl auch schon yacc vorgestellt.

Aufgabe 9

Geben Sie eine kontextfreie Grammatik  (vollständige Definition) für die Sprache L9:={0n+1 1n 0m 1 2m | m,n >0 } an.
Beweis!


Aufgabe 10

Überführen Sie die Grammatik (Kleinbuchstaben=Terminalsymbole, S Startsymbol)

S-->ASA | aB
A-->B|S|a
B-->b

in Chomsky Normalform


Aufgabe 11
Gegeben seien zwei kontextfreie Sprache A und B. Man zeige

- die Vereinigung  A U B ( = { u | u aus A oder u aus B} ) ist kontextfrei.
- die Verkettung  AB (= { uv | u aus A und v aus B } ) ist kontextfrei.
- das Komplement A\ B (= { u | u ist aus A aber nicht aus B} ) muß nicht kontextfrei sein.