Automaten + Formale Sprachen

Formale Sprache L: Eine, durch eine Grammatik geregelte, oft unendliche Menge an Wörtern aus einem Alphabet Σ, deren syntaktische Struktur durch eine Grammatik geregelt wird. Sie gibt jedoch keine Information über die Syntax (Bedeutung) und muss somit weder sinnvoll noch interessant sein.

Die formale Sprache L fokussiert sich auf die syntaktische Struktur und gibt keine Vorgabe hinsichtlich der Bedeutung oder des Inhalts der Wörter."

Alphabet Σ: eine nichtleere, endliche Menge von Symbolen. Ein Symbol kann zum Beispiel einem ASCII-Zeichen entsprechen, jedoch auch komplexer sein.

Wort w: eine endliche Folge von Symbolen aus dem Alphabet Σ. Die Menge aller Wörter entspricht Σ*.

Formale Grammatik G: besteht aus einem 4-Tuple (N, T, S ∈ N, P):
- Einer Zustandsmenge N von Nichtterminalen (Teile die noch ersetzt werden müssen)
- Einem Eingabealphabeth T von Terminalen (Teile, durch die N ersetzt werden)
- Einem Anfangszustand S ∈ N
- Den Produktionsregeln P
z.B.: N = {S, A}

T = {0, 1}

S = S

P = {S→1A, A→0A|1B, B → ϵ}
Ein Wort ist erst fertig, wenn alle Nichtterminalen (N) durch Terminale (T) ersetzt wurden.

Reguläre Grammatiken: Bei einer regulären Grammatik wird immer ein N durch eine Folge von Terminalen und max. einem N ersetzt. Sie beschreibt eine reguläre Sprache und kann entweder Rechts- oder Linksregulär sein:
Rechtsregulär (Das Nichtterminal steht immer rechts): A -> aB | a | ε
das Wort entwickelt sich von links nach rechts
Linksregulär (Das Nichtterminal steht immer links): A -> Ba | a | ε
das Wort entwickelt sich von rechts nach links  

Kontextfreie Grammatiken: Bei einer kontextfreien Grammatik wird immer ein Nichtterminal durch eine beliebige Folge von Terminalen und Nichtterminalen ersetzt.

Reguläre ausdrücke: werden verwendet, um eine Sprache formal zu beschreiben:

R = a* beliebige viele a, auch null möglich

R = a+ beliebig viele a

R = b|a entweder a oder b

R = (aa) nur doppelte a verwenden 

R = ε keine Eingabe nötig (nichts)

z.B.: 

R = a*ba* beliebig viele a, gefolgt von einem b, gefolgt von beliebig vielen a

R = b*|(aa)* beliebig viele b oder beliebig viele doppelte a 

R = b*(aa)* beliebige Anzahl b und beliebige Anzahl von doppelt a möglich

R = ε | ba* entweder nichts oder ein b, anschließend beliebig viele a

B = b(b*a)* erst ein b, anschließend eine Abfolge aus beliebig vielen b und einem a. Diese Abfolge kann beliebig wiederholt werden, auch kein einziges mal

Es gilt das jeder endliche Automat in einen Regulären Ausdruck umgewandelt werden kann und jeder reguläre Ausdruck in einen endlichen Automaten.

Endliche Automaten bestehen aus einem 5-Tuple (Q, Σ, q₀ ∈ Q, F, δ):
- Einer Zustandsmenge Q von Nichtterminalen
- Einem Eingabealphabeth Σ von Terminalen
- Einem Anfangszustand q₀ ∈ Q
- Eine Menge von akzeptierenden Zuständen F ⊆ Q
- Der Übergangsfunktion δ die sich als Graph, Tabelle oder Funktion angeben lässt
TRAP dient als Zustand, aus dem das Entkommen nicht mehr möglich ist
Der Automat akzeptiert eine Eingabefolge, wenn er sich am Ende der Eingabe in einem akzeptierenden Zustand befindet.

Funktionsweise:
Endliche Automaten akzeptieren eine gewisse Sprache mit w ∈ Σ.
- Er beginnt im Startzustand q₀.
- Es wird das erste Zeichen des Wortes w gelesen und der Zustand entsprechend gewechselt.
- Anschließend wird das nächste Zeichen gelesen und er Zustand entsprechend angepasst…
- Wenn das Wort zu Ende gelesen ist wird geprüft, ob es sich um einen akzeptierten Endzustand handelt.
- Wenn es sich um einen akzeptierten Zustand handelt, wird das Wort w akzeptiert, Wenn nicht verwirft der Automat es
Die Menge aller von dem Automaten M akzeptierten Wörter werden als die von M akzeptierte Sprache L(M) bezeichnet.

DEA: Ein Automat ist deterministisch, wenn jede Eingabe nur eine eindeutige Zustandsfolge an einen anderen Zustand hat.
NEA: Ein Automat ist nichtdeterministisch, wenn es für eine Eingabe mehr als einen möglichen Folgezustand gibt. 

Es kann überprüft werden, ob das Verfahren Korrekt abgelaufen ist, indem festgestellt wird, ob der neue DEA die gleichen Worte akzeptiert wie der Ausgangs NEA

Endliche Automaten sind auf reguläre Sprachen beschränkt, da sie keine rekursiven Strukturen wie L{aⁿbⁿ} zulassen, wobei a und b gleich oft vorkommen müssen.
Hierbei helfen Kellerautomaten, welche einen Keller als Speicher besitzen. Im LK sind nur deterministische Kellerautomaten relevant.

Ein PDA hat einen Speicher in From eines Stacks (LIFO-Prinzip).
Ein Wort liegt in der Sprache, wenn der Keller nur noch das Kellersymbol # enthält, die Zustandsfolge abgearbeitet ist und man sich im Endzustand befindet. Die möglichen Aktionen hängen nicht nur vom Zustand und den gelesenen Eingabezeichen ab, sondern auch vom obersten Kellersymbol. 

Kellerautomaten bestehen aus einem 7-Tuple (Z, Σ, K, δ, q₀ ∈ Z, #, F):
- Einer Zustandsmenge Z von Nichtterminalen
- Einem Eingabealphabeth Σ von Terminalen
- Einem Kelleralphabet K, einer endlichen, nicht leeren Menge
- Der Übergangsfunktion δ, welche jeder Kombination aus Zustand, Kellersymbol und Eingabesymbol eine Menge von Kombinationen aus Folgezustand und einer (ggf. leeren) endlichen Folge von Kellersymbolen zuordnet.
- Einem Anfangszustand q₀ ∈ Z
- Einem Kellersymbol #, ein Element aus K
- F ist die Menge von Endzuständen, einer Teilmenge von Z

Zustandsübergänge:
Die Zustandsübergänge zwischen zwei Zuständen sind nun komplizierter.  Ein möglicher gerichteter Übergang könnte z.B. folgendermaßen beschriftet sein: (#, p):Z#
- Das oberste Kellersymbol # (wird gelesen und entfernt)
- Das Eingabesymbol p wird gelesen und der Automat wechselt in den nächsten Zustand.
- Die Symbole des Kelleralphabets werden in der Reihenfolge: erst #, dann Z, auf den Keller geschrieben
Somit wechselt der Automat den Zustand, wenn das Eingabesymbol und das oberste Kellersymbol mit den Vorraussetzungen übereinstimmt. Nach dem Übergang liegt ein weiteres Symbol des Kelleralphabets im Keller, Z.

Scanner, Parser und Interpreter spielen eine wichtige Rolle bei der Verarbeitung von Texten, die in regulären Sprachen verfasst sind.

Scanner (Lexikalische Analyse): zerlegt den Text in Token (Token = Symbole aus dem Eingabealphabeth)

Parser (Syntaxanalyse): Prüft die Sequenz von Token, die der Scanner erzeugt hat, auf ihre syntaktische Korrektheit, indem er die Produktionen der Grammatik rückwärts durchläuft.

Interpreter (Semantische Analyse): interpretiert die Bedeutung des vom Parser erzeugten Syntaxbaumes.