Theoretische Informatik
Theoretische Informatik 5. Semester Fachhochschule.
Theoretische Informatik 5. Semester Fachhochschule.
Kartei Details
| Karten | 17 |
|---|---|
| Sprache | Deutsch |
| Kategorie | Informatik |
| Stufe | Universität |
| Erstellt / Aktualisiert | 08.01.2014 / 08.01.2014 |
| Weblink |
https://card2brain.ch/box/theoretische_informatik1
|
| Einbinden |
<iframe src="https://card2brain.ch/box/theoretische_informatik1/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
Definition eines Alphabets:
Definition: Ein Alphabet ist eine endliche, nichtleere Menge von Zeichen. Ein geordnetes Alphabet ist ein Alphabet, dessen Zeichen gemäß einer Ordungsrelation angeordnet sind.
Beispiel: Die folgenden Mengen sind Beispiele für Alphabete:
A0 = {a, b}
A1 = {a, ..., z} (Kleinbuchstaben)
A2 = { ·, –, } (Morsezeichen: kurz, lang, Pause)
A3 = { t, c, a, g } (DNA-Basen)
A4 = { a, ..., z, ä, ö, ü, ß, A, ..., Z, Ä, Ö, Ü, , ., ,, !, ?, : } (Buchstaben, Leerzeichen, Satzzeichen)
A1 ist ein geordnetes Alphabet, gemäß der alphabetischen Ordnung der Buchstaben.
was wird mit A* bezeichnet?
Definition: Die Menge aller Wörter über einem Alphabet A wird mit A* bezeichnet:
A* = { x | x = x0 ... xn-1 , xi A, n 0 }.
was wird mit A+ bezeichnet ?
Die Menge aller nichtleeren Wörter über A wird mit A+ bezeichnet:
A+ = { x | x = x0 ... xn-1 , xi A, n } = A* \ {ε}.
was wird mit A? bezeichnet?
Die Menge aller Wörter der Länge höchstens 1 über A wird mit A? bezeichnet:
A? = { x | x = x0 ... xn-1 , xi A, n {0, 1} }
was wird mit A1 bezeichnet?
Die Menge aller Wörter der Länge 1 über A wird mit A1 bezeichnet:
A1 = { x | x = x0 ... xn-1 , xi A, n {1} } = A? \ {ε}.
Definition von Sprache:
Sei A ein Alphabet. Eine Teilmenge L A* heißt Sprache über A. Eine Sprache ist also eine beliebige Menge von gewissen Wörtern über A.
Sprachen werden hier nur unter formalen Gesichtspunkten betrachtet; es wird keinerlei Bedeutung mit den Wörtern der Sprache verbunden.
Es sei A = {a, b, c}. Dann sind beispielsweise folgende Mengen Sprachen über A:
L1 =
L2 =
L3 =
L4 =
L5 =
L6 =
L1 = {aa, ab, aabcaacb}
L2 = {a, b}
L3 = {ε}
L4 =
L5 = { anbncn | n 0 }
L6 = A*
Die Sprachen L1, L2, L3 und L4 enthalten endlich viele Wörter, die Sprachen L5 und L6 unendlich viele. Zu beachten ist der Unterschied zwischen L3 und L4. Die Sprache L3 enthält ein Wort, nämlich das leere Wort ε, die Sprache L4 enthält kein Wort. Die Sprache L2 enthält nur Wörter der Länge 1; eine solche Sprache bezeichnen wir als Elementarsprache.
Eine Teilmenge von A1 nennen wir eine ______?
Elementarsprache.
Sei A = {a, b, c}. Dann gibt es acht Elementarsprachen über A, nämlich:
, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}
Sei A ein Alphabet und sei L eine Sprache über A. Das Komplement L der Sprache L besteht aus allen Wörtern über A, die nicht in L liegen, d.h.
L = A* \ L = { w A* | w L }
Seien X und Y Sprachen, d.h. Mengen von Wörtern über A. Die Verkettung (oder das Produkt) der Sprachen X und Y ist die Sprache:
XY = { xy | x X, y Y }.
Seien X = {a, le}, Y = {ber, bend, der}. Dann ist XY = ______
{aber, abend, ader, leber, lebend, leder}
Für alle Sprachen X gilt:
{ε}X = X{ε} = X,
aber
X = X = .
Die i-te Potenz einer Sprache X ist definiert durch:
X 0 = {ε},
X i = X i-1X für alle i .
Der Abschluss X* einer Sprache X ist definiert durch:
X* = i IN0 X i = {ε} X X 2 ...
Bemerkung: Fasst man das Alphabet A als Menge aller Wörter der Länge 1 auf und bildet den Abschluss A*, so erhält man die Menge aller Wörter über A, also A* aus der ursprünglichen Definition.
Ein nichtdeterministischer endlicher Automat ist ein 5-Tupel
N = (Z, A, d, q, F).
Hierbei ist:
Z A d q Z F Z
Z eine endliche, nichtleere Menge von Zuständen, A das Eingabealphabet, d die Übergangsrelation d ZAZ, q Z der Startzustand, F Z die Menge der Endzustände.
