Übungsblatt 1 & 2

Aufgabe 1: Begriffe und Definitionen

1. Definieren Sie die Begriffe Alphabet, Wort und Sprache! (1-2)

Alphabet: eine Menge von Zeichen (Symbolen, Buchstaben)
Wort: endliche Zeichenkette von Symbolen eines Alphabets

w = a1, a2, a3, …, ak (ein Wort der Länge k)

leeres Wort = ε (Länge 0)

$A^{*}$ = Menge aller Worte inklusive ε
$A^{+}$ = Menge aller nicht-leeren Worte
Sprache: Teilmenge von $A^{*}$

2. Nennen und erläutern Sie die Bestandteile einer Grammatik! (1-8)

Eine Sprache L(G) wird definiert durch eine Grammatik G = (N, T, P, S), wobei gilt:

N sind die nichtterminalen Symbole (Variable),
T sind die terminalen Symbole (Terminale), wobei T $\cap$ N = ∅,
P sind die Produktionsregeln der Form α $\rightarrow$ β, wobei

α ∈ $(N\cup T)^{+}$ , β ∈ (N $\cup$ T)*,

S ∈ N ist das Startsymbol, ein spezielles nichtterminales Symbol

3. Wie stehen die Begriffe Grammatik und Sprache miteinander in Beziehung? (1-7)

Eine Grammatik ist ein System zur Ableitung von Worten einer Sprache.

4. Was beschreibt die Chomsky-Hierarchie? (1-15ff)

Die Chomsky-Hierarchie beschreibt eine Hierarchie von vier Grammatiktypen zur Erzeugung von formalen Sprachen:

Typ 0-Sprache (rekursiv aufzählbar): keine Einschränkungen bezüglich der Produktion
Typ 1-Sprache (kontextsensitiv): auf der linken Seite vom Produktionspfeil sind Terminal- und Nichtterminalsymbole erlaubt

α1Aα2 $\rightarrow$ α1βα2 , wobei A ∈ N, α1, α2 ∈ ( N $\cup$ T )*, ß ∈ $(N\cup T)^{+}$

Typ 2-Sprache (kontextfrei): auf der linken Seite vom Produktionspfeil ist nur ein Nichtterminalsymbol erlaubt

A $\rightarrow$ 􀃆 β, wobei A ∈ N, β ∈ $(N\cup T)^{+}$

Typ 3-Sprache (regulär): analog zu Typ2, jedoch dürfen Worte entweder nur von links nach rechts

(rechtsregulär) oder nur von rechts nach links (linksregulär) erzeugt werden

A $\rightarrow$ aB oder A $\rightarrow$ a, wobei A, B ∈ N und a ∈ T

5. Worin unterscheiden sich kontextfreie und kontextsensitive Grammatiken ?

Der Unterschied zwischen diesen beiden Grammatiken besteht darin, dass bei einer kontextfreien Grammatik auf der linken Seite vom Produktionspfeil nur ein nichtterminales Symbol erlaubt ist, während bei einer kontextsensitiven Grammatik ein oder mehrere nichtterminale und terminale Symbole erlaubt sind.

Aufgabe 2: Grammatiken

Gegeben sei folgende Grammatik mit dem Startsymbol S:

N = {S, A, B}
T = {a, b, c}
P = {S $\rightarrow$ abc, S $\rightarrow$ aAbc, Ab $\rightarrow$ bA, Ac $\rightarrow$ Bbcc, bB $\rightarrow$ Bb, aB $\rightarrow$ aaA, aB $\rightarrow$ aa}

1. Welchen Typ hat die Grammatik bzgl. der Chomsky-Hierarchie ?

Die Grammatik ist kontextsensitiv, da auf der linken Seite der Produktionsregeln sowohl Zeichen aus N und aus T vorkommen.

2. Zeigen Sie, dass die von dieser Grammatik erzeugte Sprache gegeben ist durch die Sprache

L(G) = { $a^{n}b^{n}c^{n}$ | n>0 } = {abc, aabbcc, aaabbbccc, …}!

S $\rightarrow$ abc
S $\rightarrow$ aAbc $\rightarrow$ abAc $\rightarrow$ abBbcc $\rightarrow$ aBbbcc $\rightarrow$ aabbcc $\rightarrow$ aaAbbcc

) analoger Aufbau, Rekursion)

Aufgabe 3: Grammatiken

Gegeben sei der folgende Auszug aus einer Grammatik:

\rightarrow

\rightarrow

( <Expression> )

\rightarrow

\rightarrow

\rightarrow

\rightarrow

\rightarrow

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

1. Wie lautet die Definition der entsprechenden Grammatik, welchen Typ hat sie ?

G = (N, T, P, S)

N = {<Expression>, <number>}

T = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +. -, *, /, (, )}

S = <Expression>

P = siehe oben

Es handelt sich um eine Typ 2-Grammatik (kontextfrei), da auf der linken Seite der Produktionsreageln nur ein Nicht-Terminalsymbol vorhanden ist.

== 2. Prüfen Sie, ob folgende Worte Elemente der durch die Grammatik beschriebenen Sprache sind: (1+2)*3, (1-2)+(4-13), -1, (-1)*(+1), 3-1++2 ==

(1+2)*3:

S

\rightarrow

( <Expression> ) * <Expression>

( <Expression> + <Expression>) * <Expression>

( <number> + <number> ) * <number>

(1+2)*3

(1-2)+(4-13):

keine zweistelligen Zahlen ableitbar

-1

keine negativen Zahlen ableitbar

(-1)*(+1)

keine negativen Zahlen ableitbar,

+-Operator ist in dieser Grammatik ein binärer Operator

3-1++2

kein doppeltes-Pluszeichen ableitbar