x >0−positiv
x ≥ 0−nichtnegativ (groeßer / gleich)
x <0−negative
x ≤ 0−nichtpositiv (kleiner / gleich)
⊆ - Teilmenge
Σ - eine nichtleere Menge einstelliger Symbole nennen wir Alphabet
ε („Epsilon“) - das „leere Wort“ (kein Teil eines Alphabets)
1. Mengen
eine Menge ist eine Zusammenfassung von bestimmten
Elementen
A = {♦, ♣}
♦ gehört zu A => ♦ ∈ A (ein Element von A)
♠ gehört nicht zu A => ♠ ∉ A (kein Element von A)
{♦, ♣} = {♣, ♦} ebenso
N = {1, 2, 3, 4, . . .} die natürlichen Zahlen,
N 0 = {0, 1, 2, 3, 4, . . .} die natürlichen Zahlen mit 0,
Z = {0, 1, −1, 2, −2, 3, −3, . . .} die ganzen Zahlen
Q = die rationalen Zahlen
R = die realen Zahlen
A ⊂ B – die Menge A ist eine Teilemenge der Menge B
(wenn jedes Element von A auch ein Element von B ist)
E = {1,4}; C = {1,4,9} => E ⊂ C
A=B – die Menge A enthält die gleichen Elemente wie die Menge B,
nur wenn A ⊂ B und B⊂ A
{1,2,3} = {3,2,1}; {a,a,b} = {a.b}
∅ - steht für die leere Menge (kein Element enthält)
o Vereinigungsmenge
eine Menge, die Elemente von A oder B oder beiden enthält
M v =M 1 ∪ M 2 =¿{1,2} ∪ {2,3} = {1,2,3}
X ∈ (A∪ B) nur wenn X ∈ A oder X ∈ B
A∪ B = B∪ A
o Schnittmenge
eine Menge, die aus Elementen von A und B gemeinsam besteht
{1,2} ∩ {2,3} = {2}
disjunkt – Mengen, deren Schnittmenge leer ist – keine
gemeinsamen Elemente
M 1={1 , 2 ,3 }
M 2={1 , 3 , 5}
M S =M 1 ∩ M 2={1, 3 }
o Teilmenge
wenn alle Elemente von A auch in B enthalten, wird
M 4 ={3 , 5 , 9} ist eine Teilmenge von M 2={1 , 3 , 5}⇒ M 4 ⊆ M 2
o Komplement - A
Im Komplement der Menge A liegen alle
Elemente, die in der Obermenge aber nicht
in der Menge A selbst liegen.
Kann auch geschrieben werden als Σ* \ A.
(gesprochen Σ* „ohne“ A)
Bemerkungen von Variablen
o aus der Menge der natürlichen oder ganzen Zahlen meist u oder
m
o aus der Menge der rationalen Zahlen meist p oder q
o aus der Menge der realen Zahlen meist x,y oder z
+¿−die Menge aller realen Zahlen ,die groeßer als0 sind (0 nicht eingeschlossen)¿
R
−¿−die Menge aller realen Zahlen ,die kleiner als0 sind (0 nicht eingeschlossen)¿
R
+¿−die Menge aller realen Zahlen ,die groeßer oder gleichals 0 sind ¿
R0
2. Konkatenation
a · b = ab
das leere Wort
können auch das leere Wort anhängen
verhält sich hierbei als das neutrale Element
w·ε=ε·w=w
Vergleich
Bei der Addition von Zahlen ist die 0 das neutrale Element: n + 0 = 0 + n
=n
Bei der Multiplikation von Zahlen ist die 1 das neutrale Element: x ∗ 1 = 1
∗x=x
Bei der Konkatenation a · a · ε · a entsteht das Wort aaa mit |aaa| = 3
Wort
Eine beliebig lange Kette an Symbolen aus dem Alphabet nennen wir ein
Wort.
Beispiele:
• abba ist ein Wort über dem Alphabet Σ = {a, b}
• 10011101 ist ein Wort über dem Alphabet Σ = {0, 1}
• StartVorwärtsRechtsVorwärtsStopp ist ein Wort über Σ = {Rechts, Links,
Vorwärts, Rückwärts, Start, Stopp, Pause}
Wortlänge
Wir schreiben |w| um Länge des Wortes w abzukürzen.
Um nur ein Symbol (z.B. a) zu zählen verwenden wir ¿ w∨¿ a ¿ .
Abbildung 1: Menge von allen Kombinationen der Elemente von Σ heißt Σ ¿
Sei Σ = {a, b} unser Alphabet
Wir beschreiben die Menge, die alle Möglichkeiten enthält, Elemente aus Σ
zu konkatenieren mit Σ ¿ = {ε, a, b, aa, ab, ba, bb, aba, . . .}.
¿
M über einer beliebigen Menge M enthält nur das leere Wort ε!
Abbildung 2: Teilmengen unserer Obermenge (hier Σ ¿) nennen wir
Sprachen
n
L1={a ∨n∈ N }={0 , 2 , 4 , 6 , 8 , ....}={ x∨x ist gerade }
¿ {x∨es gibt eine Zahl k ∈ N :2 k=x }
n
L2={a ∨n=0 , n ∈ N } = {ε,a,aa,aaa,aaaa, …}
(n stammt aus der Menge der natürlichen Zahlen)
0
a =ε
1
a =a
2
a =a . a=aa
3
a =a . a . a=aaa
n
a =a . a ..... a
¿ n n
L3={uv∨u ∈{a , b } , v ∈ {a}}={a b ∨n∈ N }={ε , ab , aabb , aaabbb , aaaabbbb }
L4 ={a n w∨n∈ N , w=bccb }={bccb , abccb , aabccb ,... }
endet nach einer beliebigen Anzahl von a’s immer mit bccb
L5={w∨¿ w∨¿ 2 , w ∈{a , b }∗}={aa , bb , ab , ba }
Wörter der Länge 2 aus {a, b} *
L6={w∨¿ w∨¿a =2 , w ∈{a , b }∗}={aa , bb , ab , ba }¿
Wörter mit genau 2 a’s und beliebig vielen b’s aus {a, b} *