AFS Auswendig lernen

Alphabet

Definition

Ein Alphabet ist eine endliche, nichtleere Menge von Symbolen.

endliches Wort

Definition

Ein Wort über einem Alphabet $\Sigma$ ist eine Endliche Folge $w=w_1\cdots w_n$ von Symbolen aus $\Sigma$

Sprachen

Formale Sprache

Definition

Eine Sprache über $\Sigma$ ist eine Menge $L\subseteq {\Sigma }^{\ast }$

Konkatenation

Definition

$L^{n+1}:=L^n\cdot L$

Kleene-Stern

Definition

$L^{\ast }:={\bigcup }_{n\ge 0}{L}^n$

Automaten

DEA

Definition

$A=(Q,\Sigma ,q_s,\delta ,F)$

• Q eine endliche Menge von Zuständen ist
• $\Sigma$ ein Eingabealphabet ist
• $q_s\in Q$ der Anfangszustand ist
• $\delta :Q\times \Sigma ⟶Q$ die Übergangsfunktion ist
• $F\in Q$ eine Menge von akzeptierenden Zuständen ist

NEA

Definition

$A=(Q,\Sigma ,q_s,△,F)$

• Q eine endliche Menge von Zuständen ist
• $\Sigma$ ein Eingabealphabet ist
• $q_s\in Q$ der Anfangszustand ist
• $△:Q\times \Sigma \times Q$ die Übergangsrelation ist
• $F\in Q$ eine Menge von akzeptierenden Zuständen ist

minimal-DEA

Definition

Ein minimaler DEA hat die minimale Menge and Zuständen, aber akzeptiert immernoch die gleiche Sprache

kanonischer-DEA

Definition

Sei $L\subseteq {\Sigma }^{\ast }$ eine Reguläre Sprache. (sodass Die Nerode-Rechtskongruenz ${\simeq }_L$ einen endlichen Index hat)
Der kanonische DEA $A_L=(Q,\Sigma ,q_s,\delta ,F)$ zu L ist definiert durch:

• $Q:=\{[u{]}_L|u\in {\Sigma }^{\ast }\}$
• $q_s:=[\epsilon {]}_L$
• $\delta ([u{]}_L,a):=[ua{]}_L$
• $F:=[u{]}_L|u\in L$

Kellerautomaten (PDA)

Definition

Ein Kellerautomat (PDA) ist ein Tupel
$A=(Q,\Sigma ,\Gamma ,q_s,Z_s,△,F)$, wobei

• $Q$ eine endliche Menge von Zuständen ist,
• $\Sigma$ das Eingabealphabet ist,
• $\Gamma$ das Kelleralphabet ist,
• $q_s\in Q$ der Anfangszustand ist,
• $Z_s\in \Gamma$ das Kellerstartsymbol ist,
• $△\subseteq Q\times (\Sigma \cup \{\epsilon \}\times \Gamma \times {\Gamma }^{\ast }\times Q)$ eine endliche Übergangsrelation ist und
• $F\subseteq Q$ eine Menge von akzeptierenden Zuständen ist.

Kellerautomat per leeren Keller

⇒ $B=(Q,\Sigma ,\Gamma ,q_0,Z_0,△)$

Die Chomsky-Hierarchy

	Name	Grammatik	Sprache	Automaten
Typ 0		Jede
Typ 1	monoton	$w⟶u\Vert w\Vert \le \Vert u\Vert$
Typ 2	Kontextfreie Grammatik	$A⟶w$	Kontextfreie Sprache	Kellerautomat
Typ 3	rechtslinear	$A⟶u$ oder $A⟶uB$	Reguläre Sprache	DEA, NEA, ε-NEA, wort-NEA

Reguläre Sprache

Definition

Eine Sprache $L\subseteq {\Sigma }^{\ast }$ heißt regulär, wenn es einen DEA $A$ gibt mit $L=L(A)$

Die Nerode-Rechtskongruenz

Definition

Es sei $L\subseteq {\Sigma }^{\ast }$ eine Sprache. Für $u,v\in \Sigma$ definiren wir:
$u{\simeq }_{L}v⟺\forall w\in {\Sigma }^{\ast }:uw\in L⟺vw\in L$

Satz von Myhill und Nerode

Definition

Eine Sprache $L$ ist regulär genau dann, wenn Die Nerode-Rechtskongruenz ${\simeq }_L$ einen endlich Index hat.

Link to original

Reguläre Ausdrücke

Definition

Sei $\Sigma$ ein endlichee Alphabet.
Die Menge $Re{g}_{\Sigma }$ der regulären Ausdrücke über $\Sigma$ ist induktiv definiert:

• $\varnothing ,\epsilon ,a$ (für $a\in \Sigma$) sind Elemente von $Re{g}_{\Sigma }$
• Sind $r,s\in Re{g}_{\Sigma }$, so auch
  • $(r+s)\in Re{g}_{\Sigma }$,
  • $(r\cdot s)\in Re{g}_{\Sigma }$,
  • $r^{\ast }\in Re{g}_{\Sigma }$.

Der Satz von Kleene

Definition

Für eine Sprache $L\in {\Sigma }^{\ast }$ sind äquivalent:

1. Es gibt einen regulären Ausdruck $r$ mit $L=L(r)$.
2. $L$ ist regulär

Pumping Lemma

Reguläre Spache

Kontraposition

kontextfreie Sprachen

Link to original

Grammatik

Definition

Eine Grammatik ist von der Form $G=(N,\Sigma ,P,S)$ wobei

• $N$ und $\Sigma$ endliche, disjunkte Alphabete von Nichtterminalensymbol bzw Terminalsymbol ist,
• $S\in N$ das Startsymbol ist,
• $P\subseteq (N\cup \Sigma {)}^{+}\times (N\cup \Sigma {)}^{\ast }$ eine endliche Menge von Ersetzungsregeln ist.

Kontextfreie Grammatik

Definition

Eine Grammatik ist kontextfrei falls alle Regeln die Form $A⟶w$ haben mit $A\in N,w\in (\Sigma \cup N{)}^{\ast }$

Chomsky-Normalform

Definition

Eine Kontextfreie Grammatik $(N,\Sigma ,P,S)$ ist in Chomsky-Normalform, wenn alle Ableitungsregeln die folgende Form haben:

• $A⟶a$ oder $A⟶BC$ mit $A,B,C\in N,a\in \Sigma$
• $S⟶ϵ$ ist erlaubt, wenn es keine Regeln $A⟶BC$ mit $S\in \{B,C\}$ gibt.

Ableitungsbäume

Definition

Sei $G=(N,\Sigma ,P,S)$ eine Kontextfreie Grammatik
Ein partieller Ableitungsbaum ist ein gewurzelter, geordneter Baum, dessen Knoten mit Symbolen aus $N\cup \Sigma$ beschriftet sind, so dass

• jeder innere Knoten mit einem Nichtterminalensymbol beschriftet ist.  
• jedes Blatt mit einem Terminalsymbol oder Nichtterminalensymbol beschriftet ist. 
• wenn ein innerer Knoten mit einen Nichtterminalensymbol beschriftet ist, so gibt es eine Ableitungsregel für die Kinder.

Bei einem vollständiger Ableitungsbaum

• ist die Wurzel mit S beschriftet.
• jedes Blatt mit einem Symbol aus $\Sigma$ beschriftet ist.

Abgeschlossenheit der Sprach Typen

Abschlusseigenschaften der regulären Sprachen

Definition

Sind $L_1$ und $L_2$ regulär dann sind

• Vereinigung $L_1\cup L_2$
• Komplement ${\overline{L}}_1$
• Schnitt $L_1\cap L_2$
• Konkatenation $L_1\cdot L_2$
• Kleene-Stern $L_1^{\ast }$
  regulär.

Abschlusseigenschaften der kontextfreien Sprachen

Definition

Sind $L_1$ und $L_2$ kontextfrei dann sind

• Vereinigung $L_1\cup L_2$
• Konkatenation $L_1\cdot L_2$
• Kleene-Stern $L_1^{\ast }$
  kontextfrei.