Vorlesung 4 Flashcards
Was ist eine endliche nicht leere Menge von paarweise verschiedenen Symbolen in der Sprachtheorie?
Diese Menge wird als Alphabet Σ bezeichnet und beinhaltet alle Symbole, die zur Bildung von Strings (Sequenzen von Symbolen) verwendet werden können.
Was versteht man unter der Kleene-Hülle von Σ?
Die Kleene-Hülle von Σ, bezeichnet als Σ*, ist die Menge aller endlichen Sequenzen (Strings) von Symbolen, die aus Σ gebildet werden können, einschließlich der leeren Sequenz ε.
Wie ist die Konkatenation von Strings definiert?
Was definiert die Länge eines Strings?
Die Länge eines Strings s, bezeichnet als |s|, ist die Anzahl der Symbole in s.
Wann ist ein String u ein Präfix eines anderen Strings s?
Was ist ein Suffix eines Strings?
Was ist ein Substring eines gegebenen Strings?
Was ist eine formale Sprache?
Eine formale Sprache L über einem Alphabet Σ ist eine Teilmenge von Σ*, also eine Menge von Strings, die aus Symbolen des Alphabets Σ gebildet werden.
Was ist die Definition eines deterministischen endlichen Automaten (DFA)?
Wie wird ein DFA grafisch repräsentiert?
Grafisch wird ein DFA als Automatengraf dargestellt, der ein gerichteter und gewichteter Graph ist, mit Knotenmenge X sowie Kanten und Kantengewichtungen gemäß der Zustandsübergangsfunktion.
Was ist die Rolle der Zustandsübergangsfunktion δ in einem DFA?
Die Zustandsübergangsfunktion δ ist eine totale Funktion, die für jedes Paar aus Zustand und Eingabesymbol einen Folgezustand definiert, was bedeutet, dass für jedes solche Paar eindeutig ein Folgezustand existiert.
Was versteht man unter der Transitionstruktur eines DFA?
Die Transitionstruktur eines DFA kodiert die zu erkennende Sprache und kann einen Dump-State enthalten, der über alle Transitionen erreicht wird, die nicht zur Sprache gehören. Dies ergänzt die Transitionen zu einer totalen Funktion.
Wann ist ein String Teil der von einem DFA erkannten Sprache?
Ein String ist genau dann ein Element der Sprache, wenn der DFA durch Eingabe dieses Strings in einen markierten Zustand übergeht.
Was ist eine formale Sprache?
Was ist ein Erkenner und wie funktioniert er?
Was ist der Unterschied zwischen einer totalen und einer partiellen Zustandsübergangsfunktion?
Eine totale Zustandsübergangsfunktion definiert für jedes Paar aus Zustand und Eingabesymbol einen Folgezustand innerhalb der Zustandsmenge X. Eine partielle Zustandsübergangsfunktion ist nicht für alle möglichen Paare von Zuständen und Eingabesymbolen definiert.
Was passiert, wenn die Zustandsübergangsfunktion eines Erkenners für ein gegebenes Paar nicht definiert ist?
Was bedeutet es, wenn ein Erkenner eine Sprache “erkennt”?
Was ist die Definition einer regulären Sprache?
Eine formale Sprache ist regulär (Typ 3), wenn sie von einem endlichen Automaten erkannt wird.
Welche mengentheoretischen Operationen sind auf Sprachen anwendbar?
Auf Sprachen sind die Operationen Vereinigung, Schnitt, Differenz, Komplement und symmetrische Differenz anwendbar.
Wie ist die Konkatenation von Sprachen definiert?
Was versteht man unter der Präfix-Hülle einer Sprache?
Was ist die Kleene-Hülle einer Sprache?
Was besagt der Satz über die Abgeschlossenheit regulärer Sprachen?
Die Klasse der regulären Sprachen ist abgeschlossen unter den Operationen Vereinigung, Schnitt, Komplement, Konkatenation sowie der Bildung der Präfix- und Kleene-Hülle.
Wann ist eine Sprache präfix-geschlossen?
Was versteht man unter der Präfix-Hülle einer Sprache?
Gib ein Beispiel für die Präfix-Hülle einer Sprache L
Was bedeutet es, dass eine Menge einer Klasse bezüglich einer Eigenschaft abgeschlossen ist?
Eine Menge ist bezüglich einer Eigenschaft abgeschlossen, wenn die Anwendung dieser Eigenschaft auf Elemente der Menge immer zu einem Ergebnis führt, das ebenfalls in der Menge liegt.
Gib ein Beispiel für die Abgeschlossenheit einer Menge.
Die Menge der natürlichen Zahlen
�
N ist bezüglich der Addition abgeschlossen, denn wenn man zwei natürliche Zahlen addiert (zum Beispiel 1 und 3), ist das Ergebnis (4) immer auch eine natürliche Zahl. Die Menge der ganzen Zahlen
�
Z ist bezüglich der Subtraktion abgeschlossen, denn das Subtrahieren zweier ganzer Zahlen (wie 4 - 3) resultiert immer in einer ganzen Zahl (1).
Was ist die Funktion eines Erzeugers oder Generators in einem ereignisdiskreten System?
Was ist die Definition eines Generators in der Automatentheorie?
Was besagt die Erweiterung der Zustandsübergangsfunktion auf Strings für einen Generator?
Ist das leere Wort ε immer Teil der vom Generator erzeugten Sprache?
Was beschreibt das ungesteuerte Verhalten eines durch einen Generator modellierten DES?
Was bedeutet es, dass L(G) immer präfix-geschlossen ist?
Was definiert das markierende Verhalten eines durch einen Generator modellierten DES?
Was illustriert das Beispiel der Lampe mit Kippschaltern in Bezug auf ungesteuertes und gesteuertes Verhalten?
Was ist die Definition der natürlichen Projektion in der Automatentheorie?
Was bedeutet es, dass die Projektionsfunktion idempotent ist?
Was ist die inverse natürliche Projektion?
Wie funktioniert die inverse natürliche Projektion in Bezug auf einen Generator?
Was illustriert das Beispiel mit der Lampe und den Kippschaltern in Bezug auf natürliche Projektion?
Was ist der Unterschied zwischen einem monolithischen Modell und einem kompositionalen Modell?
Ein monolithisches Modell ist ein unstrukturiertes Modell, das das System als Ganzes ohne Unterscheidung seiner Teile beschreibt. Ein kompositionales Modell hingegen ist ein strukturiertes Modell, das das System durch die Zusammenstellung seiner interagierenden Komponenten darstellt.
Was illustriert das Beispiel einer Flaschenabfüllanlage in Bezug auf kompositionale Modellbildung?
Das Beispiel zeigt, wie ein anfänglich ganzheitlich betrachtetes System – eine Flaschenabfüllanlage – in seine Bestandteile zerlegt wird, wie z.B. verschiedene Füllstationen und eine Verdeckelungsstation, um das Systemverhalten besser zu verstehen und zu modellieren.
Wie werden in der kompositionalen Modellbildung die Komponenten des Systems dargestellt und miteinander verbunden?
In der kompositionalen Modellbildung werden die Komponenten des Systems durch einzelne Automaten repräsentiert, die spezifische Funktionen ausführen. Diese Komponenten werden dann durch definierte Schnittstellen oder Kopplungen miteinander verbunden, um die Interaktionen zwischen den Komponenten innerhalb des Gesamtsystems zu modellieren.
Was ist das Ziel der Zusammenschaltung von Systemmodell und Steuerungsmodell?
Das Ziel der Zusammenschaltung von Systemmodell und Steuerungsmodell ist es, ein Modell des gesteuerten Systems zu erstellen, das zeigt, wie die Steuerung das Verhalten des gegebenen Systems beeinflusst.
Wie wird in der Systemtheorie die Zusammenschaltung von System und Steuerung notiert?
In der Systemtheorie wird die Zusammenschaltung von System (G) und Steuerung (S) als S/G bezeichnet, wobei das resultierende System als “gesteuertes System” betrachtet wird.
Was ist der Unterschied zwischen gemeinsamen und privaten Ereignissen in der Komposition von DES?
Wie werden im Kontext von DES Komponentenmodelle zu einem Gesamtsystem komponiert?
Warum ist eine strukturierte Beschreibung in der Modellbildung von Vorteil?
Eine strukturierte Beschreibung ermöglicht eine klare Trennung der verschiedenen Komponenten eines Systems und ihrer Interaktionen. Dies erleichtert das Verständnis des Gesamtsystems, die Lokalisierung von Fehlern, die Wiederverwendung von Modellen und die Parallelisierung der Entwicklung.
Was ist die Sprache des komponierten Systems bei Anwendung der strengen Synchronisation?
