1. Einführung

Im Anschluss an die grundlegenden Begriffe Abzählbarkeit, (rekursive) Aufzählbarkeit, Entscheidbarkeit (bzw. Rekursivität) sowie den Grundbegrifen zu einer formalen Sprache soll nun der Begriff der formalen Grammatik, der syntaktischen Ableitbarkeit der durch die Grammatik G definierten Sprache L(G) eingeführt werden. Mittels dieser Begriffe kann man dann die Chomsky Hierarchie definieren. Ausgehend von der Chomsky Hierarchie werden dann konkrete Untersuchungen zu den ausgewählten Sprachtypen 'reguläre Sprachen' sowie 'kontextfreie Sprachen' mitsamt den zugehörigen Automatentypen 'endlicher Automat' sowie 'Kellerautomat' angestellt. Letzteres aber erst in der Folgevorlesung.

START

2. Grammatik: informell

Der Begriff der formalen Grammtik wird zunächst anhand eines Beispiels aus dem Alltag eingeführt.

(a) Ein Textfragment

Wir betrachten einige einfache Sätze der deutschen Sprache.

1. Hans ist gross.




2. Hans lacht.




3. Das Auto fährt schnell.




4. Susi und Hans treffen sich.




5. Hans vergisst das rote Buch.

(b) Das Alphabet V

Die Menge der Buchstaben, die in diesem Textfragment vorkommen, sind eine Teilmenge der Zeichen {a,...,z, A, .. Z,ä,ö,ü, Ä,Ö,Ü,.}. Der Einfachheit halber nehmen wir an, dass unser Alphabet V aus allen diesen Zeichen besteht: V = {a,...,z, A, .. Z,ä,ö,ü, Ä,Ö,Ü,.} (man beachte, dass wir den Punkt '.' als Zeichen zulassen!).

(c) Liste der Worte V* über V

Nun betrachten wir die Menge aller Wörter V', die in diesem Textfragmet vorkommen. V' ist nur eine Teilmenge der möglichen Wörter V* über dem Alphabet V:

1. Hans

2. ist

3. gross

4. lacht

5. .

6. Das

7. Auto

8. fährt

9. schnell

10. Susi

11. und

12. treffen

13. sich

14. vergisst

15. rote

16. Buch

(d) Wortkategorien und Lexikon

Diese Worte bilden in der Sprache konkrete Objekte, mittels denen kommuniziert wird. Regeln, die über diesen Objekten operieren (bzw. eine Grammatik als Menge von solchen Regeln (s.u.)), müssen über diese konkreten Objekte in einer abstrakteren Weise sprechen. Die Sprachwissenschaftler haben daher schon vor mehr als tausend Jahren sogenannte Wortkategorien erfunden, um Mengen konkreter Wörter unter bestimmten Sammelbezeichnungen (Kategorien, Klassen) zusammenzufassen. Bis heute haftet solchen Wortklassifizierung eine gewisse Beliebigkeit und Unschärfe an. Im Folgenden werden einige Wortkategorien rein experimentell eingeführt. Die Liste von Paaren [Wortkategorie ---> Wort] nennt man im Rahmen einer formalen Grammatik auch ein Lexikon

1. N ---> Hans, Susi

2. AUX ---> ist

3. ADJ ---> gross, schnell, rote

4. V ---> lacht, fährt, treffen, vergisst

5. ENDM ---> .

6. DET ---> Das

7. CN ---> Auto, Buch

8. CONJ ---> und

9. RPR ---> sich

Die Schreibweise 'A ---> b' wird auch Ersetzungsregel (oder Produktion) genannt. Sie besagt, dass die Zeichenkette A duch die zeichenkette b ersetzt werden kann.

(e) Sätze

Mit diesen Vereinbarungen könnte man das Textfragment jetzt wie folgt umschreiben:

1. (N,Hans) (AUX,ist) (ADJ,gross) (ENDM,.)

2. (N,Hans) (V, lacht) (ENDM,.)

3. (DET,Das) (CN,Auto) (V,fährt) (ADJ,schnell) (ENDM,.)

4. (N,Susi) (CONJ,und) (N,Hans) (V,treffen) (RPR,sich) (ENDM,.)

5. (N,Hans) (V,vergisst) (DET,das) (ADJ,rote) (CN,Buch) (ENDM,.)

Da alle diese Wortfolgen Sätze sein sollen (Kategorie 'S'), kann man die Gleichungen einführen:

1. S ---> N AUX ADJ ENDM

2. S ---> N V ENDM

3. S ---> DET CN V ADJ ENDM

4. S ---> N CONJ N V RPR ENDM

5. S ---> N V DET ADJ CN ENDM

(h) Optimierungen

Die Ersetzungsregeln für S wirken noch sehr umständlich. Man kann versuchen, Optimierungen dadurch einzuführen, dass man 'Zwischenkategorien' einführt, etwa wie folgt:

1. S ---> NP VP

2. NP ---> N | DET CN | DET ADJ CN | N CONJ N

3. VP ---> AUX ADJ | V | V RPR

Damit würde sich dann die folgende Regelmenge ergeben:

1. S ---> NP VP

2. NP ---> N | DET CN | DET ADJ CN | N CONJ N

3. VP ---> AUX ADJ | V | V RPR

4. N ---> Hans, Susi

5. AUX ---> ist

6. ADJ ---> gross, schnell, rote

7. V ---> lacht, fährt, treffen, vergisst

8. ENDM ---> .

9. DET ---> Das

10. CN ---> Auto, Buch

11. CONJ ---> und

12. RPR ---> sich

(f) Ein erster Syntaxbaum

Mit diesen Regeln könnte man dann einen sogenannten Syntaxbaum erzeugen:

Ein Syntaxbaum zu den Beispielregeln

In Verbindung mit dem Lexikon kann man jetzt alle Sätze generieren, die diese Regeln festlegen. Man stellt leicht fest, dass man jetzt mehr Sätze erzeugen kann, als im ursprünglichen Textfragment vorkommen (=> die Grammtik verallgemeinert, generalisiert!). Ausserdem stellt man fest, dass man Sätze bilden kann, die ein deutscher Sprecher nicht unbedingt als 'volständig korrekt' akzeptieren würde. Beispiele:

1. Hans vergisst sich (Kann man akzeptieren)

2. Hans lacht sich (würde man noch ergänzen)

3. Hans treffen sich (statt treffen erwartet man trifft und noch eine Ergänzung)

4. Hans fährt sich (mit Ergänzung vielleicht akzeptabel)

5. Hans und Susi ist gross (mit sind statt ist akzeptabel)

6. Hans und Susi ist schnell (mit sind akzeptabel)

7. Hans und Susi ist rote (mit sind rot akzeptabel)

Man sieht, dass man bei natürlichen Sprachen neben der reinen Form zusätzlich sogenannte implizite Faktoren wie Anzahl der Personen, Geschlecht, Aktionszeit usf. mit berücksichtigen muss. Und diese zusätzlichen impliziten Faktoren interagieren über Wortgrenzen hinweg zwischen verschiedenen Kategorien. Diese und weitere Faktoren stellen hohe Anforderungen an eine formale Grammatik der natürlichen Sprachen. Die Tatsache, dass es bis heute keine wirklich umfassende und allgemein akzeptierte formale Grammatik natürlicher Sprachen gibt, lässt erahnen, dass diese Aufgabe nicht leicht zu lösen ist. Im Rahmen der Informatik beschränkt man sich daher in der Regel auf solche Sprachen, die sich im Rahmen von formalen Grammatiken vollständig beschreiben und damit technisch nutzen lassen (Anmerkung: wie schon in vorausgehenden Vorlesungen bemerkt, ist diese Haltung der Informatik in der Zukunft kaum haltbar; es besteht schon heute die klare Herausforderung an die Informatik, leistungsfähigere sprachliche Schnittstellen bereit zu stellen. Diese können aber nur mit leistungsfähigeren theoretischen Modellen realisiert werden. Dazu gehören notwendigerweise semantische, pragmatische und adaptive Elemente!).

START

3. Grammatik: formal und Beispiele

Für formale Grammatiken hat sich eine allgemeine Schreibweise eingebürgert, die wir hier als Struktur im Sinne der Algebra und der Wissenschaftstheorie wiedergeben.

x ist eine formale Grammatik [FG(x)] gdw x = < <V,T,{S} > P> mit

1. V := Menge der Variablen (oder nicht-terminalen Elemente)

2. T := Menge der terminalen Elemente

3. S := Das Startsymbol (steht für Satz ('sentence')); es gilt {S} C V

4. P := Die Menge der Ersetzungs- bzw. Produktionsregeln. Es gilt allgemein P C (V ∪ T)⁺ x (V ∪ T)*. Dies bedeutet, auf der linken Seite einer Erzeugungsregel muss mindestens ein Zeichen stehen, die rechte Seite kann leer sein.

Man muss jetzt festlegen, was es heisst, dass man mit den Produktions-Regeln einer formalen Grammatik ein zulässiges Wort der Grammatik erzeugt bzw. ableitet.

1. y ist mit der formalen Grammatik g direkt ableitbar aus x [geschrieben: DABL(y,x,g) oder x =>_g y oder x |-_g y] gdw
   
   (E:a,b,k,k')( (a,b) ∈ P_g & x = kak' & y = kbk' & a ∈ (V_g ∪ T_g)⁺ & k,k',b ∈ (V_g ∪ T_g)^* )




2. y ist in g ableitbar aus x [ geschrieben: ABL(y,x,g) oder x ^*=>_g y oder x |--^*_g y] gdw
   
   (E:f)( SEQ(f) & (f:Nat ---> (V_g ∪ T_g)* & A:i,j)( i,j ∈ dm(f) & j =i+1 => DABL(f_j,f_i,g) & x = f₀ & y =f_len(f)-1 ))
   
   'SEQ(f)' heisst, dass f eine Folge ist (siehe mengentheoretische Grundbegriffe) und x ist das erste Element der Folge und y ist das letzte Element der Folge. Da der Index einer Folge mit Nat ab 0 läuft, hat das letzte Element einer Folge f den Index len(f)-1 = |dom(f)|-1.




3. L ist die durch g erzeugbare Sprache [L(g)] = { w | FG(g) & ABL(w,S_g,g) }
   
   Die durch die Grammatik g bestimmte Sprache besteht also aus allen Worten w, die sich aus dem Startelement S_g der Grammatik g ableiten lassen.




4. Grammatik g ist äquivalent zu Grammtik g' AEQUIVALENT(g,g')] gdw FG(g) & FG(g') & L(g) = L(g')

Wenden wir das Schema auf das vorausgehende Beispiel an, dann würden wir folgende konkrete Grammatik bekommen:

x ist die formale Grammatik FG1 gdw x = < <V1,T1,{S} > P1> mit

1. V1 = {A, .., Z}

2. T1 = {a,...,z, A, .. Z,ä,ö,ü, Ä,Ö,Ü,.} und es gilt: V1 ∩ T1 = 0

3. S = bleibt

4. P :=

   1. S ---> NP VP

   2. NP ---> N | DET CN | DET ADJ CN | N CONJ N

   3. VP ---> AUX ADJ | V | V RPR

   4. N ---> Hans | Susi

   5. AUX ---> ist

   6. ADJ ---> gross | schnell | rote

   7. V ---> lacht | fährt | treffen | vergisst

   8. ENDM ---> .

   9. DET ---> Das

   10. CN ---> Auto | Buch

   11. CONJ ---> und

   12. RPR ---> sich

Ein Ausdruck wie

CN ---> Auto | Buch

ist eine verkürzende Schreibweise für

CN ---> Auto
or

CN ---> Buch

Hier ein anderes Beispiel einer einfachen formalen Grammatik g1.

FG(g1) und g1 = < <V_g1,T_g1,{S_g1} >, P_g1> mit den Werten:

1. V_g1 = {E,T,F},

2. T_g1 = {(,),a,+,*}

3. S_g1 = E

4. P_g1 = {(E,T), (E,E + T), (T,F),(T,T * F),(F,a),(F,(E))}

Wir schreiben statt V_g1, T_g1, S_g1, P_g1 einfach V1, T1, S1 und P1.

Zum Verständnis, wie die einzelnen Regeln aus P1 zustandekommen, hier eine ausführliche Darstellung der Elementschaft von P1:

P1 C (V1 ∪ T1)⁺ x (V1 ∪ T1)*

(a,b) ∈ P1

gdw

(a,b) ∈(V1 ∪ T1)⁺ x (V1 ∪ T1)*

gdw

a ∈ (V1∪T1)⁺ & b ∈ (V1∪T1)*

gdw

{(E,T), (E,E + T), (T,F),(T,T * F),(F,a),(F,(E))}

auch geschrieben als:

{(E --> T), (E --> E + T), (T --> F),(T -->T * F),(F -->a),(F --> (E))}

Ableiten

Satz: E *=>_g1 a * a + a ( E |--*_g1 a * a + a )

a * a + a ist in g1 ableitbar aus E

gdw

(E:f)( SEQ(f) & (f:Nat ---> ({E,T,F} ∪ {(,),a,+,*})* & A:i,j)( i,j ∈ dm(f) & j =i+1 => DABL(f_j,f_i,g1) & E = f₀ & a * a + a =f_len(f)-1 ))

START

4. Zuordnung von formaler Grammatik zu Syntaxbaum

Anhand der Definition von Bäumen kann man eine direkte Zuordnung herstellen zwischen formalen Grammatiken einerseits und Bäumen andererseits. Dies kann man in einem Algorithmus fassen:

Gegeben ist eine formale Grammatik g mit < <V_g,T_g,{S_g} >, P_g>

Gesucht ist ein gerichteter Graph g' mit < <E_g', {r_g'} >, K_g'> mit den Werten E_g' = V_g ∪ T_g und r_g' = S_g . Dies bedeutet, die Variablen V_g und terminalen Symbole T_g von g werden in die Menge der Ecken E_g' von g' abgebildet; dabei wird das Startsymbol S_g mit dem Wurzelknoten r_g' von g' identifiziert. Schliesslich werden die Produktionsregeln P_g in die Menge der Kanten K_g' abgebildet.

Man kann dann auf der Basis der Kanten K_g' dadurch einen Baum konstruieren, dass man, beginnend mit dem Wurzelknoten r_g', alle Nachfolger der Wurzel über Pfeile mit der Wurzel verbindet, dann alle Nachfolger der Nachfolger usw.

START

5. Chomsky Hierarchie

Wie sich gezeigt hat, ist die oben eingeführte Definition einer formalen Grammatik in ihrer Allgemeinheit so stark, dass sie für solche Anwendungen, in denen in endlichen Zeitintervallen Entscheidungen getroffen werden müssen, solche Entscheidungen entweder garnicht möglich sind oder aber nur mit einem unakzeptablen Zeitaufwand. Dies hat dazu geführt, dass man auch schwächere Formen von formalen Grammatiken untersucht hat, also solche Grammatiken, deren Sprachen sich mittels Automaten in vertretbaren Zeiten 'erkennen' lassen.

Die Formulierung vertretbarer Zeitaufwand ist in diesem Zusammenhang mehrfach ambivalent:

1. Anwendungskontext: bei klassischer Briefpost erwartet man Antworten in Zeiträumen von einigen Tagen; bei email möglicherweise in Stunden oder Minuten; beim Bremsen im Auto erwartet man 'sofort' eine Reaktion usw.




2. Hardware: je nach verfügbarer Hardware kann der gleiche Berechnungsprozess Stunden, Minuten oder Sekunden dauern oder gar noch weniger Zeit beanspruchen.




3. Rekursiv/ Entscheidbar: das Problem ist grundsätzlich entscheidbar, auch wenn es, wie im Fall der Typ-2-Sprachen (s.u.) möglicherweise in der Praxis nicht nutzbar ist.

Im vorliegenden Kontext ist der Fall der entscheidbaren Sprachen von grösstem Interesse. Die folgende auf Noam CHOMSKY zurückgehende Klassifizierung hat sich eingebürgert:

1. g ist eine formale Grammatik vom Typ 0 [FG(g,0)] (Phrasenstrukturgrammatik, 'Phrase Structure Grammar' [PSG]) gdw
   FG(g) & ∀(v,w) ( (v,w) ∈ P ==> v ∈ (V ∪ T)+ & w ∈ (V ∪ T)* )




2. g ist eine formale Grammatik vom Typ 1 [FG(g,1)](Kontextsensitive Grammatik, 'Contextsensitive Grammar' [CSG]) gdw
   FG(g) & (A:u,w)( (u,w) ∈ P_g => (E:a,b,X,p)([u = aXb & w = apb & X ∈ V_g &
   (Fall 1:)[[a,b ∈ (V_g ∪ T_g)^* & p ∈ ( V_g ∪ T_g)⁺ ]
   or
   (Fall 2:) [u = S_g & p = ε & ¬∃ (u',w')((u',w') ∈ P & S_g ∈ rn(w))]
   )
   
   Der entscheidende Punkt ist, dass die Ersetzung von X durch p nur bei Vorliegen des Kontextes 'a_b' erlaubt ist. Ferner darf p nicht leer sein; Falls man p=ε zulässt, dann darf das Startsymbol S nicht mehr auf der rechten Seite einer Produktion auftreten.




3. g ist eine formale Grammatik vom Typ 2 [FG(g,2)](Kontextfreie Grammatik, 'Contextfree Grammar' [CFG]) gdw
   FG(g) & (A:u,w)( (u,w) ∈ P_g => u ∈ V_g & w ∈ (V ∪ T)* )




4. g ist eine formale Grammatik vom Typ 3 [FG(g,3)](Reguläre Grammatik, 'Regular Grammar')gdw
   FG(g,2) & RECHTSLINEAR(g) + LINKSLINEAR(g))




5. g ist eine rechtslineare formale Grammatik vom Typ 3 [RLFG(g,3)] gdw
   FG(g,3) & (A:u,w)( (u,w) ∈ P_g => (E:a,B)(B in V_g & a in T_g & [w=a or w=aB] ))




6. g ist eine linkslineare formale Grammatik vom Typ 3 [LLFG(g,3)] gdw
   FG(g,3) & (A:u,w)( (u,w) ∈ P_g => (E:a,B)(B in V_g & a in T_g & [w=a or w=Ba] ))




L ist die durch eine formale Grammatik vom Typ i erzeugte Sprache [L(g,i)] gdw
L(g,i) = { w | ABL(w,S_g,g) & FG(g,i)}

Satz: L(g,3) C L(g,2) C L(g,1) C L(g,0)

Ein Beispiel für eine kontextsensitive Grammatik ist die Grammatik g2:

FG(g2,1) und g2 = < <V_g2,T_g2,{S_g2} >, P_g2> mit den Werten:

V_g2 = {S,B,C},
T_g2 = {a,b,c},
S_g2 = S
P_g2 = {(S,aSBC), (S,aBC), (CB,BC),(aB,ab),(bB,bb),(bC,bc), (cC,cc)}

Ein Beispiel für eine kontextfreie Grammatik war die vorausgehende Grammatik g1.

Zwei Beispiele für reguläre Grammatiken sind die Grammatiken g3 und g4

FG(g3,3) und g3 = < <V_g3,T_g3,{S_g3} >, P_g3> mit den Werten:

V_g3 = {S},
T_g2 = {0},
S_g2 = S
P_g2 = {(S,0S), (S,0) }

FG(g4,3) und g4 = < <V_g4,T_g4,{S_g4} >, P_g4> mit den Werten:

V_g4 = {S},
T_g4 = {0,1},
S_g4 = S
P_g4 = {(S,0), (S,1), (S,0S), (S,1S) }

START

6. Beispiel einer Typ-3-Grammatik und Sprache

Es wird jetzt das Beispiel einer Typ-3-Grammatik g4 im Format einer rechtslinearen Grammatik gegeben, die die folgende Sprache definiert: L(g4,3) = {anne, anke, abzug, ablage}

FG(g4,3) mit g4 = < <V_g4,T_g4,S_g4 > P_g4>

mit

V_g4 = {S, X, Y, Z, G, H, M, V}

T_g4 = {a, b, e, g, k, l, n, u, z}

P_g4 = {(S,aX), (X,bY),(X,nZ),(Y,zV),(Y,lW),(V,uM),(W,aG),(G,gH),(Z,nG),(Z,kG),(M,g),(H,e)}

Vereinbarungsgemäss kann man statt (S,aX) auch schreiben S ---> aX und statt '(X,bY),(X,nZ)' kann man auch schreiben X --> bY | nZ.

Laut Definition ist ein Wort w dann in der Sprache L(g4,3) wenn w in g4 ableitbar ist, also S_g4 *=>_g4 w, und g4 ist eine formale Grammatik vom Typ3, also FG(g4,3). Man müsste also zeigen, dass die Worte {anne, anke, abzug, ablage} alle ableitbar sind und auch nur genau diese.

Eine Möglichkeit, dies zu tun besteht darin, dass man bezogen auf den Syntaxbaum ein allgemeines Verfahren (Algorithmus) definiert, das diesen Baum systematisch absucht. Ein Verfahren wäre das folgende (informelle Beschreibung):

1. Beginne bei dem Wurzelknoten S

2. Markiere letzten Knoten und gehe zum nächsten. Wenn es Alternativen gibt, wähle den am weitesten links liegenden Knoten.

3. Ist der Pfad zu Ende ohne ein terminales Element, dann Fehlermeldung

4. Andernfalls gebe den Pfad aus.

5. Backtracking: suche rückwärts den nächsten noch nicht markierten Pfad

6. Falls es keinen mehr gibt: Ende

7. Andernfalls setze fort bei 2

Wenn dieses Verfahren keine Fehlermeldung produziert, dann generiert es die Menge aller möglichen Pfade. Hier ein Beispiel für Ableitungen nach diesem Verfahren:

1. S (S ---> aX)

2. aX (X ---> bY)

3. abY (Y ---> zV)

4. abzV (V ---> uM)

5. abzuM (M ---> g)

6. abzug

Ein Pfad im Syntaxbaum ist jetzt markiert. Mittels Backtracking wird jetzt rückwärts nach einer möglichen Fortsetzung gesucht. Diese ist hinter dem Knoten 'bY' gegeben. Es wird also hier eine zweite Ableitung versucht:

1. S (S ---> aX)

2. aX (X ---> bY)

3. abY (Y ---> lW)

4. ablW (W ---> aG)

5. ablaG (G ---> gH)

6. ablagH (H ---> e)

7. ablage

Entsprechend leitet man die beiden restlichen Worte 'anne' und 'anke' ab. Das Verfahren stoppt an dieser Stelle, da alle Knoten markiert sind. Auserdem wurde keine Fehlermeldung ausgegeben. Also wurden genau die Worte erzeugt, die die Sprache definieren. Damit wäre nun ein Beispiel für eine reguläre Grammatik und der durch sie definierten Sprache gegeben. Im nächsten Beispiel wird gezeigt, wie ein endlicher deterministischer Automat eine solche reguläre Sprache erkennen kann.

Es wird jetzt das Beispiel einer regulären Grammatik g5 im Format einer rechtslinearen Grammatik gegeben, die die gleiche Sprache wie die Grammatik g4 definiert: L(g5,3) = {anne, anke, abzug, ablage}. Trotzdem unterscheidet sich die Grammatik g5 von der Grammatik g4 durch die benutzten Regeln:

FG(g5,3) mit g5 = < <V_g5,T_g5,S_g5 > P_g5>

mit

V_g5 = {S, X₁, X₂, Y₁, Y₂, Z₁, Z₂, G, H, M, V}

T_g5 = {a, b, e, g, k, l, n, u, z}

P_g5 = {(S,aX₁),(S,aX₂),(X₁,bY₁),(X₁,bY₂),(X₂,nZ₁ ),(X₂,nZ₂), (Ysub>1,zV),(Y₂,lW),(V,uM), (W,aG),(G,gH),(Z₁,nG),(Z₂,kG),(M,g),(H,e)}

Man sieht, dass durch die Änderung der Produktionsregeln von g5 zusätzliche Alternativen entstehen.

Für die Ableitung (bzw. Erzeugung) von Worten mit der Grammatik g5 gelten die gleichen Regeln wie oben im Fall der Grammatik g4.

7. Fragen und Aufgaben

Einige Fragen:

1. Geben Sie die Definition für eine formale Grammatik im allgemeinen Fall an und erklären Sie die verschiedenen Komponenten.

2. Was bedeutet es, dass ein Ausdruck E' mit einer formalen grammatik G direkt ableitbar ist aus einem Ausdruck E?

3. Was bedeutet es, dass ein Ausdruck E' mit einer formalen grammatik G ableitbar ist aus einem Ausdruck E?

4. Wie definiert man die durch eine formale Grammatik G erzeugbare Sprache L(G)?

5. Unter welchen Bedingungen sind zwei formale Grammatiken G und G' formal äquivalent?

6. Welche Funktion hat ein Syntaxbaum relativ zu einer formalen Grammatik G?

7. Was wird durch die Chomsky-Heirarchie definiert?

8. Wodurch unterscheiden sich die Sprachen, die durch die Chomsky Hierarchie unterschieden werden?

9. Wie ist das Verhältnis der Sprachen untereinander, die durch die Chomsky Hierarchie unterschieden werden?

Einige Aufgaben:

1. Gegeben sei das folgendes einfaches Textfragment: "Die Ampel ist rot. Das schwarze Auto stoppt. Peter geht über die Strasse. Es regnet. Die Ampel wird grün. Das Auto startet und verschwindet." Analysieren Sie diesen Text und konstruieren Sie eine formale Grammatik, mit der sich alle Sätze des Textfragmentes ableiten lassen.

2. Geben Sie Ableitungen für die folgenden drei Sätze an: "Die Ampel ist rot", "Peter geht über die Strasse", "Die Ampel wird grün".

3. Folgende Sätze sollen mit ihrer Grammatik nicht ableitbar sein: "Das Ampel ist rot", "schwarze Auto stoppt.","Die Auto startet."

4. Konstruieren Sie einen Syntaxbaum zu ihrer Grammatik.

5. Geben Sie das Beispiel einer Sprache an, die sich durch eine Typ2-Grammatik beschreiben lässt, nicht aber durch eine Typ3-Grammatik.

START