Lernkarten

Karten 80 Karten
Lernende 4 Lernende
Sprache Deutsch
Stufe Universität
Erstellt / Aktualisiert 29.03.2016 / 02.10.2018
Lizenzierung Keine Angabe
Weblink
Einbinden
0 Exakte Antworten 80 Text Antworten 0 Multiple Choice Antworten

1/80

Fenster schliessen

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.

Fenster schliessen

Welche beiden Normalformen gibt es für Typ 2-Grammatiken?

Chomsky-Normalform und Greibachnormalform

Fenster schliessen

Wie wird die Chomsky-Normalform gebildet?

Jedes Nonterminal wird in zwei Nonterminale oder in ein Terminalsymbol abgeleitet.

Fenster schliessen

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

Fenster schliessen

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.

Fenster schliessen

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.

Fenster schliessen

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.

Fenster schliessen

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

Fenster schliessen

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.

Fenster schliessen

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.

Fenster schliessen

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.

Fenster schliessen

Wann heißt eine Grammatik kontextsensitiv?

\(P \subseteq ((\Sigma \cup N)^*\setminus \Sigma^*)\times(\Sigma\cup N)^*\)

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.

Fenster schliessen

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!).

Fenster schliessen

Was sind Typ 0 Grammatiken?

Typ 1-Grammatik ohne Monotonie-Beschränkung

 

Fenster schliessen

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

 

Fenster schliessen

Welche 4 Typen von Grammatiken gibt es?

Typ 3: Reguläre Sprachen

Typ 2: Kontextfreie Sprachen, umfasst Typ 3

Typ 1: Kontextsensitive Sprachen. umfasst Typ 2

Typ 0: Phrasenstruktursprachen, umfasst Typ 1

 

 

Fenster schliessen

Was ist ein Alphabet?

endliche, abgeschlossene Menge vereinbarter, eindeutiger, unterscheidbarer, unzerlegbarer Einzelzeichen / Symbole

Fenster schliessen

Was ist eine Zeichenreihe?

Reihe aus Elementen eines Alphabets

Fenster schliessen

Was ist eine Sprache?

Menge von Zeichenreihen aus Eingabezeichen

- Menge der Zeichenreihen einer natürlichen Sprache

- Menge aller von einem endlichen Automaten akzeptierten Zeichenreihen

Fenster schliessen

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.

Fenster schliessen

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.

Fenster schliessen

Wie ergibt sich die Anzahl aller möglichen Teilmengen eines Alphabetes?

| Potenzmenge des Alphabetes | = 2 |Alphabet|

Fenster schliessen

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\)

Fenster schliessen

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.

Fenster schliessen

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

Fenster schliessen

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^+\)

 

Fenster schliessen

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.

Fenster schliessen

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

Fenster schliessen

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.

Fenster schliessen

Wie wird eine Teilmenge von \(\Sigma\)* bezeichnet?

als formale Sprache L über \(\Sigma\)