Einführung Flashcards
Was ist ein Alphabet?
Endliche, nicht-leere Menge an Objekten, genannt Symbole
Was ist ein Argument?
Eine Eingabe einer Funktion
Was ist eine binäre Relation?
Eine Relation dessen Urbildmenge eine Menge aus Paaren ist
Was ist eine Bool’sche Operation?
Eine Operation auf bool’schen Werten
Was ist ein Kartesisches Produkt?
Eine Operation auf Mengen die eine Menge aus allen Tupeln der Elemente der Mengen erzeugt
Was ist ein Komplement?
Eine Operation auf eine Menge die eine Menge aus allen nicht vorhandenen Elementen erzeugt
Was ist eine Konkatenation?
Eine Operation die Wörter aneinanderreiht
Was ist eine Konjunktion?
Bool’sche UND Operation
Was ist ein zusammenhängender Graph?
Ein Graph mit Pfaden die alle Knoten paarweise verbinden
Was ist ein Zyklus?
Ein Pfad der im selben Knoten startet und endet
Was ist ein gerichteter Graph?
Eine Sammlung von Punkten und Pfeilen die Paare von Punkten verbinden
Was ist eine Disjunktion?
Bool’sche ODER Operation
Was ist eine Urbildmenge?
Die Menge aller möglichen Eingaben einer Funktion
Auch: Quellmenge
Was ist eine Kante?
Eine Linie in einem Graphen
Was ist ein Element?
Ein Objekt in einer Menge
Was ist eine Leere Menge?
Eine Menge ohne Elemente
Was ist ein Leeres Wort?
Ein Wort mit der Länge null
Was ist eine Äquivalenzrelation?
Eine binäre Relation die reflexiv, symmetrisch und transitiv ist
Was ist eine Funktion?
Eine Operation die Eingaben in Ausgaben übersetzt
Was ist ein Graph?
Eine Sammlung von Punkten und Linien die Paare von Punkten verbinden
Was ist ein Schnitt?
Eine Operation auf Mengen die eine Menge aus allen gemeinsamen Elementen erzeugt
Was ist ein k-Tupel?
Eine Liste von k Objekten
Was ist eine Sprache?
Eine Menge an Wörtern
Was ist ein Element?
Ein Objekt in einer Menge (Duplikat)
Was ist ein Knoten?
Ein Punkt in einem Graphen
Was ist ein geoordnetes Paar?
Eine Liste aus zwei Elementen
Was ist ein Pfad?
Eine Sequenz von Knoten in einem Graphen die durch Kanten verbunden sind
Was ist ein Prädikat?
Eine Funktion mit dem Bildbereich {TRUE, FALSE}
Was ist eine Eigenschaft?
Ein Prädikat
Was ist ein Bildbereich?
Die Menge aus der die Ausgaben einer Funktion gewählt werden
Was ist eine Relation?
Ein Prädikat, typischerweise wenn die Urbildmenge eine Menge an k-Tupeln ist
Was ist eine Sequenz?
Eine Liste von Objekten
Was ist eine Menge?
Eine Gruppe von Objekten
Was ist ein einfacher Pfad?
Ein Pfad ohne Wiederholung
Was ist eine Einelementige Menge?
Menge mit einem Element
Was ist ein Wort?
Eine endliche Liste an Symbolen aus einem Alphabet
Was ist ein Symbol?
Ein Element eines Alphabets
Was ist ein Baum?
Ein zusammenhängender Graph ohne einfache Zyklen
Was ist eine Vereinigung?
Eine Operation auf Mengen die alle Elemente in eine Menge kombiniert
Was ist ein Ungeordnetes Paar?
Eine Menge mit zwei Elementen
Was ist eine Ecke?
Ein Punkt in einem Graphen
Wie ist ein Deterministischer endlicher Automat definiert?
Wie ist eine erkannte (akzeptierte) Sprache definiert?
Was bedeutet eine erfolgreiche Rechnung?
Im Kontext der Endlichen Automaten bedeutet eine erfolgreiche Rechnung das Akzeptieren von Wörtern.
Wie ist eine reguläre Sprache definiert?
Eine Sprache heißt reguläre Sprache (auch reguläre Menge), wenn sie von einem endlichen Automaten erkannt wird.
Die Familie aller regulären Sprachen wird mit REG bezeichnet.
Sei M ein DFA, was ist L(M)?
Eine Menge von Wörtern (die von M erkannte Sprache) und
außerdem ist L(M) ∈ REG
REG enthält also Mengen!
Wann ist ein DFA vollständig?
jede Eingabe kann gelesen werden
Wann ist ein DFA initial zusammenhängend?
jeder Zustand ist erreichbar
Wie Zeigt man, dass ein Automat zu einer Sprache gehört und andersherum?
Was ist damit gemeint?
Wie viele Zweien sind in dem Wort?
3
Wie werden Sequenzen notiert?
Mit runden Klammern. Zum Beispiel:
(7, 21, 57)
Ist die Reihenfolge bei Sequenzen wichtig?
Ja, anders als bei Mengen
Sind Wiederholungen bei Sequenzen von Interesse?
Ja, anders als bei Mengen
Wie werden endliche Sequenzen genannt?
Tupel
Wie wird die Menge der möglichen Eingaben für eine Funktion genannt?
Urbildmenge/Domain
Wie wird die Menge der möglichen Ausgaben für eine Funktion genannt?
Bildmenge/range
Wie wird eine Funktion genannt, die alle Elemente der range/Bildmenge nutzt?
the function is onto the range
Wie werden die a’s genannt?
Argumente
Wie wird eine Funktion mit k-Argumenten genannt?
k-ary-function
Was ist eine Relation?
Eine Prädiktion, dessen Urbildmenge aus einer Menge von k-Tupel besteht
Was ist der Grad eines Knotens?
Die Anzahl dessen Kanten?
Wann ist eine Graph ein Subgraph?
Wenn er eine Teilmenge der Knoten von einem anderen Graphen hat und dabei die Kanten beibehält
Was ist ein simpler Pfad?
Ein Pfad, der keine Knoten wiederholt
Was ist ein simpler Zyklus?
Ein Zyklus, der mind. drei Knoten hat und keine wiederholt
Wann ist ein Graph ein Baum?
Wenn er verbunden ist und keine simplen Zyklen hat
Was ist die Shortlex/String order?
identical to lexicographic order, except that shorter strings precede longer strings.
Wann ist ein Graph k-regulär?
We define a graph to be k-regular if every node in the graph has degree k.
