\documentclass[12pt]{article}

\usepackage{ngerman,a4}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}
\usepackage{graphicx}

\thispagestyle{empty}

\title{Theoretische Informatik - Übungsblatt 6}
\author{Jan Hendrik Dithmar - Matrikelnummer 2031259 \\
				Dirk Heine - Matrikelnummer 2030941 \\
		Di, 9-11 Uhr, Andreas Augustin \\
	}
\date{}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetC}{\ensuremath{\mathbb{C}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\bild}[4]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[width=#1cm]{#2}\\[0.2cm]
			\caption{#3}
			\label{#4}
	\end{figure}
	}

\maketitle

\newpage

\section*{Aufgabe 1}
Bearbeitet von {\bfseries Dirk Heine} \\[0.5cm]
Idee: \\
Die Aussage ist korrekt. Man nehme eine beliebige DKA-Sprache für $\{a,b\}$, die nicht regulär ist. Schneidet man diese mit
$\{a|b\}^*$ bekommt man die Originalsprache, die offenbar DKA-Sprache ist. \\[0.3cm]
Es gilt:
$$L \cap R = \overline{\overline{L} \cup \overline{R}} \quad (1)$$
Es gilt weiter: \\
DKA-Sprachen sind unter Komplementbildung abgeschlossen. Also
$$L \text{ DKA-Sprache} \Rightarrow \overline{L} \text{ DKA-Sprache} \quad (2)$$
$L$ DKA-Sprache $\stackrel{(2)}{\Rightarrow} \overline{L}$ DKA-Sprache, $R$ reguläre Sprache $\Rightarrow \overline{R}$ reguläre Sprache.
$$\Rightarrow \overline{L} \cup \overline{R} \text{ DKA-Sprache (laut Vorlesung)}$$
$$\stackrel{(2)}{\Rightarrow} \overline{\overline{L} \cup \overline{R}} = L \cap R \text{ DKA-Sprache}$$
Automat: \\
Nehme einen DKA für $L$ und einen DEA für $R$. Lasse $L$ und $R$ parallel laufen. Das Wort wird dann akzeptiert, wenn $L$ und $R$ nicht akzeptieren.



\newpage

\section*{Aufgabe 2}
Bearbeitet von {\bfseries Jan Hendrik Dithmar} \\[0.5cm]
$G=(V,T,P,S), V=\{S,A,B\}, T=\{a,b\}$
\begin{eqnarray*}
	P & = & \{ S \to \varepsilon, \quad \; \; (1) \\
	& & S \to AB, \quad (2) \\
	& & S \to BA, \quad (3) \\
	& & A \to aS, \quad \; (4) \\
	& & A \to SA, \quad (5) \\
	& & B \to bS, \quad \; (6) \\
	& & B \to SB, \quad (7)\}
\end{eqnarray*}

\subsubsection*{(a)}
\begin{eqnarray*}
	S & \stackrel{(2)}{\rightarrow} & AB \\
	& \stackrel{(4)}{\rightarrow} & aSB \\
	& \stackrel{(3)}{\rightarrow} & aBAB \\
	& \stackrel{(6)}{\rightarrow} & abSAB \\
	& \stackrel{(1)}{\rightarrow} & abAB \\
	& \stackrel{(4)}{\rightarrow} & abaSB \\
	& \stackrel{(1)}{\rightarrow} & abaB \\
	& \stackrel{(6)}{\rightarrow} & ababS \\
	& \stackrel{(1)}{\rightarrow} & abab
\end{eqnarray*}

\begin{eqnarray*}
	S & \stackrel{(3)}{\rightarrow} & BA \\
	& \stackrel{(6)}{\rightarrow} & bSA \\
	& \stackrel{(3)}{\rightarrow} & bBAA \\
	& \stackrel{(6)}{\rightarrow} & bbSAA \\
	& \stackrel{(1)}{\rightarrow} & bbAA \\
	& \stackrel{(4)}{\rightarrow} & bbaSA \\
	& \stackrel{(1)}{\rightarrow} & bbaA \\
	& \stackrel{(4)}{\rightarrow} & bbaaS \\
	& \stackrel{(1)}{\rightarrow} & bbaa
\end{eqnarray*}

\begin{eqnarray*}
	S & \stackrel{(2)}{\rightarrow} & AB \\
	& \stackrel{(5)}{\rightarrow} & SAB \\
	& \stackrel{(3)}{\rightarrow} & BAAB \\
	& \stackrel{(6)}{\rightarrow} & bSAAB \\
	& \stackrel{(1)}{\rightarrow} & bAAB \\
	& \stackrel{(4)}{\rightarrow} & baSAB \\
	& \stackrel{(1)}{\rightarrow} & baAB \\
	& \stackrel{(4)}{\rightarrow} & baaSB \\
	& \stackrel{(1)}{\rightarrow} & baaB \\
	& \stackrel{(6)}{\rightarrow} & baabS \\
	& \stackrel{(1)}{\rightarrow} & baab
\end{eqnarray*}

\subsubsection*{(b)}
$$L(G) = \{w \in \{a,b\}^* \; | \; \#_a(w) = \#_b(w)\}$$
Beweis: \\
Die Ableitungen $S \to AB$ und $S \to BA$ implizieren letztendlich, dass in dem Wort mindestens ein $a$ und ein $b$ vorkommen müssen (vgl. Ableitungen $A \to aS$ und $B \to bS$). Wie das $S$ in den Ableitungen $A \to aS$, $A \to SA$, $B \to bS$ und $B \to SB$ weitergeführt wird, spielt keine Rolle, da man irgendwann die Ableitung $A \to aS$ oder $B \to bS$ anwenden muss. \\
Da die Ableitungen $S \to AB$ und $S \to BA$ zur Folge haben, dass immer ein $a$ und ein $b$ im Teilwort ist, haben wir gleiche Anzahl $a$'s und $b$'s im Wort. \\
Für den Fall, dass die Ableitung $S \to \varepsilon$ am Anfang angewendet wird, haben wir das leere Wort und somit auch gleiche Anzahl an $a$'s und $b$'s.

\end{document}
