7. Übung, Theoretische Grundlagen der Informatik · Konstruktion von Grammatiken Chomsky-0-Grammatiken und DTMs Sprache der korrekten Klammerausdr ucke¨ Der Cocke-Younger-Kasami-Algorithmus

Theoretische Grundlagen der Informatik

7. Ubungstermin · 7. Januar 2020Guido Bruckner

KIT – Die Forschungsuniversitat in der Helmholtz-Gemeinschaft

INSTITUT FUR THEORETISCHE INFORMATIK · LEHRSTUHL ALGORITHMIK

www.kit.edu

Ubung

Guido Bruckner – 7. Ubung, Theoretische Grundlagen der Informatik Institut fur Theoretische InformatikLehrstuhl Algorithmik

Ubersicht

Inhalt

Konstruktion von GrammatikenChomsky-0-Grammatiken und DTMs

Sprache der korrekten Klammerausdrucke

Der Cocke-Younger-Kasami-AlgorithmusNEA aus Chomsky-3-GrammatikEindeutige und mehrdeutige Grammatiken

Chomsky-Normalform

Grammatiken und Chomsky-Hierarchie

Chomsky-2-Grammatiken

Organisatorisches

Evaluation

1


Chomsky-Hierarchie

(semi-entscheidbar)Typ 0

Menge aller Sprachen

(kontextsensitiv)Typ 1

(kontextfrei)Typ 2

(regular)Typ 3

2


Chomsky-Hierarchie



alleSprachen

semi-entscheidbareSprachen

entscheidbareSprachen

aus Ubung 3:

(entscheidbar)


(kontextfrei)Typ 2

(regular)Typ 3

2


Chomsky-Hierarchie



Chomsky-0-Gram.

Chomsky-1-Gram.

G = (Σ, V , S, R)R beliebig

u → v , |u| ≤ |v |u ∈ V +, S /∈ vS → ε

Chomsky-2-Gram.A→ v , A ∈ Vv beliebig

Chomsky-3-Gram.A→ v , A ∈ Vv ∈ {ε} ∪ Σ · V


(kontextfrei)Typ 2

(regular)Typ 3

(entscheidbar)

2


Chomsky-Hierarchie



Chomsky-0-Gram.

Chomsky-1-Gram.


u → v , |u| ≤ |v |u ∈ V +, S /∈ vS → ε




(kontextfrei)Typ 2

(regular)Typ 3

(entscheidbar)

NTM akzeptiert LDTM akzeptiert L

NTM mit Platz-bedarf n erkenntWorter d. Lange nin L⇒ NT APE(n)

CYK-Alg. erkenntL in polynom. Zeit

⇒ Chomsky-Normalform

NEA erkennt LDEA erkennt L

2


Chomsky-Hierarchie



Chomsky-0-Gram.

Chomsky-1-Gram.


u → v , |u| ≤ |v |u ∈ V +, S /∈ vS → ε




(kontextfrei)Typ 2

(regular)Typ 3

(entscheidbar)






2


Chomsky-0-Grammatiken und DTMs

Satz aus der Vorlesung (Vorlesung 13, 17.12.2019):Die von Typ-0-Grammatiken erzeugten Sprachen sind genau die vonnichtdeterministischen Turingmaschinen akzeptierten Sprachen.

L ist Typ 0, d.h.,es gibt Grammatik G

mit L(G) = L.

Es gibt nichtdeterm.TMM, die L

akzeptiert.⇔

A B

A B⇔

3





mit L(G) = L.


akzeptiert.⇔

Beweis aus der Vorlesung von :

A B

A B⇒

Schreibe S auf das Band.

Repeat

Wahle nichtdeterministisch eine anwendbare Ableitungsregel.Vergleiche das erzeugte Wort mit der Eingabe w .Bei Gleichheit wird w akzeptiert.

Wir konstruieren eineNTM, die L akzeptiert.

A B⇔

3





mit L(G) = L.


akzeptiert.

Es gibtdeterministische TMM, die L akzeptiert.

⇔ ⇔A B

C

A B⇔

In der Vorlesung wurde dann bewiesen.⇒ AC

Und es gilt auch allgemein, dass .⇒

Beweis aus der Vorlesung von .A B⇒

B C

3





mit L(G) = L.


akzeptiert.


⇔ ⇔A B

C

A B⇔

In der Vorlesung wurde dann bewiesen.⇒ AC

Und es gilt auch allgemein, dass .⇒

Beweis aus der Vorlesung von .A B⇒

B C

DTMs und NTMs sind gleich machtig. (Wenn Laufzeit egal ist.)

3





mit L(G) = L.


akzeptiert.


⇔ ⇔

Beweis aus der Vorlesung von :

A B

C

A B⇒

Schreibe S auf das Band.

Repeat

Wahle nichtdeterministisch eine anwendbare Ableitungsregel.Vergleiche das erzeugte Wort mit der Eingabe w .Bei Gleichheit wird w akzeptiert.

Wir konstruieren eineNTM, die L akzeptiert.

A B⇔

3





mit L(G) = L.


akzeptiert.


⇔ ⇔A B

C

Hier beweisen wir :A ⇒

Fur i = 1, 2, 3, . . .

Wir konstruieren eineDTM, die L akzeptiert.

C

A B⇔

Fur jede Folge F von genau i Ableitungsregeln

Schreibe S auf das Band.Wenn F anwendbar, vergleiche erzeugtes Wort mit der Eingabe w .Bei Gleichheit wird w akzeptiert, ansonsten das Band geloscht.

3


Chomsky-Hierarchie



Chomsky-0-Gram.

Chomsky-1-Gram.


u → v , |u| ≤ |v |u ∈ V +, S /∈ vS → ε




(kontextfrei)Typ 2

(regular)Typ 3

(entscheidbar)






4


Chomsky-Hierarchie



Chomsky-0-Gram.

Chomsky-1-Gram.


u → v , |u| ≤ |v |u ∈ V +, S /∈ vS → ε




(kontextfrei)Typ 2

(regular)Typ 3

(entscheidbar)






4


Chomsky-Hierarchie



Chomsky-0-Gram.

Chomsky-1-Gram.


u → v , |u| ≤ |v |u ∈ V +, S /∈ vS → ε




(kontextfrei)Typ 2

(regular)Typ 3

(entscheidbar)






4


Konstruktion von Grammatiken

Geben Sie fur die folgende Sprache eine Grammatik an.L = {aibjck ∈ {a, b, c}? | i = j ∨ j = k}

5




1. Schritt: Von welchem Typ ist die Sprache?

5




1. Schritt: Von welchem Typ ist die Sprache? Typ 2

5





2. Schritt: Grammatik vom Typ 2 formal definieren und formulieren.

Typ 2

5




G = (Σ, V , S, R) Σ = {a, b, c} V = {S, T , U, V , W}



Typ 2

5




G = (Σ, V , S, R) Σ = {a, b, c} V = {S, T , U, V , W}S → TU | VW ,T → aTb | ε,U → Uc | ε,W → bWc | ε,V → Va | ε.

R = {

}



Typ 2

5



Geben Sie fur die folgende Sprache eine Grammatik an.L = {ww | w ∈ {0, 1}?}

6





6




1. Schritt: Von welchem Typ ist die Sprache? Typ 1

6






Typ 1

6




G = (Σ, V , S, R) Σ = {0, 1} V = {S, Xi , Ri , Li , T}



Typ 1

fur i ∈ {0, 1}

6




G = (Σ, V , S, R) Σ = {0, 1} V = {S, Xi , Ri , Li , T}S → T | εT → 0TX0 | 1TX1 | L0R0 | L1R1

R = {

}



Typ 1

fur i ∈ {0, 1}

R0X0 → X0R0R0X1 → X1R0R1X0 → X0R1R1X1 → X1R1

L0X0 → L0R0L0X1 → L0R1L1X0 → L1R0L1X1 → L1R1

R0 → 0R1 → 1L0 → 0L1 → 1

6



Geben Sie fur die folgende Sprache eine Grammatik an.L = {ww | w ∈ {0, 1}?}G = (Σ, V , S, R) Σ = {0, 1} V = {S, Xi , Ri , Li , T}

S → T | εT → 0TX0 | 1TX1 | L0R0 | L1R1

R = {

}

fur i ∈ {0, 1}



R0 → 0R1 → 1L0 → 0L1 → 1

w = 1101 :

7




S → T | εT → 0TX0 | 1TX1 | L0R0 | L1R1

R = {

}

fur i ∈ {0, 1}



R0 → 0R1 → 1L0 → 0L1 → 1

S → 1 T X1 → 11 T X1X1 → 110 T X0X1X1 → 110L1 R1X0X1X1

w = 1101 :

7




S → T | εT → 0TX0 | 1TX1 | L0R0 | L1R1

R = {

}

fur i ∈ {0, 1}



R0 → 0R1 → 1L0 → 0L1 → 1


→ 110L1 X0R1X1X1 → 110L1 R0R1X1X1

w = 1101 :

7




S → T | εT → 0TX0 | 1TX1 | L0R0 | L1R1

R = {

}

fur i ∈ {0, 1}



R0 → 0R1 → 1L0 → 0L1 → 1


→ 110L1 X0R1X1X1 → 110L1 R0R1X1X1

→ 110L1 R0X1R1X1 → 110L1 X1R0R1X1 → 110L1 R1R0R1X1

w = 1101 :

7




S → T | εT → 0TX0 | 1TX1 | L0R0 | L1R1

R = {

}

fur i ∈ {0, 1}



R0 → 0R1 → 1L0 → 0L1 → 1


→ 110L1 X0R1X1X1 → 110L1 R0R1X1X1

→ 110L1 R0X1R1X1 → 110L1 X1R0R1X1 → 110L1 R1R0R1X1

→ · · · → 110L1 R1R1R0R1 → · · · → 1101 1101

w = 1101 :

7



Uber dem Alphabet Σ = {(,)} ist die Sprache L() der korrekten Klammer-ausdrucke gegeben.(a) Konstruieren Sie eine Typ-k -Grammatik mit maximalem k , die L()

erzeugt.

(b) Zeigen Sie, dass Ihre Grammatik genau L() erzeugt.

(c) Beweisen Sie die Maximalitat von k .

8




erzeugt.

8




erzeugt.

1. Schritt: Von welchem Typ ist die Grammatik?

8




erzeugt.

1. Schritt: Von welchem Typ ist die Grammatik? Typ 2

8




erzeugt.



Typ 2

8




erzeugt.

G = (Σ, V , S, R) Σ = {(, )} V = {S}



Typ 2

8




erzeugt.

G = (Σ, V , S, R) Σ = {(, )} V = {S}

S → (S)S | εR = {

}



Typ 2

8



Uber dem Alphabet Σ = {(,)} ist die Sprache L() der korrekten Klammer-ausdrucke gegeben.(b) Zeigen Sie, dass Ihre Grammatik genau L() erzeugt.

Zu zeigen ist: L(G) = L()

9





L(G) ⊆ L():

9





L(G) ⊆ L(): Klammern werden nie geloscht oder verschoben (Typ 2)

9






Jede Produktion, die eine Klammer erzeugt, erzeugtgenau ein Paar ( und ). Also hat jedes Wort in L(G)genauso viele offnende wie schließende Klammern.

9






Jede Produktion, die eine Klammer erzeugt, erzeugtgenau ein Paar ( und ). Also hat jedes Wort in L(G)genauso viele offnende wie schließende Klammern.

Jede Produktion, die mindestens eine Klammererzeugt, erzeugt ( vor ). Also beinhaltet fur jedes Wortw in L(G) jedes Prafix von w mindestens so vieleoffnende wie schließende Klammern.

9





L(G) ⊇ L():

9





L(G) ⊇ L(): Sei w in L() beliebig.

9






Algorithmus, der w erzeugt:

9






Algorithmus, der w erzeugt:w = (w1)w2, (w1) ist erstes Klammerpaar im Ausdruck

Fuhre S → (S)S aus

9






Algorithmus, der w erzeugt:w = (w1)w2, (w1) ist erstes Klammerpaar im Ausdruck

Fuhre S → (S)S aus

w = ε

Fuhre S → ε aus

9



Uber dem Alphabet Σ = {(,)} ist die Sprache L() der korrekten Klammer-ausdrucke gegeben.(c) Beweisen Sie die Maximalitat von k .

10




L() ist nicht regular (Pumping-Lemma)

10





Regulare Sprachen entsprechen Chomsky-Typ 3

10





Regulare Sprachen entsprechen Chomsky-Typ 3

⇒ Chomsky-Typ 2 ist maximal.

10


Evaluation

Ausfullen und zum Gang reichen

Freitextfelder besonders hilfreich!

5 min Zeit

11


Chomsky-Hierarchie



Chomsky-0-Gram.

Chomsky-1-Gram.


u → v , |u| ≤ |v |u ∈ V +, S /∈ vS → ε




(kontextfrei)Typ 2

(regular)Typ 3

(entscheidbar)






12


Chomsky-Hierarchie



Chomsky-0-Gram.

Chomsky-1-Gram.


u → v , |u| ≤ |v |u ∈ V +, S /∈ vS → ε




(kontextfrei)Typ 2

(regular)Typ 3

(entscheidbar)






12


Chomsky-Normalform

Gegeben sei die kontextfreie Grammatik G = (Σ, V , S, R) mit Σ ={a, b, c, d}, V = {S, A, B, C, D} und R:

S → A | aB | aC, B → S | Ba, D → d | dDD,A→ B | C | cAd, C → D | c.

(a) Lasst sich der CYK-Algorithmus auf G (ohne Abanderungen) anwen-den? Begrunden Sie Ihre Antwort. Andern Sie gegebenfalls G ab.

(b) Prufen Sie, ob das Wort addd in L(G) liegt. Verwenden Sie dafur denCYK-Algorithmus.

13


Chomsky-Normalform

Gegeben sei die kontextfreie Grammatik G = (Σ, V , S, R) mit Σ ={a, b, c, d}, V = {S, A, B, C, D} und R:


(a) Lasst sich der CYK-Algorithmus auf G (ohne Abanderungen) anwen-den? Begrunden Sie Ihre Antwort. Andern Sie gegebenfalls G ab.


(a) Nein. Begrundung:G ist nicht in Chomsky-Normalform

Chomsky-Normalform:A→ BC oder A→ a mit A, B, C ∈ V und a ∈ Σ

13


Chomsky-Normalform

G = (Σ, V , S, R) mit Σ = {a, b, c, d}, V = {S, A, B, C, D} und R:


13


Chomsky-Normalform



1. Schritt: Alle Regeln sind der FormX → Y , Y ∈ V? oder X → a, a ∈ Σ

13


Chomsky-Normalform



1. Schritt:

S → A | aB | aC

B → S | Ba

D → d | dDD

A→ B | C | cAd

C → D | c

Alle Regeln sind der FormX → Y , Y ∈ V? oder X → a, a ∈ Σ

13


Chomsky-Normalform



1. Schritt:

S → A | aB | aC

B → S | Ba

D → d | dDD

A→ B | C | cAd

C → D | c

S → A | ZaB | ZaC

B → S | BZa

D → Zd | Zd DD

A→ B | C | ZcAZd

C → D | Zc

Za → a Zc → c Zd → d


13


Chomsky-Normalform



1. Schritt:

S → A | aB | aC

B → S | Ba

D → d | dDD

A→ B | C | cAd

C → D | c

S → A | ZaB | ZaC

B → S | BZa

D → Zd | Zd DD

A→ B | C | ZcAZd

C → D | Zc



13


Chomsky-Normalform



1. Schritt:

S → A | aB | aC

B → S | Ba

D → d | dDD

A→ B | C | cAd

C → D | c

S → A | ZaB | ZaC

B → S | BZa

D → Zd | Zd DD

A→ B | C | ZcAZd

C → D | Zc



13


Chomsky-Normalform



1. Schritt:

S → A | aB | aC

B → S | Ba

D → d | dDD

A→ B | C | cAd

C → D | c

S → A | ZaB | ZaC

B → S | BZa

D → Zd | Zd DD

A→ B | C | ZcAZd

C → D | Zc



13


Chomsky-Normalform



2. Schritt: Rechte Seiten haben Lange ≤ 2.

13


Chomsky-Normalform



2. Schritt: Rechte Seiten haben Lange ≤ 2.S → A | ZaB | ZaC

B → S | BZa

D → Zd | Zd DD

A→ B | C | ZcAZd

C → D | Zc


13


Chomsky-Normalform




B → S | BZa

D → Zd | Zd DD

A→ B | C | ZcAZd

C → D | Zc


S → A | ZaB | ZaC

B → S | BZa

D → Zd | Zd E

A→ B | C | ZcF

C → D | Zc


E → DD F → AZd

13


Chomsky-Normalform




B → S | BZa

D → Zd | Zd DD

A→ B | C | ZcAZd

C → D | Zc


S → A | ZaB | ZaC

B → S | BZa

D → Zd | Zd E

A→ B | C | ZcF

C → D | Zc


E → DD F → AZd

13


Chomsky-Normalform




B → S | BZa

D → Zd | Zd DD

A→ B | C | ZcAZd

C → D | Zc


S → A | ZaB | ZaC

B → S | BZa

D → Zd | Zd E

A→ B | C | ZcF

C → D | Zc


E → DD F → AZd

13


Chomsky-Normalform



3. Schritt: Es kommen keine Regeln A→ ε vor.

13


Chomsky-Normalform



3. Schritt: Es kommen keine Regeln A→ ε vor.S → A | ZaB | ZaC

B → S | BZa

D → Zd | Zd E

A→ B | C | ZcF

C → D | Zc


E → DD F → AZd

13


Chomsky-Normalform



3. Schritt: Es kommen keine Regeln A→ ε vor.S → A | ZaB | ZaC

B → S | BZa

D → Zd | Zd E

A→ B | C | ZcF

C → D | Zc


E → DD F → AZd X13


Chomsky-Normalform



Eliminiere Kreis B → S → A→ B.4. Schritt:

13


Chomsky-Normalform




B S

A

C

D Zc

Zd

13


Chomsky-Normalform




B S

A

C

D Zc

Zd

B S

A

C

D Zc

Zd

13


Chomsky-Normalform




B S

A

C

D Zc

Zd

B S

A

C

D Zc

Zd

S

C

D Zc

Zd

13


Chomsky-Normalform




B S

A

C

D Zc

Zd

B S

A

C

D Zc

Zd

S

C

D Zc

Zd

S

C

D Zc

Zd

13


Chomsky-Normalform



S → A | ZaB | ZaC

B → S | BZa

D → Zd | Zd E

A→ B | C | ZcF

C → D | Zc


E → DD F → AZd


13


Chomsky-Normalform



S → A | ZaB | ZaC

B → S | BZa

D → Zd | Zd E

A→ B | C | ZcF

C → D | Zc


E → DD F → AZd


13


Chomsky-Normalform



S → A | ZaB | ZaC

B → S | BZa

D → Zd | Zd E

A→ B | C | ZcF

C → D | Zc


E → DD F → AZd

Eliminiere Kreis B → S → A→ B.4. Schritt:S → ZaS | ZaC | SZa | C | ZcF

D → Zd | Zd E

C → D | Zc


E → DD F → SZd

13


Chomsky-Normalform



S → A | ZaB | ZaC

B → S | BZa

D → Zd | Zd E

A→ B | C | ZcF

C → D | Zc


E → DD F → AZd


D → Zd | Zd E

C → D | Zc


E → DD F → SZd

13


Chomsky-Normalform



S → A | ZaB | ZaC

B → S | BZa

D → Zd | Zd E

A→ B | C | ZcF

C → D | Zc


E → DD F → AZd


D → Zd | Zd E

C → D | Zc


E → DD F → SZd

13


Chomsky-Normalform



Eliminiere verbleibende Kettenregeln: A→ B.4. Schritt:

13


Chomsky-Normalform




(a) Topologische Sortierung: S, C, D, Zc , Zd ,

(b) Keine Kettenregeln mit linker Seite Zd und Zc ,

(c) Ersetze Kettenregeln mit linker Seite D,

(d) Ersetze Kettenregeln mit linker Seite C,

(e) Ersetze Kettenregeln mit linker Seite S.

S → ZaS | ZaC

D → Zd | Zd EC → D | Zc

Za → aZc → cZd → d

E → DDF → SZd

SZa | C | ZcF

13


Chomsky-Normalform




S → ZaS | ZaC | SZa | C | ZcF

D → Zd | Zd E

C → D | Zc


E → DD F → SZd

S → ZaS | ZaC | SZa | d | Zd E | c | ZcF

D → d | Zd E

C → d | Zd E | cZa → a Zc → c Zd → d

E → DD F → SZd

13


Chomsky-Normalform





D → Zd | Zd E

C → D | Zc


E → DD F → SZd


D → d | Zd E


E → DD F → SZd

13


Chomsky-Normalform





D → Zd | Zd E

C → D | Zc


E → DD F → SZd


D → d | Zd E


E → DD F → SZd

13


Der Cocke-Younger-Kasami-Algorithmus





D → d | Zd E


E → DD F → SZd

F E

1 2 3 4i

Vi i

Vi i+1

Vi i+2

Vi i+3

Input a d d d

ZaZd

DCS Zd

DCS Zd

DCS

S F E

F S CD

S

14



Chomsky-Normalform


D → d | Zd E


E → DD F → SZd

15



Chomsky-Normalform


D → d | Zd E


E → DD F → SZd

1 2 3 4i

Vi i

Vi i+1

Vi i+2

Vi i+3

Input

Variable A ∈ V ist in Vi i+j

gdw. A ?→ wi . . .wi+j .

w ist in L(G)⇔ S ∈ V1n.

Input w = w1 . . .wn aus Σ?.1

2

3

15



Chomsky-Normalform


D → d | Zd E


E → DD F → SZd

1 2 3 4i

Vi i

Vi i+1

Vi i+2

Vi i+3

Input


gdw. A ?→ wi . . .wi+j .



2

3

a d d d

15



Chomsky-Normalform


D → d | Zd E


E → DD F → SZd

1 2 3 4i

Vi i

Vi i+1

Vi i+2

Vi i+3

Input


gdw. A ?→ wi . . .wi+j .



2

3

a d d d

ZaZd

DCS Zd

DCS Zd

DCS

15



Chomsky-Normalform

F E


D → d | Zd E


E → DD F → SZd

1 2 3 4i

Vi i

Vi i+1

Vi i+2

Vi i+3

Input


gdw. A ?→ wi . . .wi+j .



2

3

a d d d

ZaZd

DCS Zd

DCS Zd

DCS

S EF

15



Chomsky-Normalform

F E


D → d | Zd E


E → DD F → SZd

1 2 3 4i

Vi i

Vi i+1

Vi i+2

Vi i+3

Input


gdw. A ?→ wi . . .wi+j .



2

3

a d d d

ZaZd

DCS Zd

DCS Zd

DCS

S EF

F

15



Chomsky-Normalform

F E


D → d | Zd E


E → DD F → SZd

1 2 3 4i

Vi i

Vi i+1

Vi i+2

Vi i+3

Input


gdw. A ?→ wi . . .wi+j .



2

3

a d d d

ZaZd

DCS Zd

DCS Zd

DCS

S EF

F

Der allgemeine Fall

Vi j

Vik Vk+1j

15



Chomsky-Normalform

F E


D → d | Zd E


E → DD F → SZd

1 2 3 4i

Vi i

Vi i+1

Vi i+2

Vi i+3

Input


gdw. A ?→ wi . . .wi+j .



2

3

a d d d

ZaZd

DCS Zd

DCS Zd

DCS

S CD

S EF

F

15



Chomsky-Normalform

F E


D → d | Zd E


E → DD F → SZd

1 2 3 4i

Vi i

Vi i+1

Vi i+2

Vi i+3

Input


gdw. A ?→ wi . . .wi+j .



2

3

a d d d

ZaZd

DCS Zd

DCS Zd

DCS

S CD

S EF

F

S

15


Chomsky-Hierarchie



Chomsky-0-Gram.

Chomsky-1-Gram.


u → v , |u| ≤ |v |u ∈ V +, S /∈ vS → ε




(kontextfrei)Typ 2

(regular)Typ 3

(entscheidbar)






16


Chomsky-Hierarchie



Chomsky-0-Gram.

Chomsky-1-Gram.


u → v , |u| ≤ |v |u ∈ V +, S /∈ vS → ε




(kontextfrei)Typ 2

(regular)Typ 3

(entscheidbar)






16


NEA aus Chomsky-3-Grammatik

Gegeben sei die Grammatik G = (Σ, V , S, R) mit Σ = {a, b} und V ={X , Y , Z , S}, welche die Sprache L erzeugt. R sei durch die folgendenAbleitungsregeln gegeben.

S → ε | aS | aX

X → aS | bY

Y → aY | aX | bZ

Z → bZ | aS

Geben Sie einen nichtdeterministischen endlichen Automaten A an, der Lerkennt.

17



Gegeben: G = (Σ, V , S, R) mit Σ = {a, b}, V = {X , Y , Z , S} und R ={S → ε | aS | aX , X → aS | bY , Y → aY | aX | bZ , Z → bZ | aS}.Geben Sie einen nichtdeterministischen endlichen Automaten A an, der Lerkennt.

17



R = {S → ε | aS | aX ,X → aS | bY ,Y → aY | aX | bZ ,Z → bZ | aS}.


V = {X , Y , Z , S}

17



R = {S → ε | aS | aX ,X → aS | bY ,Y → aY | aX | bZ ,Z → bZ | aS}.


S X Y Z

V = {X , Y , Z , S}

17




S X Y Z

V = {X , Y , Z , S} R = {S → ε | aS | aX ,X → aS | bY ,Y → aY | aX | bZ ,Z → bZ | aS}.

17




S X Y Za

a


17




S X Y Za b

a

a


17




S X Y Za b b

a a

a a


17




S X Y Za b b

a a

a

a a

b


17



a, b


S X Y Za b b

a a

a

a a

b

f

b


17


Eindeutige und mehrdeutige Grammatiken

Gegeben sei die Grammatik G = (Σ, V , S, R) mit Σ ={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, -, *} und V = {S, Z}. R :S → S+S | S-S | S*S | Z ,

Z → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0Z | 1Z | 2Z | 3Z | 4Z | 5Z |6Z | 7Z | 8Z | 9Z .

(a) Bestimmen Sie einen Syntaxbaum des Wortes 211-42+10*4.

(b) Ist die Grammatik eindeutig oder mehrdeutig? Begrunden Sie IhreAntwort.

18



G = (Σ, V , S, R) mit Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, -, *}, V = {S, Z}, R :S → S+S | S-S | S*S | Z ,

Z → 0 | 1 | . . . | 9 | 0Z | 1Z | . . . | 9Z .


18




Z → 0 | 1 | . . . | 9 | 0Z | 1Z | . . . | 9Z .


2

1

1

−

42

+

10

∗

4

Z

Z

Z

Z

Z

Z

Z Z

S

S

S

S S

S

S

18



2

1

1

−

42

+

10

∗

4

Z

Z

Z

Z

Z

Z

Z Z

S

S

S

S S

S

S


Z → 0 | 1 | . . . | 9 | 0Z | 1Z | . . . | 9Z .

(b) Ist die Grammatik eindeutig oder mehrdeutig?

18



2

1

1

−

42

+

10

∗

4

Z

Z

Z

Z

Z

Z

Z Z

S

S

S

S S

S

S

2

1

1

−

42

+

10

∗

4Z

Z

Z

Z

Z

Z

Z Z

S

S

S

S SS S


Z → 0 | 1 | . . . | 9 | 0Z | 1Z | . . . | 9Z .


18



2

1

1

−

42

+

10

∗

4

Z

Z

Z

Z

Z

Z

Z Z

S

S

S

S S

S

S

2

1

1

−

42

+

10

∗

4Z

Z

Z

Z

Z

Z

Z Z

S

S

S

S SS SG ist mehrdeutig, da es mehrere Syntaxbaume fur das

gegebene Wort gibt.


Z → 0 | 1 | . . . | 9 | 0Z | 1Z | . . . | 9Z .


18

Documents

7. Übung, Theoretische Grundlagen der Informatik · Konstruktion von Grammatiken Chomsky-0-Grammatiken und DTMs Sprache der korrekten Klammerausdr ucke¨ Der Cocke-Younger-Kasami-Algorithmus