%blatt5
\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}


\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 23.11.2021, 10 Uhr.}



\begin{center}
 \textbf{BLATT 5}\\
 (16.11.2022)
\end{center}



\begin{ubung}[4 Punkte]~\\
Wir betrachten die Turingmaschine aus dem ersten Beispiel im Skript.
%%Vielleicht noch mit Uebergangsdiagramm?
Nach h\"ochstens wievielen Konfigurationen h\"alt die Turingmaschine bei einer Eingabe von genau $n$ Nullen?
\end{ubung}
\medskip


\begin{ubung}[4 Punkte]~\\
Es sei $M=(Q,\Sigma, \Gamma,\delta, q_0,q_{ak},q_{ab})$ die folgende Turingmaschine:
\begin{itemize}
\item
\( Q = \{ q_0, q_1, q_2, q_3, q_4, q_{ak}, q_{ab} \} \),
\item
\( \Sigma = \{ 1,2 \} \),
\item
\( \Gamma = \{ 1,2,b \} \),
\item
\( \delta(q_0,1) = ( q_1, 1, R) \),
\( \delta(q_0,2) = ( q_3, 2, R) \),
\( \delta(q_0,b) = ( q_{ak}, b, L) \),\\
\( \delta(q_1,1) = ( q_2, 1, R) \),
\( \delta(q_1,2) = ( q_{ab}, 1, L) \),
\( \delta(q_1,b) = ( q_{ab}, 2, R) \),\\
\( \delta(q_2,1) = ( q_0, 1, R) \),
\( \delta(q_2,2) = ( q_{ab}, 2, R) \),
\( \delta(q_2,b) = ( q_{ab}, 1, L) \),\\
\( \delta(q_3,1) = ( q_{ab}, b, L) \),
\( \delta(q_3,2) = ( q_4, 2, R) \),
\( \delta(q_3,b) = ( q_{ab}, 2, L) \),  \\
\( \delta(q_4,1) = ( q_{ab}, 1, R) \),
\( \delta(q_4,2) = ( q_0, 2, R) \),
\( \delta(q_4,b) = ( q_{ab}, b, R) \).
\end{itemize}
\begin{itemize}
\item[a)] Geben Sie ein \"Ubergangsdiagramm f\"ur $M$ an.
\item[b)] Bestimmen Sie $A(M)$.
\end{itemize}
\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 verdoppelt, d.h. bei einer Eingabe $(e_0,\dots,e_k)\in \Sigma^*$ die Ausgabe $(e_0,\dots,e_k,b,e_0,\dots,e_k)$ hat.
\end{ubung}

\medskip



\begin{ubung}[4 Punkte]~\\
Es sei $\Sigma=\{0,1\}$. Beantworten sie die folgenden Fragen, indem Sie entweder das \"Ubergangsdiagramm einer solchen Turingmaschine oder eine kurze Begr\"undung, warum es keine geben kann, angeben. Ein exakter Beweis ist nicht n\"otig.
\begin{enumerate}
\item[a)] Gibt es eine Turingmaschine $M$, welche nicht auf das Band schreibt, mit $$A(M)=\{0^m1^n\such m,n\in\bN \}?$$
\item[b)] Gibt es eine Turingmaschine $M$, welche nicht auf das Band schreibt, mit $$A(M)=\{0^n1^n\such n\in\bN \}?$$
\end{enumerate}\end{ubung}


\end{document}