¶ Sprachen und Automaten
¶ Natürliche vs. Formale Sprache
| Merkmal | Natürliche Sprache | Formale Sprache |
|---|---|---|
| Verwendung | Alltagssprache, Kommunikation | Mathematik, Logik, Programmierung |
| Struktur | Unstrukturiert, oft mehrdeutig | Streng geregelt, eindeutig |
| Grammatik | Komplex, mit Ausnahmen | Klar definiert, ohne Ausnahmen |
| Zielgruppe | Menschen | Menschen & Maschinen |
| Flexibilität | Hoch (z. B. Metaphern, Umgangssprache) | Gering (nur definierte Ausdrücke erlaubt) |
| Eindeutigkeit | Gering (Kontextabhängigkeit) | Hoch (jede Aussage klar interpretierbar) |
| Beispiel | „Wenn es regnet, nehme ich einen Schirm.“ | „Wenn A, dann B“ bzw. „A ⇒ B“ |
¶ Beispiel Eindeutigkeit
„Ich sehe den Mann auf dem Berg mit dem Fernrohr.“
- ...
- ...
¶ Grundbegriffe
- Syntax
- Semantik
- Alphabet (Σ) = endliche, nichtleere Menge an Zeichen.
- Wort (Σ*) = über einem Alphabet Σ ist eine endliche Aneinanderreihung von Zeichen aus Σ. ε = leeres Wort. |𝑤| = Länge eines Wortes
- Formale Sprache = eine Teilmenge von Σ∗.
¶ Grammatik
Grammatik [G] ist ein 4-Tupel G = (N,T,P,S)
- N: endliche Menge der Nichtterminale
- T bzw. Σ: endliches Terminalalphabet
- P: endliche Menge der Produktionen
- S ∈ N: Startsymbol
mehr dazu auf http://gts.lernsax.de/d.demeny/aufgaben.html
¶ Produktionsregeln
Beschreiben, wie ein Nichtterminalsymbol durch eine Kombination aus Terminal- und/oder Nichtterminalsymbolen ersetzt werden kann
Darstellungsformen
- Textform (A → α)
- Backus-Naur-Form
- Syntaxdiagram
¶ Backus-Naur-Form (BNF)
<Symbol> ::= <Regel>
- z.B.:
<S> ::= a<A>
<A> ::= a<B>
<A> ::= a
<B> ::= b
¶ Erweiterte Backus-Naur-Form
EBNF erlaubt kompaktere Schreibweise mit zusätzlichen Symbolen:
- "[ ]" für optionale Teile
- { } für Wiederholungen
- | für Alternativen
- Beispiel von oben:
<S> ::= a<A>
<A> ::= a<B>
<B> ::= b
mehr dazu auf https://info-wsf.de/erweiterte-backus-naur-form-ebnf/
¶ Syntaxdiagram
¶ Beispiel
E-Mail:
G=(N,T,P,S)
N={S,NAME,SUB,TLD,DOMAIN}
T={a,b,@,.}
P={
S -> NAME@SUBDOMAIN.TLD,
Name -> aName|bName|a|b,
SUB -> NAME.|NAME.SUB|ε,
DOM -> NAME,
TLD -> NAME
}
S=S
Float:
G = {N,T,P,S}
N = {S,VALUE,ZIFFER}
T = {0,1,2,3,4,5,6,7,8,9,.,+,-}
P = {
S->+VALUE.VALUE|-VALUE.VALUE,
VALUE->ZIFFER VALUE | ZIFFER,
ZIFFER->0|...|9}
S = S
¶ Ableiten von Wörtern
Durch schrittweises Anwenden von Produktionsregeln, können Wörter abgeleitet werden. Eine Ableitung endet, wenn das Wort nur noch aus Nichtterminalen besteht.
Die Ableitung kann dargestellt werden
- schrittweise
- als Baum
Beispiel:
Ableitungs des Wortest ababa aus den Produktionsregeln
S -> a | b | EPSILON | a S a | b S b
- schrittweise: S -> aSa -> abSba -> ababa
- als Baum
¶ Übung
¶ Chomsky Hierachie
Die Chomsky-Hierarchie ist eine Klassifikation formaler Sprachen. Die Einteilung in die Typen erfolgt danach, welche Produktionsregeln in einer Grammatik erlaubt sind und welche Berechnungsmodelle die Sprache erzeugen oder erkennen können:
- website zu Grammatiken, Formale Sprachen und Chomsky: https://info-wsf.de/grammatiken-und-formale-sprachen/
- hier vereinfacht die Chomsky Hirachie: https://studyflix.de/informatik/chomsky-hierarchie-1442
¶ Typ 3: Reguläre Sprachen
Linke Seite ist ein Nichtterminal, rechte Seite ist höchstens ein Terminal gefolgt von einem Nichtterminal (rechts- oder linkslinear)
¶ Typ 2: Kontextfreie Sprachen
Linke Seite besteht aus genau einem Nichtterminal (A → γ)
¶ Typ 1: Kontextsensitive Sprachen
Länge der rechten Seite ≥ Länge der linken Seite (αAβ → αγβ), Kontext A darf nur im selben Kontext ersetzt werden
¶ Typ 0: Allgemeine Regelspachen
Keine Einschränkung: α → β, wobei α mindestens ein Nichtterminal enthält
¶ Beispiele
jeweils ein Beispiel für Typ 1-3: Beispiele_Chomsky
¶ Automaten
Ein Automat ist wie ein „Prüfer“, der entscheidet, ob ein gegebenes Wort zu einer bestimmten Sprache gehört.
Die Sprachtypen der Chomsky-Hierachie können von verschiedenen Automatentypen erkannt werden.
¶ Deterministischer endlicher Automat
5-Tupel 𝐴=(𝑄, 𝑠,Σ, 𝐹, 𝛿) mit:
- 𝑄 … nicht leere, endliche Menge von Zuständen,
- 𝑠∈𝑄 … Startzustand
- Σ … nicht leeres, endliches Eingabealphabet
- 𝐹 ⊆𝑄 … Menge der akzeptierenden Finalzustände
- 𝛿:𝑄×Σ→𝑄 … Zustandsübergangsfunktion, die jeder Kombination aus einem Zustand und einem Eingabezeichen einen Nachfolgezustand zuordnet.
¶ Sprache eines Automaten
Die von einem endlichen Automaten A akzeptierte Menge von Worten L(A) ist:
'L(A)= {w ∈ Σ* | δ(s,w) ∈ F}'
L(A) heißt auch die Sprache von A.
¶ Beispielaufgaben
2 Beispielaufgaben + weitere Übungsaufgaben: Beispielaufgaben_Automaten
¶ Reguläre Ausdrücke (regex)
Ein regulärer Ausdruck ist in der theoretischen Informatik eine Zeichenkette, die der Beschreibung von Mengen von Zeichenketten mit Hilfe bestimmter syntaktischer Regeln dient.
hier eine Seite für regex https://regex101.com/
¶ Ausdrücke
Eine Tabelle zu den herkömmlichen Ausdrücken: Ausdrücke
¶ Compiler vs. Interpreter
¶ Compiler
Ein Compiler ist ein Computerprogramm, das Quellcode einer bestimmten Programmiersprache (z.B.: Pyhton, JavaScript, C++, usw.) in einer Form überstezt, die von einem Computer ausgeführt werden können (Maschienencode oder Zwischensprachen wie Assembly). Er übersetzt zuert um danach den Code (übersetzten) ausführen zu können.
¶ Kompelierungsphasen:
- Lexikalische Analyse
- Syntaktische Analyse
- Semantische Analyse
- Erzeugung von Zwischencode
- Optimierung
¶ Vorteile:
- Ausführbare Dateien sind schnell
- Keine Quelltextoffenlegung nötig
- Reverse Engineering ist möglich (Reverse Engenieering: https://de.wikipedia.org/wiki/Reverse_Engineering)
¶ Nachteile:
- Aufwendig & Teuer, weil änderungen im Quellcode für Neucompelierung sorgen können
¶ Interpreter
Ein Interpreter ist ein Computerprogramm, das den Quellcode einer bestimmten Programmiersprache (z.B.: Python, Java, PHP, usw.) direkt Zeile für Zeile einliest, übersetzt und sofort ausführt, ohne zuvor eine eigenständige ausführbare Datei zu erzeugen.
¶ Interpreterphasen:
- Lektische Analyse
- Syntaktische Analyse
- Direkte Ausführung
¶ Vorteile:
- Einfacher zu erstellen als Compiler
- Leichter anpassbar
¶ Nachteile:
- Langsamer als ausführbare Dateien, da weniger Rechenleistung
- Extra Belastung für den Arbeitsspeicher
¶ Weitere Quellen:
- INF-SCHULE: https://inf-schule.de/automaten-sprachen/interpretercompiler
- YouTube Video von Florian Dalwigk über Compiler und Interpreter: https://www.youtube.com/watch?v=DYsQj5bJaZI
- YouTbe Video von Maik Aicher über Compiler (detailiert): https://www.youtube.com/watch?v=D60WqAjxzk4
- Studyflix Video über Compiler: https://studyflix.de/informatik/compiler-624/video
¶ Chancen und Risiken von AI
¶ Offene Punkte
- links und rechts-regulär
- Beispiel Abi Aufgaben
- epsilon Regel