Flashcards

Flashcards 80 Flashcards
Students 4 Students
Language Deutsch
Level University
Created / Updated 29.03.2016 / 02.10.2018
Licencing Not defined
Weblink
Embed
0 Exact answers 80 Text answers 0 Multiple-choice answers
Close window

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

 

 

Close window

Was ist ein Alphabet?

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

Close window

Was ist eine Zeichenreihe?

Reihe aus Elementen eines Alphabets

Close window

Was ist eine Sprache?

Menge von Zeichenreihen aus Eingabezeichen

- Menge der Zeichenreihen einer natürlichen Sprache

- Menge aller von einem endlichen Automaten akzeptierten Zeichenreihen

Close window

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.

Close window

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.

Close window

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

| Potenzmenge des Alphabetes | = 2 |Alphabet|

Close window

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