Document ID: /fineweb-2-swissfilter-quality_10-filterrobots/filtered/03178.jsonl.gz/0

Ordnerverwaltung für Automatentheorie - 4. Semester
Wähle die Ordner aus, zu welchen Du "Automatentheorie - 4. Semester" hinzufügen oder entfernen möchtest
0 Exakte Antworten
80 Text Antworten
0 Multiple Choice Antworten
Karte wurde gelöscht
1/80
Wann heißt eine Grammatik kontextfrei (Typ 2)?
Eine Grammatik heißt kontextfrei, falls die Menge der Ableitungsregeln |P| mit \(P \subseteq N \times (\Sigma \cup N)^*\) endlich ist. Das heißt, dass die Restriktion bezüglich der Position des Nonterminals aufgehoben ist und ein Nonterminal in min. ein Nonterminal und beliebig viele Terminale abgeleitet werden darf.
Welche beiden Normalformen gibt es für Typ 2-Grammatiken?
Chomsky-Normalform und Greibachnormalform
Wie wird die Chomsky-Normalform gebildet?
Jedes Nonterminal wird in zwei Nonterminale oder in ein Terminalsymbol abgeleitet.
Welche Transformationsregeln gibt es zur Vereinfachung von Typ 2-Grammatiken?
1.) Eliminierung der Epsilon-Regeln, indem die Ersetzung eines Nonterminals durch Epsilon in den anderen Regeln vorweggenommen wird. Bsp.: \(A \to aA, A\to aB, B \to \varepsilon \ wird \ zu \ A\to aA, A\to a\)
2.) Eliminierung von Kettenregeln \(A \to B\), die nichts zur Worterzeugung beitragen
3.) Separation von Terminalsymbolen (Einsatz eines "Zwischen-Nonterminals", um kein Nonterminal in einer Terminal- und ein Nonterminalsymbol abzuleiten)
4.) Eliminierung von mehrelementigen Nonterminalketten
Wie wird die Greibach-Normalform gebildet?
Die Produktionen müssen in der Form \(P \subseteq N \times (\Sigma \circ N^*)\) darstellbar sein. Das heißt, dass ein Nonterminal in maximal ein Terminal- und beliebig viele Nonterminalsymbole abgeleitet wird.
Wann heißt eine kontextfreie Grammatik mehrdeutig und wie nennt sie sich, wenn sie in eine eindeutige Grammatik überführt werden kann?
Falls es für min. ein Wort zwei oder mehr Ableitungsbäume gibt.
Wenn sie in eine eindeutige Grammatik überführt werden kann, so heißt sie inhärent mehrdeutig.
Wie funktioniert das Pumping-Lemma für kontextfreie Sprachen?
Es gibt eine natürliche Zahl n, sodass für alle Wörter z aus L mit \(|z| \geq n\) gilt:
z = uvwxy
\(|vx| \geq 1\)
\(|vwx| \leq n\)
\(\forall i \geq 0: uv^i wx^iy \in L\)
Ist die Sprache kontextfrei, ist das Pumping-Lemma erfüllt. Ein erfülltes Pumping-Lemma bedeutet jedoch nicht, dass die Sprache kontextfrei ist.
Was ist ein Kellerautomat?
- "Gedächtnisfunktion" durch unendlich großen Kellerspeicher mit Stack-Funktionalität
- Zeichenablage nach dem LIFO-Prinzip, es wird jeweils nur das oberste Zeichen im Keller gelesen
Wie werden nicht-deterministische Kellerautomaten formal beschrieben?
\(K = (\Sigma, S, \Gamma, \delta, s_0, \perp, F)\) mit \(\Gamma\) als Stack und \(\perp\)als bottom-Symbol.
Wie ist die Zustandsübergangsfunktion eines nicht-deterministischen Kellerautomaten formal beschrieben?
\(d: S \times (\Sigma \cup \{\varepsilon\}) \times \Gamma \to P(S\times\Gamma^*)\)
Man ist in einem Zustand, liest ein Zeichen aus dem Eingabeband oder ein Epsilon sowie anschließend das oberste Zeichen aus dem Stack. Daraus folgt ein Zustand und eine Eingabe in den Stack.
Wann gilt ein Wort durch einen Kellerautomaten als akzeptiert?
Sobald der Kellerautomat einen Endzustand erreicht hat und im Keller nur noch das Bottom-Symbol enthalten ist bzw. der Keller vollständig leer ist.
Das heißt, dass ein Nonterminal oder eine Verbindung aus Nonterminalen und Terminalen in eine Verbindung aus Nonterminal- und Terminalsymbolen abgeleitet werden kann, wobei auf der linken Seite der Ableitung nicht mehr Zeichen als auf der rechten Seite stehen dürfen. Damit ist es möglich, Verkettungen von Terminal- und Nonterminalsymbolen direkt abzuleiten.
Welches Problem stellt das leere Wort Epsilon für Typ 1 Grammatiken dar?
Monotonie-Eigenschaft: Satzform a darf nicht länger sein als die abgeleitete Satzform b.
Das leere Wort verletzt diese Monotonie-Eigenschaft. Als einzige Regel, die diese Eigenschaft verletzt, wird daher die Ableitung des Startsymbols in Epsilon zugelassen (nur das Startsymbol!).
Was sind Typ 0 Grammatiken?
Typ 1-Grammatik ohne Monotonie-Beschränkung
Welche 4 Grundtypen ergeben sich für die Produktionen von Typ 0-Grammatiken?
Reduktionsregel: \(A \to \varepsilon\), Nonterminale werden gelöscht
Terminierungsregel: \(A \to a\)
Expansionsregel: \(A \to AB\), Nonterminal wird in 2 Nonterminale umgewandelt
Doppelsubstitutionsregel: \(AB \to CD\), 2 Nonterminale werden durch 2 andere Nonterminale ersetzt
- Menge der Zeichenreihen einer natürlichen Sprache
- Menge aller von einem endlichen Automaten akzeptierten Zeichenreihen
Alphabete sind abgeschlossen gegenüber Mengenoperationen. Was bedeutet das?
Wenn zwei Alphabete durch eine Operation (z.B. Differenz, Vereinigung, Schnittmenge) verbunden werden, ist das Ergebnis ebenfalls ein Alphabet.
Bsp.: Wenn A und B reguläre Sprachen sind, dann ist auch A vereinigt B eine reguläre Sprache.
Für welchen Fall kann auf folgendem Wege die Anzahl der Elemente einer Vereinigungsmenge berechnet werden?
| Alphabet A vereinigt Alphabet B | = | Alphabet A | + | Alphabet B |
Diese Rechnung kann genutzt werden, wenn die Schnittmenge der beiden Alphabete die leere Menge ist, sie also keine gemeinsamen Elemente haben. Andernfalls würden diese doppelt gezählt werden.
Wie ergibt sich die Anzahl aller möglichen Teilmengen eines Alphabetes?
| Potenzmenge des Alphabetes | = 2 |Alphabet|
Wie wird die Konkatenation • einzelner Zeichen aus dem Alphabet \(\Sigma\) formal beschrieben?
\(\Sigma \times \Sigma \to \Sigma ^*\)
Das leere Wort \(\varepsilon\)ist das Neutralelement. Jedes Wort lässt sich als Verkettung beliebiger Zeichen aus \(\Sigma\) mit dem leeren Wort in beliebiger Häufigkeit darstellen. Z.B. w = ab = \(a\varepsilon\varepsilon b \varepsilon\)
Was meint das Prinzip der Aussonderung?
Definition eines Alphabetes mithilfe einer Eigenschaft \(\xi\)(ai)
Sinnvoll, falls Elemente von \(\Sigma\) eine Teilmenge einer Obermenge A darstellen.
Wofür steht die Potenz eines Zeichens und was ist die 0-te Potenz eines Zeichens?
wiederholte Konkatenation des Zeichens mit sich selbst
0-te Potenz entspricht dem leeren Wort
rekursive Definition:
a1= a0 • a1 = a, a2 = a0 • a1 • a1
Was ist der Kleene-Abschluss?
Die Potenzbildung eines Zeichens lässt sich auch auf Zeichenmengen übertragen. Die Vereinigung aller Potenzen über \(\Sigma\) bildet den Kleene-Abschluss \(\Sigma\)*. \(\Sigma^* \setminus \{\varepsilon\} = \Sigma^+\)
Die Elemente von \(\Sigma\)* unterliegen einer lexikographischen Ordnung. Was bedeutet das?
Sortierung gemäß der Länge der Wörter
Wörter gleicher Länge werden stellenwertig hinsichtlich der enthaltenen Alphabetzeichen sortiert.
Wann ist x echter Präfix eines Wortes w?
x ist Präfix von w und x ist ungleich w und ungleich dem leeren Wort
Wann heißt eine Sprache L \(\subseteq\)\(\Sigma\)* präfixfrei?
Eine Sprache ist präfixfrei, wenn eine Wort x aus Präfix, Infix und Suffix besteht und der Präfix nicht Teil der Sprache ist.
Die deutsche Sprache ist z.B. nicht präfixfrei: "ausmachen" ist ein Wort mit dem Präfix "aus", was ebenfalls ein Wort der deutschen Sprache ist.
Wie wird eine Teilmenge von \(\Sigma\)* bezeichnet?