Formale Sprachen Flashcards
Aufbau und Funktionsweise von Sprachen
Sprache besteht aus der Syntax (Regelwerk, formale Korrektheit) und der Semantik (Sinn).
Sprachen dienen zur Kommunikation. Der Sender übermittelt eine Information mithilfe der Sprache an einen Empfänger. Der Empfänger interpretiert die Sprache und erhält daraus eine Information.
Was ist ein Syntaxbaum und woraus besteht er?
Ein Syntaxbaum zeigt die syntaktische Struktur des Satzes vom Allgemeinen zum Spezifischen.
Terminalsymbol: hier endet Regelanwendung (Blätter im Baum / nur rechte Seite der Regel)
Nichtterminalsymbol: Platzhalter (innere Knoten / mind. 1-mal links vom Pfeil)
Alphabet: alle Bestandteile einer Sprache
Leeres Wort ε: Wort der Länge 0
Länge einer Zeichenkette │k│: Anzahl der Terminale, die k enthält; │ε│ = 0
Funktion und Aufbau von Regeln
Eine Sprache wird durch Regeln aufgebaut. Sie geben an , wie aus Wörtern durch eine Grammatik neue Wörter bzw. Symbolfolgen entstehen.
Eine Regel besteht aus einer linken Seite, einem Pfeil → und einer rechten Seite. Links steht ein Nichtterminal und rechts eine Term aus Nichtterminalen und Terminalen.
Wie benutz man Regeln?
Alle Wörter, die sich mit den gegebenen Regeln erzeugen lassen, gehören zur Sprache.
Zur Ableitung eines Wortes beginne mir der ersten Regel. Dieses Nichtterminal heißt Startsymbol.
Wende die Regel auf den Term an, indem das Nichtterminal durch die rechte Seite der entsprechenden Regel ersetzt wird. Wende so lange die Regel an, bis nur noch Terminale übrig sind. Das resultierende Wort ist Teil der Sprache.
Definition und Darstellung einer Grammatik
Eine (formale) Sprache über einem Alphabet ∑ ist eine Teilmenge der Menge ∑* aller möglichen Wörter über ∑.
Die „korrekte“ Teilmenge und somit die Sprache wird durch die Grammatik G definiert:
1. Menge von Variablen V (Nichtterminale)
2. Alphabet ∑ (Terminale) ( kann auch
aus zsmgesetzten Zeichen (Token)
bestehen)
3. Menge der Produktionen P
(Ableitungsregeln)
4. Eine Startvariable S є V
5. Mit ∑ ∩ V = 0
Produktionen können mit EBNF oder in Diagrammform mit Syntaxdiagrammen dargestellt werden.
Wozu braucht man (endliche) Automaten?
Computer können nur Vorgänge bearbeiten, die sich durch eine formale Sprache ausdrücken lassen. Die Maschine muss eine Syntaxprüfung durchführen.
Dies kann mithilfe eines erkennenden Automaten (EA) stattfinden. Erst danach ist eine eindeutige Weiterverarbeitung möglich.
Aufbau und Funktionsweise eines DEAs
Der (deterministische) endliche Automat dient zur Erkennung, ob ein Wort Teil einer (regulären) formalen Sprache ist.
Definiert wird ein EA durch seine endliche Anzahl an Zuständen, ein Startzustand, mind. einem Endzustand, den Zustandsübergängen und dem Eingabealphabet.
Ein Wort wird zeichenweise vom Automaten abgearbeitet und genau dann akzeptiert, wenn nach vollständiger Abarbeitung des Wortes ein Endzustand des Automaten erreicht ist.
Besserer DEA?
Endliche Automaten, bei denen es zu jedem Zustand bei jedem Eingabezeichen einen Zustandsübergang gibt, nennt man vollständigen Automaten. Durch Hinzufügen von Fangzuständen kann jeder DEA zum vollständigen Automaten ergänzt werden. Vollständige Automaten stoppen immer erst dann, wenn alle Zeichen abgearbeitet sind.
