Blatt 4 PDF

Preview

Summary

Download Blatt 4 PDF

Description

Theoretische Informatik Sommersemester 2019

TH Köln – Campus Gummersbach Prof. Dr. Hans L. Stahl / Raphaela Butz, M. Sc.

Übungen zur Vorlesung Viertes Aufgabenblatt

Grammatiken Aufgabe 4.1 Gegeben sei die Grammatik G󰇛󰇝A, B, C, S󰇞, 󰇝a, e, i, k, n, o, p, r, z󰇞, P, S󰇜 mit P:

S → ziA | zaC | zoB B → nk | o

A → rC | eC | C C → p | pp

Geben Sie in einem Syntaxbaum den Weg an, der durch das Wort „zirp“ beschrieben wird.

Aufgabe 4.2 Gegeben sei das Alphabet Σ  󰇝 a, b, c 󰇞. Betrachten Sie die Grammatik G  󰇛V, Σ, P, S󰇜 mit V󰇝S, X, Y, Z󰇞 und P ⊆ 󰇛 󰇛Σ∪V󰇜*V󰇛Σ∪V󰇜*  󰇛󰇛Σ∪V󰇜\󰇝S󰇞󰇜 󰇜 ∪ 󰇝 󰇛S,ε󰇜: S → aX | bbY | cZc. aX → aaX | abc, bY → aX | bc. Zc → cZc | ccc a󰇜 Wie lautet L󰇛G󰇜? b󰇜 Für welches Wort w ∈ 󰇝 ε, aa, abc, bbc, ccc, cccc, ccccc 󰇞 gilt: w ∈ L󰇛G󰇜 ?

Aufgabe 4.3 Gegeben sei das Alphabet Σ  󰇝 a, b 󰇞. Betrachten Sie die Grammatik G  󰇛V, Σ, P, S󰇜 mit V󰇝S󰇞 und: a󰇜 P ⊆ V  󰇛Σ ∪ V󰇜* S → aSb | ε . Wie lautet L󰇛G1󰇜? L󰇛G1󰇜  󰇝ε, ab, aabb, aaabbb, aaaabbbb, aaaaabbbbb, …󰇞  󰇝anbn | n ∈ ℕ󰇞 b󰇜 P ⊆ V  󰇛Σ ∪ V󰇜* S → aSa | bSb | ε . Wie lautet L󰇛G2󰇜?

Hinweis: L󰇛G 2󰇜 beschreibt eine Teilmenge der Palindrome, also von Zeichenketten welche rückwärts sowie vorwärts das gleiche ergeben.

Aufgabe 4.4 Geben Sie eine möglichst einfache Grammatik an, welche die Sprache L  󰇝hu, huu, huuu, …󰇞 über dem Alphabet Σ  󰇝h,u󰇞 definiert. Jedes Wort der Sprache besteht also aus einem h gefolgt von einem u, ansonsten beliebig vielen u’s.

1

Theoretische Informatik Sommersemester 2019

TH Köln – Campus Gummersbach Prof. Dr. Hans L. Stahl / Raphaela Butz, M. Sc.

Aufgabe 4.5 a󰇜 Eine Grammatik ist formal als Quadrupel definiert. Geben Sie diese Definition mathematisch exakt und mit den entsprechenden Schlüsselbegriffen an. b󰇜 Wie werden die Grammatiken vom Typ1, Typ2 und Typ3 noch bezeichnet und durch welche Charakteristiken unterscheiden sich diese?

Aufgabe 4.6 Geben Sie eine reguläre Grammatik für die folgende Sprache 󰇝[email protected] | x ∈ 󰇝a,b,c󰇞, y ∈ 󰇝a,b,c󰇞 und v ∈ 󰇝de,com󰇞 über dem Alphabet Σ  󰇝a,b,c,d,e,m,o,@,.󰇞 an.

Aufgabe 4.7 Gegeben sei das Alphabet Σ  󰇝0, 1󰇞. Betrachten Sie die Grammatik G  󰇛V, Σ, P, S󰇜 mit V  󰇝 S, T󰇞, S  Startsymbol und P ⊆ V  󰇛Σ ∪ V󰇜*: S → 0 | T00, T → T0 | T1 | ε. a󰇜 Wieso ist diese Grammatik nur fast linksregulär? b󰇜 Ändern Sie G in eine linksreguläre Grammatik G‘ mit L󰇛G󰇜  L󰇛G‘󰇜 c󰇜 Geben Sie eine rechtsreguläre Grammatik G‘‘ an mit L󰇛G󰇜  L󰇛G‘‘󰇜

2...