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

Fenster schliessen

Wie erfolgt die Konkatenation von Sprachen?

über die Konkatenation der Elemente (jedes Element einer Sprache mit alle Elementen der anderen Sprache)

Fenster schliessen

Auf welche Weise lassen sich formale Sprachen definieren?

akzeptierende Konzepte --> endliche Automaten

beschreibende Konzepte --> reguläre Ausdrücke

erzeugende Konzepte --> Grammatiken

Fenster schliessen

Welche Automatentypen wurden in der Vorlesung behandelt?

Transduktoren: Moore Maschine, Mealy Maschine

Akzeptoren: nichtdeterministischer endlicher Automat NEA, deterministischer endlicher Automat DEA, \(\varepsilon\) - endlicher Automat

Fenster schliessen

Wodurch wird ein DEA beschrieben?

Quintupel: (\(\Sigma\), S, \(\delta\), s0, F) --> (Eingabealphabet, Zustandsmenge, Zustandsübergangsfunktion, Anfangszustand, Endzustandsmenge)

 

Fenster schliessen

Wie wird die Zustandübergangsfunktion \(\delta\) für einen DEA ausgedrückt?

\(\delta\) : S x \(\Sigma\) --> S

Fenster schliessen

Wann gilt eine Sprache L als eine vom Automaten akzeptierte Sprache?

Wenn die Elemente \(w_i \in L \subseteq \Sigma^*\) vom Startzustand s0 zu einem Endzustand führen.

\(\delta^* (s_0, w) = s_i \in F\)

Fenster schliessen

Was gilt allgemein für akzeptierte Sprachen?

\(L(A) = \{w\in \Sigma^* | (s_0, w) \vdash ^* (s_i\in F, \varepsilon)\}\)

In Worten: Das Wort w ist Element der transitiv reflexiven Hülle und es gilt: Vom Startzustand kommt man über die komplette Abarbeitung des Wortes in einen Endzustand.

Fenster schliessen

Wann ist ein DEA vollständig und wie wird er formal abgebildet?

Der Automat ist vollständig, wenn alle möglichen Eingabezeichen von einem Zustand in einen Zustand führen (es kann auch der gleiche sein). Für alle nicht definierten Übergänge wird ein zusätzlicher Zustand eingebunden (sozusagen das Abstellgleis).

Atotal = (\(\Sigma, S \cup \{s_{tot}, \delta_{total}, s_0, F\}, s_{tot} \notin S\))

mit \(\delta_{total} = \delta(s,a) gdw (s,a) \in Def(\delta), sonst s_{tot}\)

Fenster schliessen

Womit wird die Klasse der von einem DEA akzeptierten Sprachen notiert?

DFA\(\Sigma\) (Deterministic Finite Automata) bzw. REG\(\Sigma\) (reguläre Sprachen)

Fenster schliessen

Wann sind zwei Automaten äquivalent?

Wenn sie die gleiche Sprache erkennen.

Fenster schliessen

Wie wird ein Nichtdeterministischer Automat NEA formal beschrieben?

\(A_{NEA} = (\Sigma, S, \delta, S_0, F)\)

Der Unterschied zu einem DEA ist, dass S0 nun eine Menge von Startzuständen ist. Der Wertebereich der Zustandsübergangsfunktion wird auf Mengen erweitert. \(\delta: S \times \Sigma \to P(S)\) (Potenzmengenaxiom)

Fenster schliessen

Womit wird die Klasse der von einem NEA akzeptierten Sprachen notiert?

NFA\(\Sigma\) Nondeterministic Finite Automata

Fenster schliessen

Wozu dient das Trellis-Schema?

Visualisierung einer Eingabesequenz w in einen NEA: Vertikal werden die möglichen Zustände aufgelistet, horizontal die Eingabesequenz. Es werden alle möglichen "Wege" eingetragen, sodass man nachvollziehen kann, welcher Weg in einer Sackgasse mündet und welcher zu einem Endzustand führt.

Fenster schliessen

Wie erfolgt bei einem NEA die Berechnung von \(\delta\)* unter Berücksichtigung der Zustandsmenge S' \(\subseteq\)S?

\(\delta\)* (S', aw) = \(\delta\)*\((\cup \delta(s,a), w), a \in \Sigma, w \in \Sigma^*\)

Fenster schliessen

Welche Fragestellungen ergeben sich bei der Analyse von formalen Sprachen?

1.) Akzeptieren beide Varianten die gleiche Klasse von Sprachen L?

2.) Ist ein Automatentyp mächtiger als der andere? D.h., ist die Klasse der von dem einen Automatentyp akzeptierten Sprachen eine Unterklasse der von dem anderen Automaten akzeptierten Sprachen?

3.) Sind die Klassen verschieden, enthalten aber Sprachen, die beide akzeptieren? (Schnittmenge nicht leer, aber Klassen sind ungleich)

4.) Sind die Klassen verschieden und disjunkt? (Schnittmenge leer)