\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 7}
\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{\eur}{\mbox{\euro}}
\newcommand{\bild}[4]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[width=#1cm]{#2}\\[0.2cm]
			\caption{#3}
			\label{#4}
	\end{figure}
	}

\maketitle

\newpage
\section*{Aufgabe 1}
\textbf{Spezifiktation der Maschine $_{ab}T_{ccd}$:}
\begin{align*}
	\Sigma = &\{a,b,c,d\} \\
	\Gamma = &\{a,b,c,d,\#\} \\
	Q = &\{A,B,C,D, W_a, W_b, q, q', W\} \\
	s = &q \\
	F = &\{q'\} \\
	\Delta = &\{(q,k,q,k,R), \quad \mbox{mit } k \in \{b,c,d\} \\
	& (q,a,W_a,a,R), \\
	& (W_a, b, W_b, d, L), \\
	& (W_a, k', q, k', R), \quad \mbox{mit } k' \in \{a,c,d\} \\
	& (W_b, a, W, c, L), \\
	& (W, c, C, c, L), \\
	& (W, a, A, c, L), \\
	& (W, d, D, c, L), \\
	& (W, b, B, c, L), \\
	& (X_1, x_1, X_2, x_2, L), \quad \mbox{wobei } (X_1,x_2); (X_2, x_1) \in \{(A,a); (B,b); (C,c); (D,d)\} \\
	& (X, \#, q', x, B) \quad \mbox{wobei } (X,x) \in \{(A,a); (B,b); (C,c); (D,d)\} \\
	& \}
\end{align*} \\
\textbf{Wirkungsweise:} \\
Die Maschine $_{ab}T_{ccd}$ beginnt am linken Ende des Bandes. Von hier aus macht der Lesekopf solange \glqq Rechtsbewegungen\grqq\ bis er auf ein $a$ stößt. In diesem Fall wechselt die Maschine in einen Zustand $W_a$ und prüft dann, ob der Buchstabe rechts von $a$ ein $b$ ist. Ist dies nicht der Fall, so wechselt sie wieder in den Startzustand $q$ zurück und setzt das Einlesen mit \glqq Rechtsbewegung\grqq\ fort. Tritt bis zum rechten Ende des Bandes kein $ab$ auf, so wird die Maschine im Zustand $q$ dort stecken bleiben. \\
Findet die Maschine rechts von $a$ jedoch ein $b$, so ersetzt sie dieses durch ein $d$ und geht über in eine \glqq Linksbewegung\grqq\ und einen Zustand $W_b$. Jetzt wird das gefundene $a$ durch ein $c$ ersetzt, in Zustand $W$ gewechselt und der Kopf weiter nach links bewegt. In Zustand $W$ wird der aktuelle Buchstabe eingelesen und mit Hilfe besonderer Zustände $(A,B,C,D)$ \glqq zwischengespeichert\grqq . In jedem Fall wird hier ein weiteres $c$ geschrieben, so dass jetzt die Buchstabenfolge $ccd$ komplett ist. Im Folgenden liest die Maschine in \glqq Linksbewegung\grqq\ immer einen Buchstaben ein, speichert diesen mittels $A,B,C,D$ kurzzeitig und schreibt an die Stelle den jeweils vorher zwischengespeicherten Buchstaben. Erreicht sie das linke Ende so schreibt sie den letzten zwischengespeicherten Buchstaben statt $\#$, lässt den Kopf dort stehen und wechselt in den Zustand $q'$.

\section*{Aufgabe 2}
\subsubsection*{(a)}
2NKA $M=(\Sigma, \Gamma_a, \Gamma_, \eur_a, \eur_b, Q, s, F, \Delta)$.
\begin{align*}
	\Sigma & \mbox{ Eingabealphabet} \\
	\Gamma_a & \mbox{ Kelleralphabet des ersten Kellers} \\
	\Gamma_b & \mbox{ Kelleralphabet des zweiten Kellers} \\
	\eur_a \in \Gamma_a & \mbox{ Kellerbodensymbol des ersten Kellers} \\
	\eur_b \in \Gamma_b & \mbox{ Kellerbodensymbol des zweiten Kellers} \\
	Q & \mbox{ endliche Zustandsmenge} \\
	s \in Q & \mbox{ Startzustand} \\
	F \subset Q & \mbox{ Endzustände} \\
	\Delta \subset & (Q \times \Gamma_a \times \Gamma_b \times (\Sigma \cup \{\varepsilon\}) \times \Gamma_a^* \times \Gamma_b^* \times Q)
\end{align*}
Dabei ist $Q$ der alte Zustand, $\Gamma_a$ und $\Gamma_b$ das oberste Kellersymbol des jeweiligen Kellers, $(\Sigma \cup \{\varepsilon\})$ das nächste Zeichen auf dem Eingabeband, $\Gamma_a^*$ und $\Gamma_b^*$ der neue Kellergipfel des jeweiligen Kellers und $Q$ der neue Zustand. \\[0.5cm]
\textbf{Konfigurationsraum:} \\
$$K_M = Q \times \Gamma_a^* \times \Gamma_b^* \times \Sigma^*$$
Dabei ist $Q$ der derzeitige Zustand, $\Gamma_a^*$ und $\Gamma_b^*$ der Kellerinhalt und $\Sigma^*$ der Eingaberest. \\
Startkonfiguration: $start_x = (s, \eur_a, \eur_b, x)$ mit $x \in \Sigma^*$. \\
Endkonfiguration: $Fin = \{(f, U, V, \varepsilon) | f \in F, U \in \Gamma_a^*, V \in \Gamma_b^*\}$ \\[0.5cm]
\textbf{Rechenschrittrelation:} \\
Seien $q,q' \in Q; A \in \Gamma_a; B \in \Gamma_b; X,U \in \Gamma_a^*; Y,V \in \Gamma_b^*; a \in \Sigma; u \in \Gamma^*$.
$$(q, AU, BV, au) \vdash_M (q', XU, YV, u) \Leftrightarrow (q,A,B,a,X,V,q') \in \Delta$$
$$(q, AU, BV, u) \vdash_M (q', XU, YV, u) \Leftrightarrow (q,A,B,\varepsilon,X,V,q') \in \Delta$$
$\vdash_M^*$ ist die reflexive, transitive Hülle von $\vdash_M$. \\[0.5cm]
\textbf{Akzeptanz:}
$$L(M) = \{x \in \Sigma^* | start_x \vdash_M^* \varphi \mbox{ für irgendein } \varphi \in Fin\}$$
\textbf{2NKA-Sprache:} \\
$L$ ist genau dann 2NKA-Sprache, wenn $\exists$ 2NKA $M$ mit $L=L(M)$.

\subsubsection*{(b)}
Sei $L=L_{abc} = \{a^nb^nc^n | n \in \SetN\}$. $L$ ist laut Vorlesung nicht NKA-Sprache. \\[0.5cm]
\textbf{Behauptung:} $L$ ist 2NKA-Sprache \\[0.5cm]
\textbf{Beweis durch Automaten:} \\
Sei 2NKA $M=(\Sigma, \Gamma_a, \Gamma_b, \eur_a, \eur_b, Q, s, F, \Delta)$.
\begin{align*}
	\Sigma = &\{a,b,c\} \\
	\Gamma_a = &\{A\} \\
	\Gamma_b = &\{B\} \\
	Q = &\{s,f\} \\
	F = &\{f\} \\
	\Delta = &\{(s, \eur_a, \eur_b, \varepsilon, \eur_a, \eur_b, f), \\
	& (s,\eur_a, \eur_b, a, A\eur_a, \eur_b, s), \\
	& (s, A, \eur_a, b, \varepsilon, B\eur_b, s), \\
	& (s, \eur_a, B, c, \eur_a, \varepsilon, s), \\
	& (s, A, \eur_b, a, AA, \eur_b, s), \\
	& (s, A, B, b, \varepsilon, BB, s) \\
	& \}
\end{align*}

\subsubsection*{(c)}
\textbf{Behauptung:} 2NKA-Sprachen gehören zum Typ0. \\[0.5cm]
\textbf{Beweis:} \\
Wir wissen, dass einfache TM Typ0-Sprachen akzeptieren. Es genügt hier also zu zeigen, dass 2NKA $M$ die selbe Sprache akzeptiert wie eine einfache TM. \\[0.5cm]
\textbf{Idee:} Baue 2NKA, der eine einfache TM simuliert. \\
Auf dem 2NKA-Eingabeband stehe das selbe wie auf dem eTM-Band. Im ersten Keller des 2NKA stehe immer der Inhalt links vom Lesekopf der eTM, im zweiten Keller immer der Inhalt rechts vom Lesekopf der eTM. Diese Invarianz soll immer aufrecht erhalten bleiben. \\
So findet man im ersten Keller immer die Symbole bei \glqq Linksbewegung\grqq , analog im zweiten Keller die Symbole der \glqq Rechtsbewegung\grqq . Man hat also die selben Möglichkeiten, die die einfache TM bietet.

\end{document}