7. Übung, Theoretische Grundlagen der Informatik · Konstruktion von Grammatiken...

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

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

Chomsky-Hierarchie

(semi-entscheidbar)Typ 0

Menge aller Sprachen

(kontextsensitiv)Typ 1

(kontextfrei)Typ 2

(regular)Typ 3

Chomsky-Hierarchie

alleSprachen

semi-entscheidbareSprachen

entscheidbareSprachen

aus Ubung 3:

(entscheidbar)

(kontextfrei)Typ 2

(regular)Typ 3

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)

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

Chomsky-Hierarchie

Chomsky-0-Gram.

Chomsky-1-Gram.

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

(kontextfrei)Typ 2

(regular)Typ 3

(entscheidbar)

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⇔

mit L(G) = L.

akzeptiert.⇔

Beweis aus der Vorlesung von :

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⇔

mit L(G) = L.

akzeptiert.

Es gibtdeterministische TMM, die L akzeptiert.

⇔ ⇔A B

A B⇔

In der Vorlesung wurde dann bewiesen.⇒ AC

Und es gilt auch allgemein, dass .⇒

Beweis aus der Vorlesung von .A B⇒

mit L(G) = L.

akzeptiert.

⇔ ⇔A B

A B⇔

In der Vorlesung wurde dann bewiesen.⇒ AC

Und es gilt auch allgemein, dass .⇒

Beweis aus der Vorlesung von .A B⇒

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

mit L(G) = L.

akzeptiert.

⇔ ⇔

Beweis aus der Vorlesung von :

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⇔

mit L(G) = L.

akzeptiert.

⇔ ⇔A B

Hier beweisen wir :A ⇒

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

Wir konstruieren eineDTM, die L akzeptiert.

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.

Chomsky-Hierarchie

Chomsky-0-Gram.

Chomsky-1-Gram.

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

(kontextfrei)Typ 2

(regular)Typ 3

(entscheidbar)

Chomsky-Hierarchie

Chomsky-0-Gram.

Chomsky-1-Gram.

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

(kontextfrei)Typ 2

(regular)Typ 3

(entscheidbar)

Chomsky-Hierarchie

Chomsky-0-Gram.

Chomsky-1-Gram.

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

(kontextfrei)Typ 2

(regular)Typ 3

(entscheidbar)

Konstruktion von Grammatiken

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

1. Schritt: Von welchem Typ ist die Sprache?

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

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

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

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

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

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

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

fur i ∈ {0, 1}

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

fur i ∈ {0, 1}

R0X0 → X0R0R0X1 → X1R0R1X0 → X0R1R1X1 → X1R1

L0X0 → L0R0L0X1 → L0R1L1X0 → L1R0L1X1 → L1R1

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

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

fur i ∈ {0, 1}

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

w = 1101 :

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

fur i ∈ {0, 1}

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

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

w = 1101 :

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

fur i ∈ {0, 1}

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

→ 110L1 X0R1X1X1 → 110L1 R0R1X1X1

w = 1101 :

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

fur i ∈ {0, 1}

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

→ 110L1 X0R1X1X1 → 110L1 R0R1X1X1

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

w = 1101 :

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

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 :

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 .

erzeugt.

1. Schritt: Von welchem Typ ist die Grammatik?

erzeugt.

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

erzeugt.

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

erzeugt.

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

S → (S)S | εR = {

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()

L(G) ⊆ L():

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

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.

L(G) ⊇ L():

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

Algorithmus, der w erzeugt:

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

Fuhre S → (S)S aus

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

Fuhre S → (S)S aus

w = ε

Fuhre S → ε aus

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

L() ist nicht regular (Pumping-Lemma)

Regulare Sprachen entsprechen Chomsky-Typ 3

⇒ Chomsky-Typ 2 ist maximal.

Evaluation

Ausfullen und zum Gang reichen

Freitextfelder besonders hilfreich!

5 min Zeit

Chomsky-Hierarchie

Chomsky-0-Gram.

Chomsky-1-Gram.

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

(kontextfrei)Typ 2

(regular)Typ 3

(entscheidbar)

Chomsky-Hierarchie

Chomsky-0-Gram.

Chomsky-1-Gram.

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

(kontextfrei)Typ 2

(regular)Typ 3

(entscheidbar)

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.

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 ∈ Σ

Chomsky-Normalform

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

Chomsky-Normalform

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

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 ∈ Σ

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

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

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

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

Chomsky-Normalform

2. Schritt: Rechte Seiten haben Lange ≤ 2.

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

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

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

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

Chomsky-Normalform

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

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

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:

Chomsky-Normalform

S → A | ZaB | ZaC

B → S | BZa

D → Zd | Zd E

A→ B | C | ZcF

C → D | Zc

E → DD F → AZd

Chomsky-Normalform

S → A | ZaB | ZaC

B → S | BZa

D → Zd | Zd E

A→ B | C | ZcF

C → D | Zc

E → DD F → AZd

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

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

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

Chomsky-Normalform

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

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

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

Chomsky-Normalform

D → Zd | Zd E

C → D | Zc

E → DD F → SZd

D → d | Zd E

E → DD F → SZd

Chomsky-Normalform

D → Zd | Zd E

C → D | Zc

E → DD F → SZd

D → d | Zd E

E → DD F → SZd

Der Cocke-Younger-Kasami-Algorithmus

D → d | Zd E

E → DD F → SZd

1 2 3 4i

Vi i+1

Vi i+2

Vi i+3

Input a d d d

DCS Zd

F S CD

Chomsky-Normalform

D → d | Zd E

E → DD F → SZd

Chomsky-Normalform

D → d | Zd E

E → DD F → SZd

1 2 3 4i

Vi i+1

Vi i+2

Vi i+3

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

Chomsky-Normalform

D → d | Zd E

E → DD F → SZd

1 2 3 4i

Vi i+1

Vi i+2

Vi i+3

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

a d d d

Chomsky-Normalform

D → d | Zd E

E → DD F → SZd

1 2 3 4i

Vi i+1

Vi i+2

Vi i+3

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

a d d d

DCS Zd

Chomsky-Normalform

D → d | Zd E

E → DD F → SZd

1 2 3 4i

Vi i+1

Vi i+2

Vi i+3

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

a d d d

DCS Zd

Chomsky-Normalform

D → d | Zd E

E → DD F → SZd

1 2 3 4i

Vi i+1

Vi i+2

Vi i+3

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

a d d d

DCS Zd

Chomsky-Normalform

D → d | Zd E

E → DD F → SZd

1 2 3 4i

Vi i+1

Vi i+2

Vi i+3

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

a d d d

DCS Zd

Der allgemeine Fall

Vik Vk+1j

Chomsky-Normalform

D → d | Zd E

E → DD F → SZd

1 2 3 4i

Vi i+1

Vi i+2

Vi i+3

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

a d d d

DCS Zd

Chomsky-Normalform

D → d | Zd E

E → DD F → SZd

1 2 3 4i

Vi i+1

Vi i+2

Vi i+3

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

a d d d

DCS Zd

Chomsky-Hierarchie

Chomsky-0-Gram.

Chomsky-1-Gram.

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

(kontextfrei)Typ 2

(regular)Typ 3

(entscheidbar)

Chomsky-Hierarchie

Chomsky-0-Gram.

Chomsky-1-Gram.

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

(kontextfrei)Typ 2

(regular)Typ 3

(entscheidbar)

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.

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.

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

V = {X , Y , Z , S}

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

S X Y Z

V = {X , Y , Z , S}

S X Y Z

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

S X Y Za

S X Y Za b

S X Y Za b b

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.

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 .

(b) Ist die Grammatik eindeutig oder mehrdeutig?

S SS S

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

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

gegebene Wort gibt.

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

7. Übung, Theoretische Grundlagen der Informatik · Konstruktion von Grammatiken...

Documents

WS 2006/2007 Manfred Pinkal - Universität des Saarlandes...• Kontextfreie Grammatiken heißen in der Linguistik auch Konstituentenstruktur-Grammatiken oder Phrasenstruktur-Grammatiken

Englische Fachausdr¨ucke - Springerstatic.springer.com/sgw/documents/631698/application/pdf/Glossar2.pdf · cable Seil, Kabel cantilever beam ... Cartesian coordinates kartesische

1. Formale Sprachen 1.2 Grammatiken formaler Sprachen · Informatik 12 1. Formale Sprachen 1.2 Grammatiken formaler Sprachen 1. Formale Sprachen 1.2 Grammatiken formaler Sprachen

Klaus Volbert, Folien von F. Meyer auf der Heide 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Grammatiken, Definitionen Eine

Stochastische Attribut-Wert-Grammatiken

Topologische Sortierung - infosun.fim.uni-passau.de · 29. Juni 2006 Struktur und Implementierung von Programmiersprachen I 8/13 MultiVisit Grammatiken Bekannt: next_visit_number[Mx]

Englische Fachausdrücke - Springer · central differences zentraler Differenzenquotient central force motion Zentralbewegung centrifugal moment Zentrifugalmoment centripetal acceleration

Pragmatische Aspekte in Grammatiken des Deutschen · Pragmatische Aspekte in Grammatiken des ... kommunikativen Kompetenz sowie durch eine Reihe anderer ... den (vgl. Searle: Sprechakte

015510 LS XL Hansberry A Raisin in the Sun …Walter Lee Younger 29 Mama (Lena Younger) 33 Beneatha Younger 37 Ruth Younger 40 Travis Younger 42 Joseph Asagai 43 George Murchison 44

L Formale Sprachen Grammatiken sind Konzepte, die eine ...home.uni-leipzig.de/heck/automat/webgrammar.pdf · Grammatiken Eine Grammatik besteht im wesentlichen aus einer endlichen

Grundlagen zur Numerik partieller Differenzialgleichungen · 2 Finite-Differenzen-Methode 3 2 Finite-Differenzen-Methode 2.1 Rechteckgitter und finite Ausdrücke Finite-Differenzenverfahren

Benutzung und Benutzbarkeit von Grammatiken

Wiederholung: Klassen und Objekte · Python-Syntax Regul arer Ausdr¨ ucke¨ Lernziele Die Teilnehmer k onnen Beispiele f¨ ur den Nutzen und die Anwendung¨ Regul arer Ausdr¨ ucke

Compiler - UNI Klagenfurt | ITEClaszlo/courses/cb/Compiler.pdf · 2010-06-08 · Laszlo Böszörmenyi Compiler 10 / 22. Mächtigkeit der Grammatiken • Regulär ⊂ kontextfrei ⊂

1608: Computersysteme I · 6 Kurseinheit 1 Boole’sche Ausdr˜ucke, Schaltnetze, Zahlendarstellungen 1.1 Vorbemerkungen 1.1.1 Allgemeines Wir wunschen eine erfolgreiche Besch˜ ˜aftigung

Digitale Bildverarbeitung - DHBW Stuttgartsgehrig/lectures/bv_skript.pdf · •automat. Auswertung medizinischer Bilder (Tumorerkennung) •Wettervorhersage •Kriminalistik (Fingerabdr¨ucke)

Italienische Grammatiken des 16. Jahrhunderts (I) Die Hauptpositionen der Questione della lingua

Informatik 12 1. Formale Sprachen 1.2 Grammatiken formaler Sprachen 1. Formale Sprachen 1.2 Grammatiken formaler Sprachen Die Regeln zur Bildung korrekter

EnglischeFachausdr¨ucke - Springer978-3-642-16828-4/1.pdf · momentum Impuls multi-stepmethod Mehrschrittverfahren naturalfrequency Eigenfrequenz. ... –-modul,instantaner 329 –-modul,momentaner

Lokale Grammatiken für Appositionen im rechten Kontext von