%blatt6
\documentclass[A4,11pt]{article}

\usepackage{lmodern}
\usepackage{fullpage}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{enumerate}
\usepackage[german]{babel}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}


\usepackage{tikz}
\usetikzlibrary{automata,positioning}

\pagestyle{empty}

\usepackage{fancyhdr}

\pagestyle{fancy}
\fancyhf{}
\theoremstyle{definition}
\newtheorem{ubung}{Aufgabe}
\newtheorem{uebung}{Aufgabe}

\newcommand{\bN}{\mathbb{N}}
\newcommand{\lra}{\leftrightarrow}
\newcommand{\such}{\; : \;}
\newenvironment{hint}{\textit{Hinweis:}}{}


\begin{document}

\lhead{Logik f\"ur Studierende der Informatik\\
WS 2022/23
}

\rhead{Dozentin: Prof. Dr. Heike Mildenberger\\\
Assistent: M.Sc. Christian Br\"auninger}


$\,$\\
\\
\\
\cfoot{Abgabe per Ilias bis Mittwoch 30.11.2021, 10 Uhr.}



\begin{center}
 \textbf{BLATT 6}\\
 (23.11.2022)
\end{center}



\begin{ubung}[4 Punkte]~\\
Es sei $\Sigma =\{0,1\}$ und $M$ die Einband-Turingmaschine mit Startzustand $q_0$, welche durch das folgende \"Ubergangsdiagramm gegeben ist.
\begin{center}
\begin{tikzpicture}[shorten >=1pt,node distance=3cm,on grid,auto]
   \node[state] (q_0)   {$q_0$};
   \node[state] (q_1) [right=of q_0] {$q_1$};
   \node[state] (q_2) [right=of q_1] {$q_2$};
   \node[state] (q_3) [below=of q_0] {$q_{ak}$};
   \node[state] (q_4) [below=of q_2] {$q_{ab}$};
    \path[->]
    (q_0) edge [loop left] node {$0 \to R$} ()
          edge [bend left] node {$1 \to R$} (q_1)
          edge  node [swap] {$b\to R$} (q_3)
    (q_1) edge [bend left] node {$0\to R$} (q_2)
    	  edge [bend left] node {$1\to R$} (q_0)
          edge [bend right] node [swap] {$b\to R$} (q_4)
    (q_2) edge [bend left] node {$0\to R$} (q_1)
          edge [loop right] node {$1\to R$} ()
          edge  node {$b\to R$} (q_4);
\end{tikzpicture}
\end{center}
\begin{enumerate}
\item[a)] In welchem Zustand h\"alt $M$ bei den Eingaben '$11$', '$1010$', '$1001$' und '$100101$'?
\item[b)] Geben Sie $A(M)$ an. Sie brauchen Ihre Angabe nicht zu beweisen.
\end{enumerate}
\end{ubung}
\medskip


\begin{ubung}[4 Punkte]~\\
Sei $\Sigma$ eine endliche Menge und $S$ und  $S'$ Turing-berechenbare Teilmengen von $\Sigma^*$.
Sind dann auch die Mengen $\Sigma^* \setminus S$ , $S \cup S'$ und $S \cap S'$ berechenbar?
\end{ubung}

\medskip


\begin{ubung}[4 Punkte]~\\
Es sei $\Sigma=\{a_0,\dots ,a_n\}$ ein beliebiges, nicht-leeres endliches Alphabet. Geben Sie das \"Ubergangsdiagramm einer Turingmaschine an, die jede Eingabe aus $\Sigma^\ast$ akzeptiert und diese Eingabe spiegelt, d.h. bei einer Eingabe $(e_0,\dots,e_k)\in \Sigma^*$ die Ausgabe $(e_k,\dots,e_0)$ hat, d.h. im Stoppzustand genau $(e_k, \dots, e_0)$ als Inschrift auf dem ersten Band hat.
\end{ubung}

\medskip



\begin{ubung}[4 Punkte]~\\
Gegeben sei eine nichtdeterministische Turingmaschine $M = (Q, \Sigma, \Gamma, b, q_0, q_{ab}, S, F, \delta )$ mit
\begin{itemize}
\item $Q=\{q_0,q_1,q_2,q_{ab}\}$, $S=\{q_2,q_{ab}\}$, $F=\{q_2\}$,
\item $\Sigma= \{0,1\}$, $\Gamma = \Sigma \cup \{b\}$,
\item $\delta((q_0,b)))= \{(q_0,0,R), (q_1,1,R), (q_2,b,L)\}$ und $\delta((q_1,b)))= \{(q_1,0,R), (q_2,b,L)\}$.
\end{itemize}
Geben Sie alle W\"orter an, die auf das Band geschrieben werden k\"onnen, wenn $M$ auf das leere Wort angesetzt wird und nach sp\"atestens f\"unf Schritten den Endzustand $q_2$ erreicht.
\end{ubung}


\end{document}