Informatik Grundlagen – Formale Sprachen und Grammatiken
Karteikarten zum Thema „Informatik“ · 16 Karten · von atrio. Beispiele: Was definiert eine formale Sprache? · Was ist ein Alphabet in der theoretischen Infor…
Karten
16 KartenWas definiert eine formale Sprache?
Rückseite
Eine formale Sprache ist eine Menge von Wörtern über einem endlichen Alphabet Σ. Jedes Wort ist eine endliche Symbolfolge aus Σ.
Was ist ein Alphabet in der theoretischen Informatik?
Rückseite
Ein Alphabet Σ ist eine endliche, nicht-leere Menge von Symbolen (z. B. {0,1} oder {a,b,c}). Symbole sind atomare, nicht weiter zerlegbare Einheiten.
Wie wird das leere Wort notiert und was ist seine Länge?
Rückseite
Das leere Wort wird mit ε (oder λ) bezeichnet und hat die Länge 0. Es ist Element von Σ* für jedes Alphabet Σ.
Was beschreibt die Kleene-Stern-Operation Σ*?
Rückseite
Σ* ist die Menge aller endlichen Wörter über Σ, einschließlich ε. Es ist die Hülle von Σ unter Konkatenation und bildet einen Monoid.
Was ist eine formale Grammatik G = (N, Σ, P, S)?
Rückseite
Eine Grammatik besteht aus Nichtterminalmenge N, Terminalalphabet Σ, Produktionsmenge P und Startsymbol S ∈ N. Sie erzeugt eine formale Sprache.
Was unterscheidet Terminal- von Nichtterminalsymbolen?
Rückseite
Terminalsymbolen (aus Σ) erscheinen im erzeugten Wort, Nichtterminalsymbolen (aus N) werden durch Produktionen weiter ersetzt. Nur Terminalwörter gehören zur Sprache.
Wie lautet die Definition der von G erzeugten Sprache L(G)?
Rückseite
L(G) = { w ∈ Σ* | S ⇒* w }, also alle Terminalwörter, die vom Startsymbol S durch beliebig viele Produktionsanwendungen ableitbar sind.
Welche vier Typen definiert die Chomsky-Hierarchie?
Rückseite
Typ 0: uneingeschränkt, Typ 1: kontextsensitiv, Typ 2: kontextfrei, Typ 3: regulär. Jeder Typ ist echte Teilmenge des vorherigen.
Was kennzeichnet eine reguläre Grammatik (Typ 3)?
Rückseite
Produktionen der Form A → aB oder A → a (rechtslinear) bzw. A → Ba oder A → a (linkslinear). Erzeugt reguläre Sprachen, erkennbar durch endliche Automaten.
Was ist eine kontextfreie Grammatik (Typ 2)?
Rückseite
Produktionen der Form A → α mit A ∈ N, α ∈ (N ∪ Σ)*. Linke Seite besteht aus genau einem Nichtterminal. Erzeugt kontextfreie Sprachen, parsbar mit Kellerautomaten.
Wann ist eine Grammatik kontextsensitiv (Typ 1)?
Rückseite
Produktionen α → β mit |α| ≤ |β| (Länge nicht abnehmend), Ausnahmsregel: S → ε erlaubt, wenn S nicht rechts vorkommt. Erkannt von linear beschränkten Automaten.
Welchen Automaten-Typ ordnet die Chomsky-Hierarchie Typ 3 zu?
Rückseite
Reguläre Sprachen (Typ 3) werden von endlichen Automaten (DFA/NFA) erkannt. Kein Speicher außer endlichem Zustandsraum.
Welchen Automaten benötigen kontextfreie Sprachen (Typ 2)?
Rückseite
Kontextfreie Sprachen werden von Kellerautomaten (PDA) erkannt. Der Stack bietet unbegrenzten Speicher mit LIFO-Zugriff für Verschachtelungen.
Was besagt das Pumping-Lemma für reguläre Sprachen?
Rückseite
Für jede reguläre Sprache L existiert p ≥ 1, sodass jedes w ∈ L mit |w| ≥ p als w = xyz zerlegbar ist mit |xy| ≤ p, |y| > 0 und xy^iz ∈ L für alle i ≥ 0.
Wie beweist man, dass eine Sprache nicht regulär ist?
Rückseite
Man wendet das Pumping-Lemma an: Annahme Regularität, wähle geeignetes w ∈ L, zeige, dass für jede Zerlegung ein i existiert mit xy^iz ∉ L – Widerspruch.
Was ist der Unterschied zwischen DFA und NFA?
Rückseite
DFA: deterministisch, genau ein Folgezustand pro Zustand und Eingabesymbol. NFA: nichtdeterministisch, mehrere oder keine Folgezustände möglich, ε-Übergänge erlaubt. Beide erkennen genau die regulären Sprachen.