\documentclass[12pt]{article}

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

\thispagestyle{empty}

\title{Theoretische Informatik (WS 2005/2006) - Übungsblatt 6}
\author{Jan Hendrik Dithmar - Matrikelnummer 2031259 \\
		Do, 11-13 Uhr, Vasileios Anastasatos
	}
\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{\R}{\ensuremath{\mathbb{R}}}
\newcommand{\N}{\ensuremath{\mathbb{N}}}
\newcommand{\C}{\ensuremath{\mathbb{C}}}
\newcommand{\Z}{\ensuremath{\mathbb{Z}}}
\newcommand{\Q}{\ensuremath{\mathbb{Q}}}
\newcommand{\B}{\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}
\subsubsection*{(a)}
\begin{itemize}
	\item $S \Longrightarrow_G a\underline{S}a \overset{S \to bSb}{\Longrightarrow_G} ab\underline{S}ba \overset{S \to aAb}{\Longrightarrow_G} aba\underline{A}bba \overset{A \to \varepsilon}{\Longrightarrow_G} ababba$
	\item $S \Longrightarrow_G a\underline{A}b \overset{A \to bA}{\Longrightarrow_G} ab\underline{A}b \overset{A \to \varepsilon}{\Longrightarrow_G} abb$
	\item $S \Longrightarrow_G b\underline{S}b \overset{S \to bAa}{\Longrightarrow_G} bb\underline{A}ab \overset{A \to \varepsilon}{\Longrightarrow_G} bbab$
\end{itemize}

\subsubsection*{(b)}
Behauptung:
$$L(G) = \{nopqn^R | n \in \{a,b\}^*, o,q \in \{a,b\}, o \neq q, p \in \{a,b\}^*\}$$
Die beschriebene Sprache $L(G)$ ist also gerade die Sprache der Nichtpalindrome. \\
Als Beweis sei eine Konstruktion angeführt: \\\\
Sei $n \in \Sigma$, vereinfacht sei $n^i \in \{a,b\}^i$.
\begin{itemize}
	\item Solange man ein $S$ im Wort hat, genügt es der Form
		$$n^iS{n^{i}}^R$$
		Beweis:
		\begin{enumerate}[--]
			\item IA: $i=0$: $S$ \quad \checkmark
			\item IV: $n^iS({n^i})^R$
			\item IB: $n^{i+1} S ({n^{i+1}})^R$
			\item IS: $n^iS({n^i})^R$
				\begin{enumerate}[(a)]
					\item $\overset{(IV)}{\to} n^i a S a ({n^i})^R = n^i a S (n^i a)^R$
					\item $\overset{(IV)}{\to} n^i b S b ({n^i})^R = n^i b S (n^i b)^R$
				\end{enumerate}
				$\Rightarrow n^{i+1} S (n^{i+1})^R$
		\end{enumerate}
	\item Das früheste produzierte Wort mit $A$ genügt dann der Form $n^i o A q (n^i)^R$ mit $o,q \in \Sigma, o \neq p$. Das folgt direkt aus $S \to aAb$ und $S \to bAa$.
	\item $A$ kann man zu $p \in \{a,b\}^*$ ableiten. Aus $A \to \ldots$ folgt: rechtslineare Teilsprache.
		Beweis:
		\begin{enumerate}[--]
			\item IA: $\varepsilon \in \{a,b\}^*$ \quad \checkmark
			\item IV: $n^iA$: Auch hier sei wieder $n^i \in \{a,b\}^i$, analog $n^{i+1}$.
			\item IB: $n^{i+1}A$
			\item IS: $A \to aA$ bzw. $A \to bA$.
		\end{enumerate}
\end{itemize}
Damit ist die Charakterisierung, die im Übrigen mit der Trivialaussage \glqq Nichtpalindrome\grqq\ äquivalent ist (Formelverständnis), korrekt. \QED

\newpage
\section*{Aufgabe 2}
Man wähle die Grammatik $G=(\Sigma, V, S, P), \Sigma=\{a,b\}, V=\{S,B\}$ und den Produktionen P
\begin{align*}
	S &\to aSB \quad | \quad b \\
	bB &\to Bbb \\
	aB &\to a
\end{align*}
Beweis, dass $L(G)=L$:
\begin{enumerate}
	\item
		\begin{enumerate}[--]
			\item IV: $b^iB \to Bb^{2i}$
			\item IB: $b^{i+1}B \to Bb^{2(i+1)}$
			\item IA: $b^1 B = bB \to Bbb = Bb^2 = Bb^{2 \cdot 1}$ \quad \checkmark
			\item IS: $b^{i+1}B = b^ibB \to b^iBbb = b^iBb^2 \overset{(IV)}{\to} Bb^{2i}b^2 = Bb^{2(i+1)}$
		\end{enumerate}
	\item
		\begin{enumerate}[--]
			\item IV: $S \in L$
			\item IB: $aSB \in L$
			\item IA: $b \in L$ \quad \checkmark, da $S \to b$
			\item IS: $aSB = aa^ia^{2^i}B = a^{i+1} b^{2^i} B \overset{1.}{\to} a^{i+1}Bb^{2(2^i)} = a^i \underline{aB} b^{2^{i+1}} \to a^i a b^{2^{i+1}} \to a^{i+1}b^{2^{i+1}} \in L$
		\end{enumerate}
\end{enumerate}
\QED

\newpage
\section*{Aufgabe 3}
\subsubsection*{(a)}
Man kann direkt aus der Grammatik $G$ einen Automaten $M_G$ konstruieren, indem man folgende Regeln anwendet: \\
Existiert ein Zustand bei Nennung noch nicht, so ist er einzuführen. Die in den Schemata verwendeten Variablen sind auch bei Zustandsbezeichnern durch den jeweils konkreten Bezeichner zu ersetzen. Gleiches gilt für Zeichen des Alphabets.
\begin{enumerate}
	\item $A \to Ba$: Man führe eine Kante von Zustand $A$ auf Zustand $B$ mit Zeichen $a$ ein. \\
		\bild{4}{a3a1}{Aufgabe 3 (a): 1.}{a3a1}
	\item $A \to Aa$: Sonderfall von 1.: Hierbei beschreibt die einzuführende Kante eine Schleife (von Zustand $A$ auf Zustand $A$ mit Zeichen $a$). \\
		\bild{2}{a3a2}{Aufgabe 3 (a): 2.}{a3a2}
	\item $A \to \varepsilon$: Man wandele $A$ in den Startzustand um. \\
		\bild{4}{a3a3}{Aufgabe 3 (a): 3.}{a3a3}
	\item $A \to a$: Man führe einen unbenannten Startknoten mit $a$-Kante auf $A$ ein. \\
		\bild{4}{a3a4}{Aufgabe 3 (a): 4.}{a3a4}
	\item $S$ ist Startsymbol: $S$ sei ein Endzustand. \\
		\bild{2}{a3a5}{Aufgabe 3 (a): 5.}{a3a5}
\end{enumerate}
Auf einen Beweis soll hier verzichtet werden. Die Umformungen für die drei unteren Fälle kann man direkt beweisen, wogegen sich bei den oberen beiden strukturelle Induktion mit z.B. dem zweiuntersten Fall als Anfang anbietet. \\
Somit ist $L(G)=L(M_G)$ und da $M_G$ ein EA und damit $L(G)$ regulär.

\subsubsection*{(b)}
Man überlegt sich, dass man die rechte Seite der Ableitungen auch \glqq rückwärts\grqq\ streichen kann, also Regeln der Form
$$A \to Ba \quad \mbox{als} \quad A \to aB$$
schreibt. Somit produziert man gerade das umgekehrte Wort zu jedem Wort der Sprache $L$. Diese Sprache $L'$ ist aber rechtslinear (was man sofort aus der Grammatik ablesen kann (Chomsky)). Nach der Vorlesung ist für $L'$ regulär auch $L'^R$ regulär. Da aber $L'=\{w | w^R \in L\}$ ist $L'^R=L$. Somit muss auch $L$ regulär sein.


\end{document}