Automaten Flashcards
Was sind die Eigenschaften einer formalen Sprache?
Formale Sprachen bestehen aus einem Alphabet Sigma, welches die Menge aller zulässigen distinkten Zeichen enthält.
Beliebig lange, endliche Folgen von solchen Zeichen werden als Wörter bezeichnet. Nicht jedes Wort ist dabei zulässig. Weiterhin wird zwischen terminalen und nichtterminalen Zeichen unterschieden.
Formale Sprachen werden durch Grammatiken erzeugt, die sich verschiedenen Typen zuordnen lassen.
Formale Sprachen sind mathematisch exakt analysierbar.
Was sind die Eigenschaften eines Deterministischen Endlichen Automaten (DEA)?
Die Beschreibung eines DEA erfolgt über das Quintupel
A = { Σ, S, δ, s0, F }
Die Menge der Zustände wird über
S = { s0, …, sn }
notiert.
Σ ist das Alphabet des Automaten, S die Menge der Zustände, s0 der Anfangszustand und F der Endzustand. δ steht für die Zustandsübergangsfunktion-
Ein DEA heißt deterministisch, weil alle Folgezustände eindeutig sind. Eingabewörter werden dabei zeichenweise verarbeitet, was dazu führt dass ein Wort einen DEA komplett durchlaufen muss, damit eindeutig gesagt werden kann, ob es valide ist. Stimmt das letzte Zeichen des Wortes allerdings nicht mit F überein, ist das Wort nie valide.
Welche Probleme können durch einen DEA gelöst werden und welche nicht?
Lösbar:
- Wortproblem (gehört ein Wort zu einer Sprache oder nicht?)
- Leerheitsproblem (gibt es überhaupt Wörter, die der Grammatik genügen/ist die Sprache leer?)
- Endlichkeitsproblem (hat die Sprache endlich viele Wörter?)
Nicht lösbar:
- Äquivalenzproblem (Beschreiben zwei Formalismen dieselbe Sprache bzw. Funktion?)
Was ist eine Typ-2-Sprache und wo wird sie angewendet?
Eine Typ-2-Sprache ist in der Chomsky-Hierarchie eine kontextfreie Sprache, die nicht leer sein darf und auf deren linker Gleichungsseite genau ein nichtterminales Symbol stehen darf:
A –> aBa
Anwendungsgebiete:
- Compilerbau
- Definition der Syntax höherer Programmiersprachen
- Hilfsmittel zur Beschreibung syntaktischer Strukturen
- SADT (Structured Analysis and Design Technique)
Darstellungsformen:
- Extended Backus-Naur-Form (EBNF)
- Syntaxdiagramme
Was sind die Eigenschaften eines Kellerautomaten?
- Endlicher Automat
- wird verwendet um Sprachen der Form L = { a^n b^n | n > 0 } zu überprüfen
- Lesekopf
- Unendlicher Kellerspeicher
- LIFO-Prinzip des Kellers, wobei immer nur das oberste Zeichen verglichen wird
- Übergangsfunktion besteht aus Eingabewert (Zustand, Eingabe, Kellerzeichen) und Funktionswert (Folgezustand, neues Kellerzeichen)
Wie funktioniert ein Kellerautomat?
- Anfangssymbol wird in den Kellerspeicher geschrieben
- Erstes Zeichen wird eingelesen und mit dem Kellersymbol verglichen
- Stimmen die Symbole überein, wird wieder in den Anfangszustand gewechselt (solange bis das Zeichen wechselt)
- Ist der Keller am Ende des Wortes leer, handelt es sich um ein gültiges Wort
Wie funktioniert eine Turing-Maschine?
Der Speicher besteht aus einem unendlich langen Band mit Lese-/Schreibkopf
Beliebig viele (aber endliche!) Schritte (je nachdem wie viele Zeichen verarbeitet werden müssen) werden folgendermaßen ausgeführt:
- Zeichen lesen
- Neues Zeichen schreiben
- Kopf nach links, nach rechts oder nicht bewegen (i.A. vom eingelesenen Zeichen)
- Zustand wechseln
Dabei übernimmt eine Kontrolleinheit die Zustandswechsel zwischen endlich vielen Zuständen
Analog zum Kellerautomaten gibt es einen Start- und einen Endzustand
Was ist ein Multiagentensystem?
Ein System aus mehreren, gleichartigen oder unterschiedlich spezialisierten Einheiten (Agenten), die kollektiv ein Problem lösen (bspw. Multiagentensystem in der Biologie: Ameisenstaat)
Woraus besteht eine Multiagentensimulation?
- Anwendung des Multiagentensystems in einer Simulation
- Komponenten des untersuchenden Systems werden als Agenten betrachtet, deren Verhalten ist jeweils einzeln spezifiziert
- Dient als Nachweis dynamischer Wechselwirkung zwischen Agenten und emergenter Phänomene (Entstehen einer Struktur aus Chaos / Unordnung)
