4-Grammatiken_und_kontextfreie_Sprachen.tex

\section{Grammatiken und kontextfreie Sprachen}
Wechsel des Standpunkts Spracherkennung \-> Spracherzeugung\\
Werkzeug: Phasenstrukturgrammatiken\\
Ansatz: Neben Alphabet gibt es weitere Symbole (Variable) und ein Regelsystem mit dem Worte, die Variable enthalten, geändert werden können.
\begin{Bsp}
	\begin{align*}
		\Sigma &= \{ a,(,),*,+ \}\\
		N &= \{E\}\\
		\shortintertext{Regeln:}
		\{\ E &\-> a,\\
		E &\-> (E*E),\\
		E &\-> (E+E)\\
		\}\ \phantom{ E }\\
		\shortintertext{Startsymbol $E$}
		E &\=> a\\
		E &\=> (E*E) \=> (a*E)\\
		&\=> (a*(E+E)) \=> \dots \=> (a*(a+a))
	\end{align*}
\end{Bsp}

\begin{Def}[Chomsky]
	Eine \underline{Grammatik} ist ein 4-Tupel $(N,\Sigma,P,S)$
	\begin{itemize}
	\item $N$ ist endliche Menge von \underline{Nichtterminalsymbolen}
	\item $\Sigma$ ist Alphabet von \underline{Terminalsymbolen} (Variablen)
	\item $P\subset (N\cup\Sigma)^*N(N\cup\Sigma)^* \x (N\cup\Sigma)^*$ endliche Menge von Regeln bzw. \underline{Produktionen}
	\item $S\in N$ das \underline{Startsymbol}
	\end{itemize}
\end{Def}
\begin{Def}[name={[Ableitungsrelation]}]
	Die \underline{Ableitungsrelation} zur Grammatik
	%\rlwarning{Ab hier: Symbol $G$ oder $\mathcal{G}$?}
	%\ptwarning{ich m"ochte $\mathcal{G}$ f"ur Grammatiken verwenden}
	% RL: Korrigiert!
	\begin{align*}
		\mathcal{G} &=(N,\Sigma,P,S) \text{ ist Relation}\\
		\==>_{\mathcal{G}}& \subseteq (N\cup\Sigma)^*\x(N\cup\Sigma)^*\text{ mit}\\
		v&\=>_{\mathcal{G}} w\ ,\ 
		\begin{aligned}[t]
			&\text{falls ex. Produktion}\\
			&l \-> r\in P\text{ und }\\
			&v = v_1lv_2\\
			&w=v_1rv_2
		\end{aligned}\\
		\=>^*& \text{ refl. trans. Hülle von }\=>
	\end{align*}
	\underline{Sprache von $\mathcal{G}$ erzeugt}.
	\[ L(\mathcal{G}) = \{w\in\Sigma^* \mid S\xRightarrow*_{\mathcal{G}} w \}\]
	
	Jede Folge $\alpha_0,\alpha_1,\dots,\alpha_n$ mit $\alpha_i \in (N\cup \Sigma)^*$ mit $\alpha_0=S$ und $\alpha_n\in\Sigma^*$ und $\forall 1\leq i\leq n : \alpha_{i-1} \=>_\mathcal{G} \alpha_i$ heißt \underline{Ableitung von $\alpha_n$}
	
	[\,Jedes solche $\alpha_i$ heißt \underline{Satzform von $\mathcal{G}$}\,]
\end{Def}
$n$ ist \underline{Länge der Ableitung}.
\vspace{.5em}
\begin{Bsp} $\mathcal{G}=(N,\Sigma,P,S)$ mit
	\begin{align*}
		N &= \{S,B,C\}\\
		\Sigma &= \{a,b,c\}\\8
		P &= 
		\begin{aligned}[t]
			 \{ &S \-> aSBC,\ S\->aBC,\ CB\-> BC,\ aB\-> ab,\\
			 &bB\-> bb, bC\-> bc, cC\-> cc \} & \quad\text{Startsymbol }S
		\end{aligned}\\
		L(\mathcal{G}) &=  \{ a^nb^nc^n \mid n\geq 1 \}\\
		S &\=> aBC \=> abC \=> abc \qquad S\=>a\underline{S}BC \=> aa\underline{S}BCBC\\
		S &\=> aSBC \xRightarrow{n-2} n \=> a^{n-1}S(BC)^{n-1} \=> a^n(BC)^n = a^nBCBC \dots \=> a^nBBCCBC\\
		&\=> a^nB^nC^n \xRightarrow* a^nb^nc^n
	\end{align*}
\end{Bsp}
Die Chomsky-Hierarchie teilt die Grammatiken in vier Typen unterschiedlicher Mächtigkeit ein.
\begin{Def}[Chomsky Hierarchie]\
	\begin{itemize}
	\item Jede Grammatik ist eine \underline{Typ-0 Grammatik}.
	\item Eine Grammatik ist \underline{Typ-1} oder \underline{kontextsensitiv}, falls alle Regeln expansiv sind, d.h. $\alpha\->\beta\in P$, dann ist $|\alpha|\leq |\beta|$ mit einer Ausnahme: falls $S$ nicht in einer rechten Regelseite auftritt, dann ist $S\->\epsilon$ erlaubt.
	\item Eine Grammatik heißt \underline{Typ-2} oder \underline{kontextfrei}, falls alle Regeln die Form $A\->\alpha$ mit $A\in N$ und $\alpha\in(N\cup\Sigma)^*$ haben.
	\item Eine Grammatik heißt \uline{Typ-3} oder \uline{regulär}, falls alle Regeln die Form
	\begin{alignat*}{2}
		\text{Form}\quad &A\->w &\quad w&\in\Sigma^*\\
		\text{oder}\quad &A\->aB& a&\in\Sigma,\ B\in N
	\end{alignat*}
	\end{itemize}
	Eine Sprache heißt Typ-$i$ Sprache, falls $\exists$ Typ-$i$ Grammatik für sie.
\end{Def}

\begin{Beobachtung}
	Jede Typ $i+1$ Sprache ist nicht Typ-$i$ Sprache.
\end{Beobachtung}
Jede Typ-3 Grammatik ist Typ-2 Grammatik.\\
Jede Typ-2 Grammatik kann in äquivalente $\epsilon$-freie Typ-2 Grammatik transformiert werden. \-> Typ-1 Grammatik. (Vgl.\ Elmination von $\epsilon$-Produktionen)

Ziel: Hierarchie-Satz (Chomsky)\\
Sei $\mathcal{L}_i$ die Menge der Typ-$i$ Sprachen.\\
Es gilt $\mathcal{L}_3 \subsetneq \mathcal{L}_2 \subsetneq\mathcal{L}_1 \subsetneq\mathcal{L}_0$

\begin{Satz}[name={[Typ-3 Sprache ist regulär]}]
	$L$ ist regulär \<=> $L$ ist Type-3 Sprache
\end{Satz}
\begin{proof}
	\begin{description}[font=\normalfont,labelwidth=\widthof{"'\=>"':},leftmargin=!]
	\item["`\=>"'] Sei $\A =(Q,\Sigma,\delta,q_0,F)$ \ac{DFA} für $L$.\\
		Konstruiere Grammatik $\mathcal{G}=(N,\Sigma,P,S)$
		\begin{alignat*}{2}
			N &=Q &\qquad S&=q_0\\
			q&\in Q\ \mathrlap{\forall a: \delta(q,a)=q'\ \curvearrowright\ q\->aq'\in P}\\
			q&\in F & q&\->\epsilon\in P
		\end{alignat*}
		Zeige noch $L(\mathcal{G})=L(\A)$
	\item["`\<="'] Sei $\mathcal{G}=(N,\Sigma,P,S)$ Typ-3 Grammatik
	Def. $\A=(Q,\Sigma,\delta,q_0,F)$ \ac{NFA}
	\begin{alignat*}{2}
		Q &=N\cup\dots\\
		q_0 &=S\\
		A &\->aB\in P & \delta(A,a)&\ni B\\
		A &\->a,\dots a_n &\qquad n=0\=>A &\in F\\
		&\mathclap{\tikz[shorten >=1pt,on grid,node distance=1.5cm, every state/.style={minimum size=0pt,inner sep=0pt}]{
			\node[state,inner sep=3pt] (q0) {$A$};
			\node [above=0pt of q0.north] {$n>0$: $n$ weitere Zust"ande erforderlich, letzter Endzustand};
			\node[state] (q1) [right=of q0] {};
			\node (dots) [right=of q1] {\dots};
			\node[state,accepting] (qa) [right=of dots] {};
			\path[-stealth] (q0) edge node[auto] {$a_1$} (q1)
				(q1)   edge node[auto] {$a_2$} (dots)
				(dots) edge node[auto] {$a_n$} (qa);
		}}\\
		\text{Zeige noch }\quad
		L(\mathcal{G})&=L(\A) \tag*{\qedhere}
	\end{alignat*}
	\end{description}
\end{proof}

\datenote{09.12.15}

\begin{lemma}
	$\mathcal{L}_3 \subsetneq \mathcal{L}_2$
\end{lemma}
\begin{proof}
	Betrachte $L=\{a^nb^n \mid n\in\N \}$\\
	bekannt: $L$ nicht regulär.\\
	Aber $\exists$ Typ-2 Grammatik für $L$:
	\[ \mathcal{G} = (\{S\}, \{a,b\}, \{S\->\epsilon, S\->aSb \}, S) \]
	Zeige (selbst) $L=L(\mathcal{G})$
\end{proof}

\subsection{Kontextfreie Sprachen}
\begin{itemize}
\item Arithmetische Ausdrücke\\
	$E\->a,E\->(E+E),E\->(E*E)$
\item Syntax von Programmiersprachen%\\[\abovedisplayskip]
	\begin{center}
		\begin{tabular}[t]{r@{ }l}
			<Stmt> &\-> <Var> = <Exp>\\
			&| <Stmt>\,;\,<Stmt>\\
			&| if\,(<Exp>) <Stmt>\\
			&\phantom{|} else <Stmt>\\
			&| while\,(<Exp>) <Stmt>
		\end{tabular}
	\end{center}%\\[\belowdisplayskip]
	Hier: Nichtterminal$\hat=$ Wort in spitzen Klammern <Stmt>;
	Terminalsymbol --- alles andere.
\item Palindrome über $\{a,b\}$
	\[ S\-> aSa \mid bSb \mid a \mid b \mid \epsilon \]
\item Sprache der Werte, die gleich viele Nullen wie Einsen haben $=L$
\end{itemize}
\begin{align*}
	\mathcal{G}: S &\-> 1S0S \mid 0S1S \mid \epsilon\\
	L(\mathcal{G}) &\subseteq L \quad \text{klar}\\
	\uline{\text{Def.:}}\quad d:\Sigma^* &\-> \Z\\
	d(\epsilon) &= 0\\
	d(1w) &= d(w) + 1\\
	d(0w) &= d(w) - 1\\
	\text{Es gilt} & \text{(Beweis per Induktion "uber $v$)} \\
	d(v\cdot w) &= d(v)+d(w)\\[.5em]
	L &= \{ w \mid d(w)=0 \}\\
	\text{Zeige:}\quad L &\subseteq L(\mathcal{G})\\
	\forall w\in L : w&\in L(\mathcal{G})
\end{align*}
Induktion über Länge von $w$
\begin{alignat*}{2}
	&\text{Länge }0:\quad& \epsilon &\in L
		\quad,\quad \epsilon \in L(\mathcal{G})
		\quad,\quad S \-> \epsilon\\
	&\text{Länge}>0:\quad& \text{Ang. } 0w&\in L\\
	&&\curvearrowright d(0w) &= 0\\
	&&\curvearrowright d(w) &= 1 \\
	&&\curvearrowright \exists \text{ k"urzestes Suffix $1w_2$ von $w$ mit $d(1w_2)=1$ }\\
	&&\curvearrowright \exists w_1 : w=w_1 1 w_2\\
	&&\curvearrowright d(w_1)=0 \wedge d(w_2)=0
\end{alignat*}
Per Induktion sind sowohl $S \=>^*w_1$ als auch $S\=>^*w_2$; die erste Produktion ist
$S \to 0S1S$.

Der Fall $1w$ geht analog.

%Abk.: \aclu{CFL}: \acs{CFL}\\
%\phantom{Abk.:} \aclu{CFG}: \acs{CFG}

\begin{Def}[name={[Ableitungsbaum]}] Sei $\mathcal{G}$ \ac{CFG}.\\
	Ein \uline{Ableitungsbaum} zu $w\in L(\mathcal{G})$ ist ein geordneter, markierter Baum $B$.
	\begin{itemize}
	\item Die Wurzel von $B$ ist mit $S$ markiert.
	\item Die inneren Knoten von $B$ sind mit Nichtterminalen markiert.
	\item Jedes Blatt ist mit $x\in\Sigma\cup\{\epsilon\}$ markiert.
	\item Falls Knoten $k_0$ mit $A\in N$ markiert ist und die  Nachfolgerknoten von $k_0$ sind $k_1,\dots, k_n$, dann gibt Produktion $A\-> X_1\dots X_n$ mit $X_i\in\Sigma\cup N$ und $k_i$ ist mit $X_i$ markiert.
	
	\textbf{Oder:} $n=1$, die Produktion ist $A\->\epsilon$ und $k_1$ ist mit $\epsilon$ markiert.
	\end{itemize}
	Die Markierungen der Blätter von links nach rechts gelesen ergeben $w$.
\end{Def}

\begin{Bsp}\label{bsp:Ableitungsbaum} Siehe \autoref{fig:Ableitungsbäume}.
	\begin{figure}[H]\centering
		\begin{subfigure}[t]{.25\linewidth}\centering
			\tikz{\Tree [.$E$ $a$ ]}
			\caption{$E \Rightarrow a$}
		\end{subfigure}
		\begin{subfigure}[t]{.4\linewidth}\centering
			\begin{tikzpicture}[every tree node/.style={execute at begin node=$, execute at end node=$}]
				\Tree [.E (
			          [.E a ]
			          +
			          [.E ( [.E a ] * [.E a ] ) ]
			          )
			        ]
			\end{tikzpicture}
			\caption[$E \xRightarrow{*} (a+(a*a))$]{$E \xRightarrow{*} (a+(a*a)) \newline \longrightarrow E \Rightarrow (E+E)\Rightarrow(E+(E*E))\xRightarrow{*}$}
		\end{subfigure}
		\begin{subfigure}[t]{.3\linewidth}\centering
			\begin{tikzpicture}[every tree node/.style={execute at begin node=$, execute at end node=$}]
				\Tree [.A X_1 X_2 \edge[draw=none]; {\dots} X_n ]
			\end{tikzpicture}
			\caption{$A\rightarrow X_1\dots X_n$}
		\end{subfigure}
		\caption{Ableitungsbäume zu \autoref{bsp:Ableitungsbaum}}\label{fig:Ableitungsbäume}
	\end{figure}
	$\exists$ Ableitungsbaum für $w$ genau dann, wenn $S \xRightarrow{*} w$
\end{Bsp}
\begin{Def}[name={[Eindeutigkeit von \acs*{CFG} und \acs*{CFL}]}]\
	\begin{itemize}
	\item $\mathcal{G}\in$ \ac{CFG} heißt \uline{eindeutig}, falls es für jedes Wort $\in L(\mathcal{G})$ genau einen Ableitungsbaum gibt.
	\item Eine kontextfreie Sprache heißt \uline{eindeutig}, falls $\exists$ eindeutige \ac{CFG} für sie.
	\end{itemize}
\end{Def}
\begin{Bsp}
	\begin{align*}
		L &= \{ a^ib^jc^k \mid i=j\text{ oder }j=k \}\\
		S &\-> AC \mid DB\\
		A &\-> aAb \mid \epsilon & D &\->aD \mid \epsilon\\
		C &\->cC \mid \epsilon & B &\-> bBc \mid \epsilon \quad[\text{für $L$ gibt es keine eindeutige \ac{CFG}}]
	\end{align*}
	Werte der Form $a^nb^nc^n$ haben zwei Ableitungen $\curvearrowright$ Grammatik ist nicht eindeutig.
\end{Bsp}

\subsection{Die Chomsky Normalform für \ac*{CFG}}
Notw. für \ac{PL} + \nameref{satz:wortproblem}.
\begin{Def}[name={[\acs*{CFG} in \acs*{CNF}]}]
	Eine \ac{CFG} ist in \ac{CNF}, falls jede Produktion die Form $A\->a$ oder $A\->BC$ hat, wobei $A,B,C\in N$, $a\in\Sigma$.
\end{Def}
\begin{Beobachtung}
	$\mathcal{G}$ in \ac{CNF} $\curvearrowright \epsilon \notin L(\mathcal{G})$
\end{Beobachtung}
	
\paragraph*{Transformation} einer Grammatik $\mathcal{G}$ mit $\epsilon\notin L(\mathcal{G})$ nach \ac{CNF}.

\paragraph*{1. Schritt:} Separierte Grammatik\\
d.h. jede Regel hat die Form
\begin{alignat*}{2}
	A&\-> A_1\dots A_n &\qquad A_i&\in N,n\geq 0\\
	\text{oder}\quad A &\-> a & a&\in\Sigma
\end{alignat*}
\uline{Verfahren:}
\begin{itemize}
\item Erweitere $N$ um neue \acs{NT} $\{Y_a \mid a\in\Sigma\}$
\item Zusätzliche neue Regeln $Y_a\-> a$
\item Ersetze in den "`alten"' Regeln alle Terminale $a$ durch $Y_a$
\item[$\curvearrowright$] Grammatik separiert, Sprache ist unverändert.
\end{itemize}

\paragraph*{2. Schritt:} Eliminiere alle Regeln der Form $A\->\epsilon$ ($\epsilon$-Produktion)\\
Ziel: $\epsilon$-freie Grammatik.\\
Gesucht: $M=\{ A \mid A \xRightarrow{*}\epsilon \} \subseteq N$
\begin{alignat*}{2}
    \text{Def.:}&\quad& M_0 &= \{ A \mid A\-> \epsilon \}\\
    &\forall i\in\N& M_{i+1} &= M_i\cup \{ A \mid A\->\alpha, \alpha \in M_i^* \}\\
    \text{Es gilt }&\forall i\in\N& M_i &\subseteq N \text{ endlich}\\
    && \curvearrowright\quad \exists n\in\N &: M_n = M_{n+1} = \bigcup_{i\in\N} M_i\\[.5em]
    \text{Beh.:}&& M&=\bigcup\limits_{i\in\N} M_i\\
    \forall i\in\N :&& M_i &\subseteq M\\
    i=0 :&& \quad M_0 &= \{ A \mid A\-> \epsilon \in P \} \subseteq M\\
    i>0 :&& M_{i+1} &= M_i\cup \{ A \mid A\-> \alpha,\alpha\in M_i^* \}
\end{alignat*}
\begin{alignat*}{2}
    &\text{Falls}\quad& A &\->A_1\dots A_n\in P,\ A_j\in M_i\\
    &\text{dann} & A &\=> A_1\dots A_n\\
    &&&\xrightarrow{\text{I.V.}} A_2\dots A_n\\
    &&&\ \vdots\\
    &&&\xrightarrow{\text{I.V.}} A_n\\
    &&&\xrightarrow{\text{I.V.}} \epsilon\\
    &\curvearrowright & A &\in M\\
    &\-> & \bigcup_{i\in\N} M_i &\subseteq M
\end{alignat*}
Zeige noch $M\subseteq \bigcup\limits_{i\in\N} M_i$

Sei $A\in M : A\xRightarrow{*} \epsilon$ mit Ableitungsbaum der Höhe $h+1$, dann: $A\in M_h$

\uline{h=0:} Ableitungsbaum \quad \tikz[baseline=(a.base)]{\Tree [.\node (a) {$A$}; $\epsilon$ ]} \quad $A\->\epsilon \curvearrowright A\in M_0$

\uline{h>0:}
\tikz[baseline=(a.base)]{
    \Tree [.\node (a) {$A$}; [.$A_1$ \edge[roof]; {$\epsilon$} ]
                             [.$A_2$ \edge[roof]; {$\epsilon$} ]
                             [.$\dots$ ]
                             [.$A_n$ \edge[roof]; {$\epsilon$} ]
          ]
}

so dass $A_j \=>^* \epsilon$ mit Ableitungsbaum der Höhe $<h+1$

Nach I.V. $A_j\in M_{h-1}$ und $A \-> A_1\dots A_n \in P$, so dass $ A \in M_h$.


%
\datenote{11.12.15}
%
Transformation im \ac{CNF} (Fortsetzung)
\begin{enumerate}
\item Schritt: Separierte Grammatik: $\A\->A_1\dots A_n$ oder $A\-> a\ ,\ A_i\in N$
\item Schritt: $\epsilon$-freie Grammatik, bereits bestimmt:
	\[ M=\{A \mid A\=> \epsilon \} \]
	inkl. Algorithmus dazu: berechne $M_i$ f"ur $i=0, 1, \dots$ bis keine neuen NT hinzukommen. 
	
	Anpassen der Produktionen
	\begin{enumerate}
		\item\label{itm:Prod-b} Falls Regel $A\-> A_1\dots A_n\in P$ und $\exists j:A_j\in M$, dann füge neue Regel\\
			$A\->A_1\dots A_{j-1} A_{j+1}\dots A_n$ zu $P$ hinzu.
		\item Wiederhole \nameref{itm:Prod-b} bis keine neuen Regeln erzeugt werden können.
		\item Entferne alle $\epsilon$-Regeln.
	\end{enumerate}
	Ergebnis: Grammatik, die $\epsilon$-frei ist und die gleiche Sprache erzeugt (o.B.).

\item Schritt: Beseitige Kettenregeln der Form $A\-> B$
	\begin{itemize}
		\item Betrachte den gerichteten Graphen mit Knotenmenge $N$ und den Kettenregeln als Kanten.
		\item Suche Zyklus mit Tiefensuche $A_1\->A_2\->\dots\->A_r\->A_i$. Dann ersetzt Vorkommen von $A_j\ (j>1)$ durch $A_1$ (auf linker und rechter Seite aller Produktionen).
		\item Wiederhole bis alle Zyklen eliminiert.
		\item Betrachte topologische Sortierung des verbleibenden \acsu{DAG}: $B_1\dots B_m$, so dass $B_m$ keine Kettenregel besitzt.
		\item Starte mit $B_m$ mit Produktion $B_m\->\alpha_i \mid \dots \mid \alpha_k$\\
			Ersetze alle Vorkommen von $B_m$ auf der rechten Seite von Kettenproduktionen durch $\alpha_1 \mid \dots \mid \alpha_k$
		\item Wiederhole f"ur $B_{m+1}\dots B_1$\\
			$\curvearrowright$ alle Kettenproduktionen eliminiert.
	\end{itemize}
\item Schritt: jetzt haben alle Produktionen die Form $A\-> A_1\dots A_n$, $n\geq 2$ oder $A\-> a$.
	\begin{itemize}
		\item Falls $A\-> A_1 A_2\dots A_n \in P$ mit $n>2$ dann ersetze durch zwei neue Produktionen
		\begin{align*}
			A &\-> A_1 B & \text{mit $B$ neues \acs{NT}}\\
			B &\-> A_2\dots A_n 
		\end{align*}
		\item Wdhl. bis alle rechten Seiten eine L"ange $\le2$ haben.
	\end{itemize}
	$\curvearrowright$ \ac{CNF} erreicht.
\end{enumerate}
\begin{Bemerkung} Sei $|\mathcal{G}|=\sum\limits_{A\->\alpha\in P}(|\alpha|+1)$ die Gr"o"se einer CFG.\\
Die Transformation nach \ac{CNF} benötigt Zeit $O(|\mathcal{G}|^2)$. Die Größe der \ac{CNF}-Grammatik ist $O(|\mathcal{G}|^2)$.
\end{Bemerkung}

\subsection{Pumping Lemma für \acs*{CFL}}
\begin{Satz}[Pumping lemma für \acs*{CFL}, uvwxy Lemma]
\label{satz:PL für CFL}
%\rlnote{Satz \# 4.2?}
	Sei $L\in {CFL}$. Dann $\exists n>0$, so dass $\forall z\in L$ mit $|z|\geq n\ \exists u,v,w,x,y:$ mit
	\begin{itemize}
	\item $z=uvwxy$
	\item $|vwx|\leq n$
	\item $|vx|\geq 1$
	\item $\forall i \in \N : uv^iwx^iy\in L$
	\end{itemize}
\end{Satz}
\begin{proof}
	Sei $\mathcal{G}= (N,\Sigma,P,S)$ in \ac{CNF} mit
    $L(\mathcal{G}) = L\setminus\{\epsilon\}$.
    
	Sei $k = |N|$ und wähle $n=2^k$
	
	Betrachte den Ableitungsbaum $B$ von $z$ mit $|z|\geq n$.
	\begin{itemize}[label=$\curvearrowright$]
		\item $B$ ist (im wesentlichen) ein Binärbaum mit $|z|\geq n = 2^k$ Blättern.
		\item in einem solchen Bin"arbaum $B$ $\exists$ Pfad  der Länge $\geq k$.
	\end{itemize}
	Auf diesem Pfad liegen $\geq k+1$ \acfp{NT}\\
	Also: mindestens ein \ac{NT} $A$ muss mehrmals auf dem Pfad vorkommen. Suche so ein $A$ beginnend vom Blatt dieses Pfads, dann ist das zweite Vorkommen von $A\leq k$ Schritte vom Blatt entfernt.
	
	Aufgrund der Wahl von $A$ hat der Ableitungsbaum für $A \=>^* vAx \xRightarrow{*} vwx$ Höhe $\leq k$.
	\begin{itemize}[label=$\curvearrowright$]
		\item hat $\leq 2^k=n$ Blätter
		\item $|vwx|\leq 2^k =n$
	\end{itemize}
	Es gilt $|vx|\geq 1$, weil
	\begin{itemize}
		\item Ableitungsbaum ist Binärbaum, mit inneren Knoten $A \-> BC$
		\item Pfad belegt nur eine Abzweigung
		\item Wegen \ac{CNF} $\not\exists C, C\xRightarrow{*} \epsilon$
	\end{itemize}
		\begin{figure}[H]\centering
		\begin{subfigure}[b]{.29\linewidth}\centering
			\begin{tikzpicture}[node distance=.75cm, on grid,
					every node/.style={
						execute at begin node=$,
						execute at end node=$
					}
				]
				\node (0) {};
				\node (A1) [below=of 0] {A};
				\node (A2) [below=of A1] {A};
				\node (A3) [below=of A2] {A};
				
				\newlength\Offset \setlength\Offset{.75cm}
				\coordinate(p1) at ($(A2.south) - (0,\Offset)$);
				%
				\coordinate (A2l) at ($(p1) - (\Offset,0)$);
				\coordinate (A1l) at ($(A2l) - (\Offset,0)$);
				\coordinate (0l) at ($(A1l) - (\Offset,0)$);
				%
				\coordinate (A2r) at ($(p1) + (\Offset,0)$);
				\coordinate (A1r) at ($(A2r) + (\Offset,0)$);
				\coordinate (0r) at ($(A1r) + (\Offset,0)$) ;
				
				\coordinate (A3l) at ($(A3.south) - (\Offset,\Offset)$);
				\coordinate (A2l2) at ($(A3l) - (\Offset,0)$);
				%
				\coordinate (A3r) at ($(A3.south) + (\Offset,-\Offset)$);
				\coordinate (A2r2) at ($(A3r) + (\Offset,0)$);
				
				\node (dots) [below=\Offset of A3] {\vdots};
				
				\node (A4) [below=\Offset of dots] {A};
				\coordinate (A4l) at ($(A3l) - (0,2*\Offset)$);
				\coordinate (A4r) at ($(A3r) - (0,2*\Offset)$);
				
				\draw (0.south) edge (0l.center) edge (0r.center)
					(A1.south) edge (A1l.center) edge (A1r.center)
					(A2.south) edge (A2l2.center) edge (A2r2.center)
					(A3.south) edge (A3l.center) edge (A3r.center)
					(A4.south) edge (A4l.center) edge (A4r.center)
				;
				\draw (0l.center) edge node[below] {u} (A1l.center)
					(A1l.center)  edge node[below] {v} (A2l.center)
					(A2r.center)  edge node[below] {x} (A1r.center)
					(A1r.center)  edge node[below] {y} (0r.center)
					(A2l2.center) edge node[below] {v} (A3l.center)
					(A3r.center)  edge node[below] {x} (A2r2.center)
					(A4l.center)  edge node[below] {w} (A4r.center)
				;
			\end{tikzpicture}
			\caption{$uv^iwx^iy\in L$}
		\end{subfigure}
		\begin{subfigure}[b]{.28\linewidth}\centering
			\begin{tikzpicture}[node distance=.5cm, on grid,
					every node/.style={
						execute at begin node=$,
						execute at end node=$
					},
					widebox/.style={draw, minimum width=.75cm, minimum height=.35cm, inner sep=0pt}
				]
				\node (S) {S};
				\node[inner sep=2pt] (A) [below=of S.south, xshift=.2cm] {A};
				\coordinate (Ap) at (A.south west);
				\node[widebox] (w) [below=of Ap] {w};
				\node[widebox] (u) at ($(Ap)!2!(w.north west)+.5*(-.75,-.3)$) {u};
				\node[widebox] (y) at ($(Ap)!2!(w.north east)+.5*(.75,-.3)$) {y};
				
				\draw (S.south) edge (u.north west) edge (y.north east)
					(Ap) edge (u.north east) edge (y.north west) edge (w.north)
					($(S.south) - (.25,.6)$) edge (S.south) edge (Ap)
				;
			\end{tikzpicture}
			\caption{$\curvearrowright uwy\in L$}
		\end{subfigure}
		\begin{subfigure}[b]{.33\linewidth}\centering
			\begin{tikzpicture}[>=stealth,
				widebox/.style={draw, minimum width=.75cm, minimum height=.35cm, inner sep=0pt}
				,dot/.style={inner sep=0pt,outer sep=0pt,label={center:\scalebox{.75}{\textbullet}}}
				]
				
				\node[dot,label={above right:$S$}] (v1) at (0,-1) {};
				\node[dot] (v2) at (-0.25,-1.6) {};
				\node[dot,label={above right:$A$}] (v3) at (0,-2) {};
				\node[dot] (v4) at (-0.5,-2.5) {};
				\node[dot,label={above right:$A$}] (v5) at (0,-3) {};
				\node[widebox] (v6) at (-1.5,-3.5) {$u$};
				\node[widebox] (v7) at (-.75,-3.5) {$v$};
				\node[widebox] (v8) at (0,-3.5) {$w$};
				\node[widebox] (v9) at (.75,-3.5) {$x$};
				\node[widebox] (v10) at (1.5,-3.5) {$y$};
				
				\draw  (v1) edge (v2);
				\draw  (v2) edge (v3);
				\draw  (v3) edge (v4);
				\draw  (v4) edge (v7.north west);
				\draw  (v4) edge (v5);
				\draw  (v3) edge (v10.north west);
				\draw  (v5) edge (v8.north west);
				\draw  (v5) edge (v8.north east);
				\draw  (v1) edge (v6.north west);
				\draw  (v1) edge (v10.north east);
				\node[align=left, text height=3em,inner sep=2pt] at (2.1,-1.5) {$A\rightarrow BC$\\[-3pt]\small{ist Binärbaum}} edge[->,shorten >=.1cm] (v3);
				\node[inner sep=0pt] at (2.75,-3.5) {$A\rightarrow a$} edge[->] (v10);
				\node (v11) at (0,-4) {$z$};
				\draw[semithick]
				let \p1 = (v6.west), \p2 = (v11), \p3 = (v10.east) in 
				 (\x1,\y2) edge[{Bar[]<}-] (v11) (v11) edge[-{>Bar[]}] (\x3,\y2);
			\end{tikzpicture}
			\caption{$\exists$ Pfad mit Länge $\geq k$}
		\end{subfigure}
		\caption{Schema zu \autoref{satz:PL für CFL}}
	\end{figure}\vspace{-2em}\qedhere
\end{proof}

\begin{lemma} %\rlnote{Lemma \# 4.3?}
	$\mathcal{L}_2 \subsetneq \mathcal{L}_1$
\end{lemma}
\begin{proof}
	Sei $L=\{L=\{a^nb^nc^n \mid n\geq 1\}$.\\
	$L$ ist nicht kontextfrei. Verwende \ac{PL}. Angenommen $L\in {CFL}$.\\
	Sei $n$ die Konstante aus dem \ac{PL}.
	
	Wähle $z=a^nb^nc^n$
	\begin{align*}
		\text{Also: } \exists &u,v,w,x,y : z = uvwxy\\
		& |vwx| \leq n
	\end{align*}
	$\curvearrowright vwx$  kann nicht gleichzeitig $a,b$ und $c$ enthalten.\\
	Angenommen $vwx$ enthält kein $c$. Dann muss $uwy \in L$
	\begin{itemize}
		\item $y$ endet mit $c^n$
		\item $|vx|\geq 1$, also $|uwy|+1\leq |z|$ also "`fehlt"' mindestens ein $a$ oder $b$
	\end{itemize}
	$\curvearrowright uvw \notin L$
\end{proof}

\subsection{Entscheidungsprobleme für \acs*{CFL}}
\begin{Satz}[name={[Wortproblem für \acs*{CFL} entscheidbar]}]
	Das Wortproblem "`$w\in L?$"' ist für \ac{CFL} entscheidbar. Falls $|w|=n$, benötigt der Algorithmus $O(n^3)$ Schritte und $O(n^2)$ Platz.
\end{Satz}
\begin{proof}
	Algorithmus \ac{CYK}.
\end{proof}
\begin{Bsp}
	$L=\{a^nb^nc^m \mid n,m\geq 1\}$ mit Grammatik (\acs{CFG})
	\begin{align*}
		S &\-> XY\\
		X &\-> ab \mid aXb\\
		Y &\-> c \mid cY\\
		\shortintertext{Umformen in \ac{CNF}}
		S &\-> XY & A &\->a\\
		X &\-> AB \mid AZ & B&\->b\\
		Y &\->c \mid CY & C &\->c\\
		Z &\-> XB
	\end{align*}
\end{Bsp}

\datenote{18.12.15}
	$\begin{aligned}[t]
		S &\-> XY\\
		X &\-> AB\\
		X &\-> AZ\\
		Z &\-> XB\\
		Y &\-> c\\
		Y &\-> CY\\
		A &\-> a\\
		B &\-> b\\
		C &\-> c
	\end{aligned}$\quad
\begin{proof}
		\ac{CYK}-Algorithmus
		\begin{description}
	    \item[Eingabe:]
		\begin{itemize}
			\item \ac{CFG} $\mathcal{G}$ in \ac{CNF}
			\item $w = a_1\dots a_n\in\Sigma^*, |w|=n$
		\end{itemize}
		\item[Ausgabe:] "`$w\in L(\mathcal{G})$"'
		\item[Idee:] Berechne eine $(n\x n)$ Matrix $M$ mit Einträgen in $\mathcal{P}(N)$ mit folgender Spezifikation:
		\end{description}
	\begin{align*}
		M_{ij} &= \{ A \mid A\xRightarrow{*} a_i\dots a_j \} && 1\leq i\leq j\leq n \quad\text{nur diese }M_{ij}\neq \varnothing\\
		& \text{falls $i=j$:}\\
		M_{ii} &= \{ A \mid A\xRightarrow{*} a_i\}\\
		&= \{A \mid A\-> a_i \} \\
		&\text{falls }1\leq i<j\leq n:\\
		M_{ij} &= \{ A \mid A\xRightarrow{*} a_i\dots a_j \}\\
		&= \{ A \mid A\=> BC \xRightarrow{*} a_i\dots a_j \}\\
		&= \{ A \mid A\-> BC \land BC \xRightarrow{*} a_i\dots a_j \}\\
		&= \{ A \mid A\-> BC \land \exists k: i\leq k<j\quad 
			\begin{aligned}[t]
				B &\xRightarrow{*} a_i\dots a_k \land{}\\
				C &\xRightarrow{*} a_{k+1}\dots a_j \}
			\end{aligned}\\
		&= \bigcup_{k=i}^{j-1} \{ A \mid A \-> BC \land 
			\begin{aligned}[t]
				B &\xRightarrow{*} a_i\dots a_k \land{}\\
				C &\xRightarrow{*} a_{k+1}\dots a_j \}
			\end{aligned}\\
		&= \bigcup_{k=i}^{j-1} \{ A \mid A \-> BC \land B \in M_{i,k} \land C \in M_{k+1,j} \}
	\end{align*}
	Damit: $w\in L$ genau dann, wenn $S \=>^* w$ genau dann, wenn $S \in M_{1,n}$.
	
	\begin{table}[H]\centering
		\caption[$w=aaa\ bbb\ cc$]{$w=aaa\ bbb\ cc$ \protect\footnotemark}
		\begin{tabular}[t]{M{c}|*8{M{c}|}}
		\cline{2-9}
			M = & A               & \bullet & \bullet & \bullet & \bullet & \color{Green}X & \coloruline{Green}{S} & S       \\
		\cline{2-9}
			\multicolumn{2}{c|}{} & \color{Blue}A       & \bullet & \bullet & \color{Red}\coloruline{Blue}{X} & \coloruline{Red}{Z} & \bullet & \bullet \\
		\cline{3-9}
			     \multicolumn{3}{c|}{}      & A       & X       & \color{Blue}Z       & \bullet & \bullet & \bullet \\
		\cline{4-9}
			          \multicolumn{4}{c|}{}           & B       & \bullet & \bullet & \bullet & \bullet \\
		\cline{5-9}
			               \multicolumn{5}{c|}{}                & B       & \bullet & \bullet & \bullet \\
		\cline{6-9}
			                    \multicolumn{6}{c|}{}                     & \color{Red}B & \bullet & \bullet \\
		\cline{7-9}
			                         \multicolumn{7}{c|}{}                          & C,\color{Green}Y     & Y       \\
		\cline{8-9}
			                              \multicolumn{8}{c|}{}                               & C,Y     \\
		\cline{9-9}
		\end{tabular} $M_{1n}$
	\end{table}\footnotetext{Zur Veranschaulichung: das Unterstrichene wird aus den Elementen der entsprechenden Farbe gebildet.}
\end{proof}

$\acs{CYK}(\mathcal{G},a_1,\dots,a_n)$\\
$M\ n\x n$ Matrix mit $M_{ij}=\varnothing$
\begin{lstlisting}[mathescape,morekeywords={for,do,return},morecomment={[l]{//}}]
  for i=1 .. n do  // $O(|\mathcal{G}|)\cdot O(n)$
    $M_{ii}=\{A \mid A \-> a_i \}$
  for i=n-1 ..  1 do
    for j=i+1 .. n do
      for k=i .. j-1 do  // $O(|\mathcal{G}|)\cdot O(n^3)$
        $M_{ij}=M_{ij}\cup \{ A \mid A \-> BC, B\in M_{ik}, C\in M_{k+1,j} \}$
  return $S\in M_{1n}$
\end{lstlisting}

\begin{Satz}[name={[Entscheidbarkeit des Leerheitsproblems für \acs*{CFL}]}] % 4.7
    Das Leerheitsproblem ist für \ac{CFL} entscheidbar.
\end{Satz}

\begin{proof}
    Sei $\mathcal{G} = (N, \Sigma, P, S)$ eine CFG für $L$.
    Gefragt ist, ob $L(\mathcal{G}) = \{ w\in\Sigma^* \mid S\overset{*}{\=>} w \} \overset?= \varnothing
$. 
    Betrachte dazu die Menge $M$ der nützlichen Nichtterminalsymbole, aus denen ein Terminalwort herleitbar ist.
	\begin{align*}
		M &= \{ A \mid A \overset{*}{\=>} w, w\in \Sigma^* \}\\
		M_0 &= \{ A \mid A \-> w\in P, w\in \Sigma^* \}\\
		M_{i+1} &= M_i\cup \{ A \mid A \-> \alpha\in P, \alpha\in(\Sigma\cup M_i)^* \}\\
		\exists n : M_n &= M_{n+1} \overset!= M\\
		L =\varnothing &\<=> S\notin M \qedhere
	\end{align*}
	Offenbar ist $M_0 \subseteq M$ eine Approximation von $M$, $M \supseteq M_{i+1} \supseteq M_i$ verbessert $M_i$ und das jeweils nächste $M_i$ ist in Linearzeit berechenbar. Da $M \subseteq N$ endlich ist, muss es ein $n$ geben, sodass $M_n = M_{n+1}$. Für dieses $n$ kann man zeigen, dass $M = M_n$. 
\end{proof}
\begin{Bem}
	$M$ ist die Menge der nützlichen Nichterminale. Nicht nützliche Nichtterminale können entfernt werden, ohne dass $L(\mathcal{G})$ sich ändert.
\end{Bem}
\begin{Satz}[name={[Entscheidbarkeit des Endlichkeitsproblem für \acs*{CFL}]}]
	Das Endlichkeitsproblem für \ac{CFL} ist entscheidbar.
\end{Satz}
\begin{proof}
	Mit \ac{PL} analog zum Endlichkeitsproblem für reguläre Sprachen.
\end{proof}

\subsection{Abschlusseingenschaften für \acs*{CFL}}


\begin{Satz} % 4.7
	Die Menge \acs{CFL} ist abgeschlossen unter $\cup, \cdot, ^*$, jedoch \underline{nicht} unter $\cap, \overline{\phantom{A}}$.
\end{Satz}
\begin{proof}
	\begin{align*}
		\mathcal{G}_i :&= (N_i, \Sigma,P_i,S_i) \quad i=1,2\\
		\text{"`}\cup\text{"'}: N &= N_1\dotcup N_2\dotcup\{S\}\\
		P &= \{S\->S_1, S\->S_2 \} \cup P_1\cup P_2\\
		\text{"`}\cdot\text{"'}:: N &= N_1\dotcup N_2\dotcup\{S\}\\
		P &= \{ S\->S_1S_2 \} \cup P_1\cup P_2\\
		\text{"`}^*\text{"'}: N &= N_1 \dotcup \{S\}\\
		P &= \{ S\->\epsilon, S\-> S_1S \} \dotcup P_1
	\end{align*}
	\begin{itemize}
	\item für $n\geq 1$
		\[ \underbrace{\{a^nb^nc^n\}}_{\notin \acs{CFL}} = \underbrace{\{a^nb^nc^m \mid n,m\geq 1 \}}_{\in \acs{CFL}} \cap \underbrace{\{a^mb^nc^n \mid m,n\geq 1 \}}_{\in \acs{CFL}} \]
		Also \ac{CFL} nicht abgeschlossen unter $\cap$.
	\item Angenommen \ac{CFG} abgeschlossen unter $\overline{\phantom{X}}$\\
		Falls $L_1,L_2\in \acs*{CFL}$, dann ist $\overline{L}_1,\overline{L}_2\in\acs*{CFL}$ nach Annahme.\\
		$\curvearrowright \overline{L}_1\cup \overline{L}_2\in\acs*{CFL}$ wegen Teil "'$\cup$"'.\\
		$\curvearrowright \overline{\overline{L}_1\cup \overline{L}_2} = L_1\cap L_2\in\acs*{CFL}\ \lightning$ zu Teil "'$\cap$"'. \qedhere
	\end{itemize}
\end{proof}

\begin{Satz} % 4.8
	Die Menge \ac{CFG} ist abgeschlossen unter $\cap$ mit reg. Sprachen. "`$\acs*{CFL} \cap \text{REG} = \acs*{CFL}$"'.
\end{Satz}
\begin{proof}
	\begin{align*}
			\text{Sei }L &= L(\mathcal{G})\quad\acs{CFL}\\
			R &= L(M)\quad\acs{REG}\\
			\mathcal{G} &= (N,\Sigma,P,S)\\
			M &= (Q,\Sigma,\delta,q_0,F)\quad\acs{DFA}
	\end{align*}
	Zeige $L\cap R$ \acs{CFL}\\
	Konstruiere \ac{CFG} für $L\cap R$\\
	Ang. $\mathcal{G}$ ist in \ac{CNF}
	\begin{alignat*}{2}
		A &\-> a &\quad& A \-> BC\\
		\tikz[baseline]{\Tree [.$qAq'$ $a$ ]}
			&= \delta(q,a) &&\qquad \mathclap{%
				\tikz[baseline]{\Tree [.$q_1Aq_3$ $q_1Bq_2$ $q_2Cq_3$ ]}
			}\\
		N' &= Q\x N\x Q\cup \{S'\}\\
		S' &\-> (q_0,S,q')\ && \forall q'\in F\\
		(q,A,q') &\-> a && \text{falls } \delta(q,a) = q'\text{ und }A\-> a\in P\\
		(q_1, A, q_3) &\-> (q_1,B,q_2)(q_2,C,q_3) &&\text{falls } A\-> BC\in P \forall q_1,q_2,q_3\in Q
	\end{alignat*}
	Zeige $(p,A,q)\overset*{\=>} w \<=> \exists$ Lauf $p\dots q$ von $M$ auf $w$ und $A \Rightarrow^* w$\\
	per Induktion über Höhe $h$ des Ableitungsbaums:
	\begin{itemize}[labelwidth=\widthof{$h=1:$},leftmargin=!]
	\item[$h=1:$] $(p,A,q) \-> a\ \exists$ Lauf denn $\delta(p,a)=q$; offenbar $A\Rightarrow a$
	\item[$h>1:$] $(p,A,q) \-> (p,\underset{\Downarrow*}{B},r)(r,\underset{\Downarrow*}{C},q)$\\
	\hspace{-2em}mit $w\phantom{A}\,=\phantom{(p,\,} w_1 \phantom{,r)(r,\ }w_2$
	\end{itemize}
	und Höhen $<h:$\\
	Nach IV $\exists$ Lauf $p\dots r$ auf $w_1$ und $B \Rightarrow^* w_1$\\
	\phantom{Nach IV }$\exists$ Lauf $r\dots q$ auf $w_2$ und $C \Rightarrow^* w_2$\\
	$\curvearrowright\ \exists$ Lauf $p\dots r\dots q$ auf $w_1 w_2=w$ und $A \Rightarrow BC \Rightarrow^* w$
	
	Nun gilt 
	\begin{align*}
	    w \in L(\mathcal{G}') & \<=> S \=>^* w \\
	    & \<=> \exists q'\in F: (q_0, S, q') \=>^* w \\
	    & \<=> \exists q'\in F: \exists \text{ Lauf von $q_0$ nach $q'$ auf $w$} \land S \=>^* w \\
	    & \<=> w \in R = L(M) \land w \in L = L(\mathcal{G}) \\
	    & \<=> w \in R \cap L
	\end{align*}
\end{proof}
%\rlerror{Vorlesung 18.12.15 unvollständig (Aufschrieb vorhanden)}
%
\datenote{21.12.15}
\vspace{-.5em}
%
%Zuletzt: $\acsu{CFL}\land\acsu{REG}=\ac{REG}$
\begin{Satz}[name={[$L\subseteq R$ entscheidbar]}] %\rlwarning{Satz 4.9}
	Falls $L\in\ac{CFL}$ und $R\in\textrm{REG}$, dann ist "`$L\subseteq R$?"' entscheidbar.
\end{Satz}
\begin{proof}
	$L\subseteq R\curvearrowleftright \underbrace{L \cap\overline{R}}_{\ac{CFL}} = \varnothing$ entscheidbar.
\end{proof}