Created
July 28, 2020 16:20
-
-
Save henrydatei/95961595ecc465280cf72e4b8dbf731b to your computer and use it in GitHub Desktop.
Lösungen zu den Übungsaufgaben Blatt 5 bis 12
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| \documentclass{article} | |
| \usepackage{amsmath,amssymb} | |
| \usepackage{tikz} | |
| \usepackage{xcolor} | |
| \usepackage[left=2.1cm,right=3.1cm,bottom=3cm,footskip=0.75cm,headsep=0.5cm]{geometry} | |
| \usepackage{enumerate} | |
| \usepackage{enumitem} | |
| \usepackage{marvosym} | |
| \usepackage{tabularx} | |
| \usepackage[utf8]{inputenc} | |
| \renewcommand*{\arraystretch}{1.4} | |
| \newcolumntype{L}[1]{>{\raggedright\arraybackslash}p{#1}} | |
| \newcolumntype{R}[1]{>{\raggedleft\arraybackslash}p{#1}} | |
| \newcolumntype{C}[1]{>{\centering\let\newline\\\arraybackslash\hspace{0pt}}m{#1}} | |
| \title{\textbf{Einführung in die Informatik, Übung 10}} | |
| \author{\textsc{Henry Haustein}} | |
| \date{} | |
| \begin{document} | |
| \maketitle | |
| \section*{Aufwärmübung} | |
| \begin{enumerate}[label=(\alph*)] | |
| \item $L(G_1)\cup L(G_2)$: \textcolor{blue}{$(N_1\cup N_2\cup \{S\},\Sigma,P_1\cup P_2\cup \{S\to S_1,S\to S_2\},S)$} \\ | |
| $L(G_3)^\ast$: \textcolor{red}{$(N_3\cup \{T\},\Sigma,P_3\cup \{T\to\varepsilon,T\to TS_3\},T)$} \\ | |
| $(L(G_1)\cup L(G_2))\cdot L(G_3)^\ast$: (\textcolor{blue}{$N_1\cup N_2\cup \{S\}$} $\cup$ \textcolor{red}{$N_3\cup \{T\}$} $\cup \,\,\{A\},\Sigma$,\textcolor{blue}{$\,P_1\cup P_2\cup \{S\to S_1,S\to S_2\}$} $\cup$ \textcolor{red}{$P_3\cup \{T\to\varepsilon,T\to TS_3\}$} $\cup \,\,\{A\to ST\},A$) | |
| \item $L(G_1)\cup L(G_2)$: \textcolor{blue}{$(N_1\cup N_2\cup \{S\},\Sigma,P_1\cup P_2\cup \{S\to S_1,S\to S_2\},S)$} \\ | |
| $(L(G_1)\cup L(G_2))\cup L(G_3)$: (\textcolor{blue}{$N_1\cup N_2\cup \{S\}$} $\cup \,\,N_3\cup \{T\},\Sigma,$\textcolor{blue}{$\,P_1\cup P_2\cup \{S\to S_1,S\to S_2\}$} $\cup \,\,P_3\cup \{T\to S_3,T\to S\},T$) | |
| \end{enumerate} | |
| \section*{Aufgabe 10.1} | |
| \begin{enumerate}[label=(\alph*)] | |
| \item Turingmaschine hält an $\Rightarrow ababa\in L(\mathcal{A})$ | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \draw (0,0) -- (9,0); | |
| \draw (0,-1) -- (9,-1); | |
| \edef\i{1}; | |
| \foreach \symb in {$\not b$,$a$,$b$,$a$,$b$,$a$,$\not b$} { | |
| \draw (\i,0) -- (\i,-1); | |
| \node at (\i+0.5,-0.5) {\symb}; | |
| \pgfmathparse{\i+1} | |
| \xdef\i{\pgfmathresult} | |
| } | |
| \draw (\i,0) -- (\i,-1); | |
| \node (k) at (2,-2) {$q_0$}; | |
| \draw (k) -- (2.5,-2); | |
| \draw[->] (2.5,-2) -- (2.5,-1); | |
| \end{tikzpicture} | |
| \end{center} | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \draw (0,0) -- (9,0); | |
| \draw (0,-1) -- (9,-1); | |
| \edef\i{1}; | |
| \foreach \symb in {$\not b$,$\not b$,$b$,$a$,$b$,$a$,$\not b$} { | |
| \draw (\i,0) -- (\i,-1); | |
| \node at (\i+0.5,-0.5) {\symb}; | |
| \pgfmathparse{\i+1} | |
| \xdef\i{\pgfmathresult} | |
| } | |
| \draw (\i,0) -- (\i,-1); | |
| \node (k) at (3,-2) {$q_1$}; | |
| \draw (k) -- (3.5,-2); | |
| \draw[->] (3.5,-2) -- (3.5,-1); | |
| \end{tikzpicture} | |
| \end{center} | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \draw (0,0) -- (9,0); | |
| \draw (0,-1) -- (9,-1); | |
| \edef\i{1}; | |
| \foreach \symb in {$\not b$,$\not b$,$b$,$a$,$b$,$a$,$\not b$} { | |
| \draw (\i,0) -- (\i,-1); | |
| \node at (\i+0.5,-0.5) {\symb}; | |
| \pgfmathparse{\i+1} | |
| \xdef\i{\pgfmathresult} | |
| } | |
| \draw (\i,0) -- (\i,-1); | |
| \node (k) at (4,-2) {$q_2$}; | |
| \draw (k) -- (4.5,-2); | |
| \draw[->] (4.5,-2) -- (4.5,-1); | |
| \end{tikzpicture} | |
| \end{center} | |
| Zustand verändert sich nicht, keine Ersetzungen finden statt, Lese-Schreibkopf bewegt sich nur nach rechts | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \draw (0,0) -- (9,0); | |
| \draw (0,-1) -- (9,-1); | |
| \edef\i{1}; | |
| \foreach \symb in {$\not b$,$\not b$,$b$,$a$,$b$,$a$,$\not b$} { | |
| \draw (\i,0) -- (\i,-1); | |
| \node at (\i+0.5,-0.5) {\symb}; | |
| \pgfmathparse{\i+1} | |
| \xdef\i{\pgfmathresult} | |
| } | |
| \draw (\i,0) -- (\i,-1); | |
| \node (k) at (7,-2) {$q_2$}; | |
| \draw (k) -- (7.5,-2); | |
| \draw[->] (7.5,-2) -- (7.5,-1); | |
| \end{tikzpicture} | |
| \end{center} | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \draw (0,0) -- (9,0); | |
| \draw (0,-1) -- (9,-1); | |
| \edef\i{1}; | |
| \foreach \symb in {$\not b$,$\not b$,$b$,$a$,$b$,$a$,$\not b$} { | |
| \draw (\i,0) -- (\i,-1); | |
| \node at (\i+0.5,-0.5) {\symb}; | |
| \pgfmathparse{\i+1} | |
| \xdef\i{\pgfmathresult} | |
| } | |
| \draw (\i,0) -- (\i,-1); | |
| \node (k) at (6,-2) {$q_3$}; | |
| \draw (k) -- (6.5,-2); | |
| \draw[->] (6.5,-2) -- (6.5,-1); | |
| \end{tikzpicture} | |
| \end{center} | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \draw (0,0) -- (9,0); | |
| \draw (0,-1) -- (9,-1); | |
| \edef\i{1}; | |
| \foreach \symb in {$\not b$,$\not b$,$b$,$a$,$b$,$\not b$,$\not b$} { | |
| \draw (\i,0) -- (\i,-1); | |
| \node at (\i+0.5,-0.5) {\symb}; | |
| \pgfmathparse{\i+1} | |
| \xdef\i{\pgfmathresult} | |
| } | |
| \draw (\i,0) -- (\i,-1); | |
| \node (k) at (5,-2) {$q_z$}; | |
| \draw (k) -- (5.5,-2); | |
| \draw[->] (5.5,-2) -- (5.5,-1); | |
| \end{tikzpicture} | |
| \end{center} | |
| Zustand verändert sich nicht, keine Ersetzungen finden statt, Lese-Schreibkopf bewegt sich nur nach links | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \draw (0,0) -- (9,0); | |
| \draw (0,-1) -- (9,-1); | |
| \edef\i{1}; | |
| \foreach \symb in {$\not b$,$\not b$,$b$,$a$,$b$,$\not b$,$\not b$} { | |
| \draw (\i,0) -- (\i,-1); | |
| \node at (\i+0.5,-0.5) {\symb}; | |
| \pgfmathparse{\i+1} | |
| \xdef\i{\pgfmathresult} | |
| } | |
| \draw (\i,0) -- (\i,-1); | |
| \node (k) at (2,-2) {$q_z$}; | |
| \draw (k) -- (2.5,-2); | |
| \draw[->] (2.5,-2) -- (2.5,-1); | |
| \end{tikzpicture} | |
| \end{center} | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \draw (0,0) -- (9,0); | |
| \draw (0,-1) -- (9,-1); | |
| \edef\i{1}; | |
| \foreach \symb in {$\not b$,$\not b$,$b$,$a$,$b$,$\not b$,$\not b$} { | |
| \draw (\i,0) -- (\i,-1); | |
| \node at (\i+0.5,-0.5) {\symb}; | |
| \pgfmathparse{\i+1} | |
| \xdef\i{\pgfmathresult} | |
| } | |
| \draw (\i,0) -- (\i,-1); | |
| \node (k) at (3,-2) {$q_0$}; | |
| \draw (k) -- (3.5,-2); | |
| \draw[->] (3.5,-2) -- (3.5,-1); | |
| \end{tikzpicture} | |
| \end{center} | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \draw (0,0) -- (9,0); | |
| \draw (0,-1) -- (9,-1); | |
| \edef\i{1}; | |
| \foreach \symb in {$\not b$,$\not b$,$\not b$,$a$,$b$,$\not b$,$\not b$} { | |
| \draw (\i,0) -- (\i,-1); | |
| \node at (\i+0.5,-0.5) {\symb}; | |
| \pgfmathparse{\i+1} | |
| \xdef\i{\pgfmathresult} | |
| } | |
| \draw (\i,0) -- (\i,-1); | |
| \node (k) at (4,-2) {$q_4$}; | |
| \draw (k) -- (4.5,-2); | |
| \draw[->] (4.5,-2) -- (4.5,-1); | |
| \end{tikzpicture} | |
| \end{center} | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \draw (0,0) -- (9,0); | |
| \draw (0,-1) -- (9,-1); | |
| \edef\i{1}; | |
| \foreach \symb in {$\not b$,$\not b$,$\not b$,$a$,$b$,$\not b$,$\not b$} { | |
| \draw (\i,0) -- (\i,-1); | |
| \node at (\i+0.5,-0.5) {\symb}; | |
| \pgfmathparse{\i+1} | |
| \xdef\i{\pgfmathresult} | |
| } | |
| \draw (\i,0) -- (\i,-1); | |
| \node (k) at (5,-2) {$q_5$}; | |
| \draw (k) -- (5.5,-2); | |
| \draw[->] (5.5,-2) -- (5.5,-1); | |
| \end{tikzpicture} | |
| \end{center} | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \draw (0,0) -- (9,0); | |
| \draw (0,-1) -- (9,-1); | |
| \edef\i{1}; | |
| \foreach \symb in {$\not b$,$\not b$,$\not b$,$a$,$b$,$\not b$,$\not b$} { | |
| \draw (\i,0) -- (\i,-1); | |
| \node at (\i+0.5,-0.5) {\symb}; | |
| \pgfmathparse{\i+1} | |
| \xdef\i{\pgfmathresult} | |
| } | |
| \draw (\i,0) -- (\i,-1); | |
| \node (k) at (6,-2) {$q_5$}; | |
| \draw (k) -- (6.5,-2); | |
| \draw[->] (6.5,-2) -- (6.5,-1); | |
| \end{tikzpicture} | |
| \end{center} | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \draw (0,0) -- (9,0); | |
| \draw (0,-1) -- (9,-1); | |
| \edef\i{1}; | |
| \foreach \symb in {$\not b$,$\not b$,$\not b$,$a$,$b$,$\not b$,$\not b$} { | |
| \draw (\i,0) -- (\i,-1); | |
| \node at (\i+0.5,-0.5) {\symb}; | |
| \pgfmathparse{\i+1} | |
| \xdef\i{\pgfmathresult} | |
| } | |
| \draw (\i,0) -- (\i,-1); | |
| \node (k) at (5,-2) {$q_6$}; | |
| \draw (k) -- (5.5,-2); | |
| \draw[->] (5.5,-2) -- (5.5,-1); | |
| \end{tikzpicture} | |
| \end{center} | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \draw (0,0) -- (9,0); | |
| \draw (0,-1) -- (9,-1); | |
| \edef\i{1}; | |
| \foreach \symb in {$\not b$,$\not b$,$\not b$,$a$,$\not b$,$\not b$,$\not b$} { | |
| \draw (\i,0) -- (\i,-1); | |
| \node at (\i+0.5,-0.5) {\symb}; | |
| \pgfmathparse{\i+1} | |
| \xdef\i{\pgfmathresult} | |
| } | |
| \draw (\i,0) -- (\i,-1); | |
| \node (k) at (4,-2) {$q_z$}; | |
| \draw (k) -- (4.5,-2); | |
| \draw[->] (4.5,-2) -- (4.5,-1); | |
| \end{tikzpicture} | |
| \end{center} | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \draw (0,0) -- (9,0); | |
| \draw (0,-1) -- (9,-1); | |
| \edef\i{1}; | |
| \foreach \symb in {$\not b$,$\not b$,$\not b$,$a$,$\not b$,$\not b$,$\not b$} { | |
| \draw (\i,0) -- (\i,-1); | |
| \node at (\i+0.5,-0.5) {\symb}; | |
| \pgfmathparse{\i+1} | |
| \xdef\i{\pgfmathresult} | |
| } | |
| \draw (\i,0) -- (\i,-1); | |
| \node (k) at (3,-2) {$q_z$}; | |
| \draw (k) -- (3.5,-2); | |
| \draw[->] (3.5,-2) -- (3.5,-1); | |
| \end{tikzpicture} | |
| \end{center} | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \draw (0,0) -- (9,0); | |
| \draw (0,-1) -- (9,-1); | |
| \edef\i{1}; | |
| \foreach \symb in {$\not b$,$\not b$,$\not b$,$a$,$\not b$,$\not b$,$\not b$} { | |
| \draw (\i,0) -- (\i,-1); | |
| \node at (\i+0.5,-0.5) {\symb}; | |
| \pgfmathparse{\i+1} | |
| \xdef\i{\pgfmathresult} | |
| } | |
| \draw (\i,0) -- (\i,-1); | |
| \node (k) at (4,-2) {$q_0$}; | |
| \draw (k) -- (4.5,-2); | |
| \draw[->] (4.5,-2) -- (4.5,-1); | |
| \end{tikzpicture} | |
| \end{center} | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \draw (0,0) -- (9,0); | |
| \draw (0,-1) -- (9,-1); | |
| \edef\i{1}; | |
| \foreach \symb in {$\not b$,$\not b$,$\not b$,$\not b$,$\not b$,$\not b$,$\not b$} { | |
| \draw (\i,0) -- (\i,-1); | |
| \node at (\i+0.5,-0.5) {\symb}; | |
| \pgfmathparse{\i+1} | |
| \xdef\i{\pgfmathresult} | |
| } | |
| \draw (\i,0) -- (\i,-1); | |
| \node (k) at (5,-2) {$q_1$}; | |
| \draw (k) -- (5.5,-2); | |
| \draw[->] (5.5,-2) -- (5.5,-1); | |
| \end{tikzpicture} | |
| \end{center} | |
| \item Turingmaschine hält nicht an $\Rightarrow abaa\notin L(\mathcal{A})$ | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \draw (0,0) -- (8,0); | |
| \draw (0,-1) -- (8,-1); | |
| \edef\i{1}; | |
| \foreach \symb in {$\not b$,$a$,$b$,$a$,$a$,$\not b$} { | |
| \draw (\i,0) -- (\i,-1); | |
| \node at (\i+0.5,-0.5) {\symb}; | |
| \pgfmathparse{\i+1} | |
| \xdef\i{\pgfmathresult} | |
| } | |
| \draw (\i,0) -- (\i,-1); | |
| \node (k) at (2,-2) {$q_0$}; | |
| \draw (k) -- (2.5,-2); | |
| \draw[->] (2.5,-2) -- (2.5,-1); | |
| \end{tikzpicture} | |
| \end{center} | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \draw (0,0) -- (8,0); | |
| \draw (0,-1) -- (8,-1); | |
| \edef\i{1}; | |
| \foreach \symb in {$\not b$,$\not b$,$b$,$a$,$a$,$\not b$} { | |
| \draw (\i,0) -- (\i,-1); | |
| \node at (\i+0.5,-0.5) {\symb}; | |
| \pgfmathparse{\i+1} | |
| \xdef\i{\pgfmathresult} | |
| } | |
| \draw (\i,0) -- (\i,-1); | |
| \node (k) at (3,-2) {$q_1$}; | |
| \draw (k) -- (3.5,-2); | |
| \draw[->] (3.5,-2) -- (3.5,-1); | |
| \end{tikzpicture} | |
| \end{center} | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \draw (0,0) -- (8,0); | |
| \draw (0,-1) -- (8,-1); | |
| \edef\i{1}; | |
| \foreach \symb in {$\not b$,$\not b$,$b$,$a$,$a$,$\not b$} { | |
| \draw (\i,0) -- (\i,-1); | |
| \node at (\i+0.5,-0.5) {\symb}; | |
| \pgfmathparse{\i+1} | |
| \xdef\i{\pgfmathresult} | |
| } | |
| \draw (\i,0) -- (\i,-1); | |
| \node (k) at (4,-2) {$q_2$}; | |
| \draw (k) -- (4.5,-2); | |
| \draw[->] (4.5,-2) -- (4.5,-1); | |
| \end{tikzpicture} | |
| \end{center} | |
| Zustand verändert sich nicht, keine Ersetzungen finden statt, Lese-Schreibkopf bewegt sich nur nach rechts | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \draw (0,0) -- (8,0); | |
| \draw (0,-1) -- (8,-1); | |
| \edef\i{1}; | |
| \foreach \symb in {$\not b$,$\not b$,$b$,$a$,$a$,$\not b$} { | |
| \draw (\i,0) -- (\i,-1); | |
| \node at (\i+0.5,-0.5) {\symb}; | |
| \pgfmathparse{\i+1} | |
| \xdef\i{\pgfmathresult} | |
| } | |
| \draw (\i,0) -- (\i,-1); | |
| \node (k) at (6,-2) {$q_2$}; | |
| \draw (k) -- (6.5,-2); | |
| \draw[->] (6.5,-2) -- (6.5,-1); | |
| \end{tikzpicture} | |
| \end{center} | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \draw (0,0) -- (8,0); | |
| \draw (0,-1) -- (8,-1); | |
| \edef\i{1}; | |
| \foreach \symb in {$\not b$,$\not b$,$b$,$a$,$a$,$\not b$} { | |
| \draw (\i,0) -- (\i,-1); | |
| \node at (\i+0.5,-0.5) {\symb}; | |
| \pgfmathparse{\i+1} | |
| \xdef\i{\pgfmathresult} | |
| } | |
| \draw (\i,0) -- (\i,-1); | |
| \node (k) at (5,-2) {$q_3$}; | |
| \draw (k) -- (5.5,-2); | |
| \draw[->] (5.5,-2) -- (5.5,-1); | |
| \end{tikzpicture} | |
| \end{center} | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \draw (0,0) -- (8,0); | |
| \draw (0,-1) -- (8,-1); | |
| \edef\i{1}; | |
| \foreach \symb in {$\not b$,$\not b$,$b$,$a$,$\not b$,$\not b$} { | |
| \draw (\i,0) -- (\i,-1); | |
| \node at (\i+0.5,-0.5) {\symb}; | |
| \pgfmathparse{\i+1} | |
| \xdef\i{\pgfmathresult} | |
| } | |
| \draw (\i,0) -- (\i,-1); | |
| \node (k) at (4,-2) {$q_z$}; | |
| \draw (k) -- (4.5,-2); | |
| \draw[->] (4.5,-2) -- (4.5,-1); | |
| \end{tikzpicture} | |
| \end{center} | |
| Zustand verändert sich nicht, keine Ersetzungen finden statt, Lese-Schreibkopf bewegt sich nur nach links | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \draw (0,0) -- (8,0); | |
| \draw (0,-1) -- (8,-1); | |
| \edef\i{1}; | |
| \foreach \symb in {$\not b$,$\not b$,$b$,$a$,$\not b$,$\not b$} { | |
| \draw (\i,0) -- (\i,-1); | |
| \node at (\i+0.5,-0.5) {\symb}; | |
| \pgfmathparse{\i+1} | |
| \xdef\i{\pgfmathresult} | |
| } | |
| \draw (\i,0) -- (\i,-1); | |
| \node (k) at (2,-2) {$q_z$}; | |
| \draw (k) -- (2.5,-2); | |
| \draw[->] (2.5,-2) -- (2.5,-1); | |
| \end{tikzpicture} | |
| \end{center} | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \draw (0,0) -- (8,0); | |
| \draw (0,-1) -- (8,-1); | |
| \edef\i{1}; | |
| \foreach \symb in {$\not b$,$\not b$,$b$,$a$,$\not b$,$\not b$} { | |
| \draw (\i,0) -- (\i,-1); | |
| \node at (\i+0.5,-0.5) {\symb}; | |
| \pgfmathparse{\i+1} | |
| \xdef\i{\pgfmathresult} | |
| } | |
| \draw (\i,0) -- (\i,-1); | |
| \node (k) at (3,-2) {$q_0$}; | |
| \draw (k) -- (3.5,-2); | |
| \draw[->] (3.5,-2) -- (3.5,-1); | |
| \end{tikzpicture} | |
| \end{center} | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \draw (0,0) -- (8,0); | |
| \draw (0,-1) -- (8,-1); | |
| \edef\i{1}; | |
| \foreach \symb in {$\not b$,$\not b$,$\not b$,$a$,$\not b$,$\not b$} { | |
| \draw (\i,0) -- (\i,-1); | |
| \node at (\i+0.5,-0.5) {\symb}; | |
| \pgfmathparse{\i+1} | |
| \xdef\i{\pgfmathresult} | |
| } | |
| \draw (\i,0) -- (\i,-1); | |
| \node (k) at (4,-2) {$q_4$}; | |
| \draw (k) -- (4.5,-2); | |
| \draw[->] (4.5,-2) -- (4.5,-1); | |
| \end{tikzpicture} | |
| \end{center} | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \draw (0,0) -- (8,0); | |
| \draw (0,-1) -- (8,-1); | |
| \edef\i{1}; | |
| \foreach \symb in {$\not b$,$\not b$,$\not b$,$a$,$\not b$,$\not b$} { | |
| \draw (\i,0) -- (\i,-1); | |
| \node at (\i+0.5,-0.5) {\symb}; | |
| \pgfmathparse{\i+1} | |
| \xdef\i{\pgfmathresult} | |
| } | |
| \draw (\i,0) -- (\i,-1); | |
| \node (k) at (5,-2) {$q_5$}; | |
| \draw (k) -- (5.5,-2); | |
| \draw[->] (5.5,-2) -- (5.5,-1); | |
| \end{tikzpicture} | |
| \end{center} | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \draw (0,0) -- (8,0); | |
| \draw (0,-1) -- (8,-1); | |
| \edef\i{1}; | |
| \foreach \symb in {$\not b$,$\not b$,$\not b$,$a$,$\not b$,$\not b$} { | |
| \draw (\i,0) -- (\i,-1); | |
| \node at (\i+0.5,-0.5) {\symb}; | |
| \pgfmathparse{\i+1} | |
| \xdef\i{\pgfmathresult} | |
| } | |
| \draw (\i,0) -- (\i,-1); | |
| \node (k) at (4,-2) {$q_6$}; | |
| \draw (k) -- (4.5,-2); | |
| \draw[->] (4.5,-2) -- (4.5,-1); | |
| \end{tikzpicture} | |
| \end{center} | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \draw (0,0) -- (8,0); | |
| \draw (0,-1) -- (8,-1); | |
| \edef\i{1}; | |
| \foreach \symb in {$\not b$,$\not b$,$\not b$,$a$,$\not b$,$\not b$} { | |
| \draw (\i,0) -- (\i,-1); | |
| \node at (\i+0.5,-0.5) {\symb}; | |
| \pgfmathparse{\i+1} | |
| \xdef\i{\pgfmathresult} | |
| } | |
| \draw (\i,0) -- (\i,-1); | |
| \node (k) at (4,-2) {$q_{loop}$}; | |
| \draw (k) -- (4.5,-2); | |
| \draw[->] (4.5,-2) -- (4.5,-1); | |
| \end{tikzpicture} | |
| \end{center} | |
| \item $q_0$: Löschen des ersten Buchstabens und entscheiden $q_1-q_3$-Zweig oder $q_4-q_6$-Zweig \\ | |
| $q_1+q_2$: zum Ende des Wortes gehen ($q_1$ sorgt dafür, dass eine Möglichkeit für die Turingmaschine gibt anzuhalten, weil $\not b$ in $q_1$ nicht behandelt wird) \\ | |
| $q_3$: letzten Buchstaben des Wortes lesen: $a\Rightarrow q_z$, $b\Rightarrow q_{loop}$ \\ | |
| $q_4$-$q_6$: machen das selbe wie $q_1$-$q_3$ nur für $b$ \\ | |
| $q_z$: zum Anfang des (verkürzten) Wortes gehen \\ | |
| $q_{loop}$: Endlosschleife, um Turingmaschine am laufen zu halten | |
| \item Palindrome über $\{a,b\}$ | |
| \end{enumerate} | |
| \section*{Aufgabe 10.2} | |
| $\mathcal{A}=(\{q_0\},\{a,b\},\{a,b,\not b\},q_0,\delta)$ mit $\delta$ | |
| \begin{center} | |
| \begin{tabular}{cccccc} | |
| $q_0$ & $a$ & $\to$ & $a$ & $n$ & $q_0$ \\ | |
| $q_0$ & $b$ & $\to$ & $b$ & $n$ & $q_0$ | |
| \end{tabular} | |
| \end{center} | |
| \section*{Aufgabe 10.3} | |
| Idee: | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \draw (0,0) -- (10,0); | |
| \draw (0,-1) -- (10,-1); | |
| \edef\i{1}; | |
| \foreach \symb in {$\not b$,$a$,$a$,$\not b$,$a$,$a$,$a$,$\not b$} { | |
| \draw (\i,0) -- (\i,-1); | |
| \node at (\i+0.5,-0.5) {\symb}; | |
| \pgfmathparse{\i+1} | |
| \xdef\i{\pgfmathresult} | |
| } | |
| \draw (\i,0) -- (\i,-1); | |
| \node (k) at (2,-2) {$q_{0}$}; | |
| \draw (k) -- (2.5,-2); | |
| \draw[->] (2.5,-2) -- (2.5,-1); | |
| \end{tikzpicture} | |
| \end{center} | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \draw (0,0) -- (10,0); | |
| \draw (0,-1) -- (10,-1); | |
| \edef\i{1}; | |
| \foreach \symb in {$\not b$,$a$,$a$,$a$,$a$,$a$,$\not b$,$\not b$} { | |
| \draw (\i,0) -- (\i,-1); | |
| \node at (\i+0.5,-0.5) {\symb}; | |
| \pgfmathparse{\i+1} | |
| \xdef\i{\pgfmathresult} | |
| } | |
| \draw (\i,0) -- (\i,-1); | |
| \node (k) at (6.8,-2) {$q_{fertig}$}; | |
| \draw (k) -- (7.5,-2); | |
| \draw[->] (7.5,-2) -- (7.5,-1); | |
| \end{tikzpicture} | |
| \end{center} | |
| $\mathcal{A}=(\{q_0,q_1,q_2,q_{fertig}\},\{a\},\{a,\not b\},q_0,\delta)$ mit $\delta$ | |
| \begin{center} | |
| \begin{tabular}{cccccc} | |
| $q_0$ & $a$ & $\to$ & $a$ & $r$ & $q_0$ \\ | |
| $q_0$ & $\not b$ & $\to$ & $a$ & $r$ & $q_1$ \\ | |
| \hline | |
| $q_1$ & $a$ & $\to$ & $a$ & $r$ & $q_1$ \\ | |
| $q_1$ & $\not b$ & $\to$ & $\not b$ & $l$ & $q_2$ \\ | |
| \hline | |
| $q_2$ & $a$ & $\to$ & $\not b$ & $n$ & $q_{fertig}$ \\ | |
| \hline | |
| $q_{fertig}$ & $a$ & $\to$ & $a$ & $l$ & $q_{fertig}$ | |
| \end{tabular} | |
| \end{center} | |
| \end{document} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| \documentclass{article} | |
| \usepackage{amsmath,amssymb} | |
| \usepackage{tikz} | |
| \usepackage{xcolor} | |
| \usepackage[left=2.1cm,right=3.1cm,bottom=3cm,footskip=0.75cm,headsep=0.5cm]{geometry} | |
| \usepackage{enumerate} | |
| \usepackage{enumitem} | |
| \usepackage{marvosym} | |
| \usepackage{tabularx} | |
| \usepackage{xcolor} | |
| \usepackage{colortbl} | |
| \usepackage[utf8]{inputenc} | |
| \renewcommand*{\arraystretch}{1.4} | |
| \newcolumntype{L}[1]{>{\raggedright\arraybackslash}p{#1}} | |
| \newcolumntype{R}[1]{>{\raggedleft\arraybackslash}p{#1}} | |
| \newcolumntype{C}[1]{>{\centering\let\newline\\\arraybackslash\hspace{0pt}}m{#1}} | |
| \title{\textbf{Einführung in die Informatik, Übung 12}} | |
| \author{\textsc{Henry Haustein}} | |
| \date{} | |
| \begin{document} | |
| \maketitle | |
| \section*{Aufgabe 12.1} | |
| \begin{enumerate}[label=(\alph*)] | |
| \item alle Modelle von $\Gamma$ finden: | |
| \begin{center} | |
| \begin{tabular}{ccc||c|c|c} | |
| $p$ & $q$ & $r$ & $p\Rightarrow q$ & $r\lor p$ & $\neg q\lor r$ \\ | |
| \hline | |
| 0 & 0 & 0 & 1 & 0 & 1 \\ | |
| 0 & 0 & 1 & \textcolor{red}{1} & \textcolor{red}{1} & \textcolor{red}{1} \\ | |
| 0 & 1 & 0 & 1 & 0 & 0 \\ | |
| 0 & 1 & 1 & \textcolor{red}{1} & \textcolor{red}{1} & \textcolor{red}{1} \\ | |
| 1 & 0 & 0 & 0 & 1 & 1 \\ | |
| 1 & 0 & 1 & 0 & 1 & 1 \\ | |
| 1 & 1 & 0 & 1 & 1 & 0 \\ | |
| 1 & 1 & 1 & \textcolor{red}{1} & \textcolor{red}{1} & \textcolor{red}{1} \\ | |
| \end{tabular} | |
| \end{center} | |
| 3 Modelle erfüllen $\Gamma$ | |
| \item $\Gamma\models (\neg p\lor r)$, denn | |
| \begin{center} | |
| \begin{tabular}{ccc||c} | |
| $p$ & $q$ & $r$ & $\neg p\lor r$ \\ | |
| \hline | |
| 0 & 0 & 1 & 1 \\ | |
| 0 & 1 & 1 & 1 \\ | |
| 1 & 1 & 1 & 1 \\ | |
| \end{tabular} | |
| \end{center} | |
| \item $\Gamma\not\models (\neg q\land r)$, denn | |
| \begin{center} | |
| \begin{tabular}{ccc||c} | |
| $p$ & $q$ & $r$ & $\neg q\land r$ \\ | |
| \hline | |
| 0 & 0 & 1 & 1 \\ | |
| 0 & 1 & 1 & 0 \\ | |
| 1 & 1 & 1 & 0 \\ | |
| \end{tabular} | |
| \end{center} | |
| \item $\Gamma\models (q\lor r)$, denn | |
| \begin{center} | |
| \begin{tabular}{ccc||c} | |
| $p$ & $q$ & $r$ & $q\lor r$ \\ | |
| \hline | |
| 0 & 0 & 1 & 1 \\ | |
| 0 & 1 & 1 & 1 \\ | |
| 1 & 1 & 1 & 1 \\ | |
| \end{tabular} | |
| \end{center} | |
| \end{enumerate} | |
| \section*{Aufgabe 12.2} | |
| \begin{enumerate}[label=(\alph*)] | |
| \item siehe Tabelle | |
| \begin{center} | |
| \begin{tabular}{cc||c|c|c} | |
| $\phi$ & $\psi$ & $\phi\lor\psi$ & $\phi\land(\phi\lor\psi)$ & $\phi\land(\phi\lor\psi)\equiv\phi$ \\ | |
| \hline | |
| 0 & 0 & 0 & 0 & 1 \\ | |
| 0 & 1 & 1 & 0 & 1 \\ | |
| 1 & 0 & 1 & 1 & 1 \\ | |
| 1 & 1 & 1 & 1 & 1 \\ | |
| \end{tabular} | |
| \end{center} | |
| \item siehe Tabelle | |
| \begin{center} | |
| \begin{tabular}{ccc||c|c|c|c|c|c} | |
| $\phi$ & $\psi$ & $\pi$ & $\psi\lor\pi$ & $\phi\land(\psi\lor\pi)$ & $\phi\land\psi$ & $\phi\land\pi$ & $(\phi\land\psi)\lor(\phi\land\pi)$ & $\phi\land(\psi\lor\pi)\equiv(\phi\land\psi)\lor(\phi\land\pi)$ \\ | |
| \hline | |
| 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ | |
| 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ | |
| 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ | |
| 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ | |
| 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ | |
| 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 \\ | |
| 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ | |
| 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 | |
| \end{tabular} | |
| \end{center} | |
| \end{enumerate} | |
| \section*{Aufgabe 12.3} | |
| Ersetzungen: | |
| \begin{itemize} | |
| \item $a\lor b\equiv \neg\neg a\lor\neg\neg b\equiv\neg(\neg a\land\neg b)$ | |
| \item $c\Leftrightarrow d\equiv (c\land d)\lor(\neg c\land\neg d) \equiv \neg(\neg (c\land d)\land\neg (\neg c\land\neg d))$ | |
| \end{itemize} | |
| \begin{align} | |
| \phi &= \neg(((\neg p\lor q)\lor(p\Leftrightarrow\neg q))\textcolor{red}{\,\lor\,}\neg(r\land(s\lor r))) \notag \\ | |
| &= \neg(\neg(\neg ((\neg p\lor q)\lor(p\Leftrightarrow\neg q))\land\neg(\neg(r\land(s\textcolor{red}{\,\lor\,} r))))) \notag \\ | |
| &= \neg(\neg(\neg ((\neg p\lor q)\textcolor{red}{\,\lor\,}(p\Leftrightarrow\neg q))\land\neg(\neg(r\land(\neg(\neg s\land\neg r)))))) \notag \\ | |
| &= \neg(\neg(\neg (\neg(\neg (\neg p\textcolor{red}{\,\lor\,} q)\land\neg (p\Leftrightarrow\neg q)))\land\neg(\neg(r\land(\neg(\neg s\land\neg r)))))) \notag \\ | |
| &= \neg(\neg(\neg (\neg(\neg (\neg(\neg (\neg p)\land\neg q))\land\neg (p\textcolor{red}{\,\Leftrightarrow\,}\neg q)))\land\neg(\neg(r\land(\neg(\neg s\land\neg r)))))) \notag \\ | |
| &= \neg(\neg(\neg (\neg(\neg (\neg(\neg (\neg p)\land\neg q))\land\neg (\neg(\neg (p\land \neg q)\land\neg (\neg p\land\neg \neg q)))))\land\neg(\neg(r\land(\neg(\neg s\land\neg r)))))) \notag | |
| \end{align} | |
| \section*{Aufgabe 12.4} | |
| \begin{enumerate}[label=(\alph*)] | |
| \item siehe Tabelle | |
| \end{enumerate} | |
| \section*{Aufgabe 12.5} | |
| \end{document} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| \documentclass{article} | |
| \usepackage{amsmath,amssymb} | |
| \usepackage{tikz} | |
| \usepackage{xcolor} | |
| \usepackage[left=2.1cm,right=3.1cm,bottom=3cm,footskip=0.75cm,headsep=0.5cm]{geometry} | |
| \usepackage{enumerate} | |
| \usepackage{enumitem} | |
| \usepackage{marvosym} | |
| \usepackage{tabularx} | |
| \usepackage{xcolor} | |
| \usepackage{colortbl} | |
| \usepackage[utf8]{inputenc} | |
| \renewcommand*{\arraystretch}{1.4} | |
| \newcolumntype{L}[1]{>{\raggedright\arraybackslash}p{#1}} | |
| \newcolumntype{R}[1]{>{\raggedleft\arraybackslash}p{#1}} | |
| \newcolumntype{C}[1]{>{\centering\let\newline\\\arraybackslash\hspace{0pt}}m{#1}} | |
| \title{\textbf{Einführung in die Informatik, Übung 12}} | |
| \author{\textsc{Henry Haustein}} | |
| \date{} | |
| \begin{document} | |
| \maketitle | |
| \section*{Aufgabe 12.1} | |
| \begin{enumerate}[label=(\alph*)] | |
| \item alle Modelle von $\Gamma$ finden: | |
| \begin{center} | |
| \begin{tabular}{ccc||c|c|c} | |
| $p$ & $q$ & $r$ & $p\Rightarrow q$ & $r\lor p$ & $\neg q\lor r$ \\ | |
| \hline | |
| 0 & 0 & 0 & 1 & 0 & 1 \\ | |
| \rowcolor{lime}0 & 0 & 1 & 1 & 1 & 1 \\ | |
| 0 & 1 & 0 & 1 & 0 & 0 \\ | |
| \rowcolor{lime}0 & 1 & 1 & 1 & 1 & 1 \\ | |
| 1 & 0 & 0 & 0 & 1 & 1 \\ | |
| 1 & 0 & 1 & 0 & 1 & 1 \\ | |
| 1 & 1 & 0 & 1 & 1 & 0 \\ | |
| \rowcolor{lime}1 & 1 & 1 & 1 & 1 & 1 \\ | |
| \end{tabular} | |
| \end{center} | |
| 3 Modelle erfüllen $\Gamma$ | |
| \item $\Gamma\models (\neg p\lor r)$, denn | |
| \begin{center} | |
| \begin{tabular}{ccc||c} | |
| $p$ & $q$ & $r$ & $\neg p\lor r$ \\ | |
| \hline | |
| 0 & 0 & 1 & 1 \\ | |
| 0 & 1 & 1 & 1 \\ | |
| 1 & 1 & 1 & 1 \\ | |
| \end{tabular} | |
| \end{center} | |
| \item $\Gamma\not\models (\neg q\land r)$, denn | |
| \begin{center} | |
| \begin{tabular}{ccc||c} | |
| $p$ & $q$ & $r$ & $\neg q\land r$ \\ | |
| \hline | |
| 0 & 0 & 1 & 1 \\ | |
| 0 & 1 & 1 & 0 \\ | |
| 1 & 1 & 1 & 0 \\ | |
| \end{tabular} | |
| \end{center} | |
| \item $\Gamma\models (q\lor r)$, denn | |
| \begin{center} | |
| \begin{tabular}{ccc||c} | |
| $p$ & $q$ & $r$ & $q\lor r$ \\ | |
| \hline | |
| 0 & 0 & 1 & 1 \\ | |
| 0 & 1 & 1 & 1 \\ | |
| 1 & 1 & 1 & 1 \\ | |
| \end{tabular} | |
| \end{center} | |
| \end{enumerate} | |
| \section*{Aufgabe 12.2} | |
| \begin{enumerate}[label=(\alph*)] | |
| \item siehe Tabelle | |
| \begin{center} | |
| \begin{tabular}{cc||c|c|c} | |
| $\phi$ & $\psi$ & $\phi\lor\psi$ & $\phi\land(\phi\lor\psi)$ & $\phi\land(\phi\lor\psi)\equiv\phi$ \\ | |
| \hline | |
| 0 & 0 & 0 & 0 & 1 \\ | |
| 0 & 1 & 1 & 0 & 1 \\ | |
| 1 & 0 & 1 & 1 & 1 \\ | |
| 1 & 1 & 1 & 1 & 1 \\ | |
| \end{tabular} | |
| \end{center} | |
| \item siehe Tabelle | |
| \begin{center} | |
| \begin{tabular}{ccc||c|c|c|c|c|c} | |
| $\phi$ & $\psi$ & $\pi$ & $\psi\lor\pi$ & $\phi\land(\psi\lor\pi)$ & $\phi\land\psi$ & $\phi\land\pi$ & $(\phi\land\psi)\lor(\phi\land\pi)$ & $\phi\land(\psi\lor\pi)\equiv(\phi\land\psi)\lor(\phi\land\pi)$ \\ | |
| \hline | |
| 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ | |
| 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ | |
| 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ | |
| 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ | |
| 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ | |
| 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 \\ | |
| 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ | |
| 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 | |
| \end{tabular} | |
| \end{center} | |
| \end{enumerate} | |
| \section*{Aufgabe 12.3} | |
| Ersetzungen: | |
| \begin{itemize} | |
| \item $a\lor b\equiv \neg\neg a\lor\neg\neg b\equiv\neg(\neg a\land\neg b)$ | |
| \item $c\Leftrightarrow d\equiv (c\land d)\lor(\neg c\land\neg d) \equiv \neg(\neg (c\land d)\land\neg (\neg c\land\neg d))$ | |
| \end{itemize} | |
| \begin{align} | |
| \phi &= \neg(((\neg p\lor q)\lor(p\Leftrightarrow\neg q))\textcolor{red}{\,\lor\,}\neg(r\land(s\lor r))) \notag \\ | |
| &= \neg(\neg(\neg ((\neg p\lor q)\lor(p\Leftrightarrow\neg q))\land\neg(\neg(r\land(s\textcolor{red}{\,\lor\,} r))))) \notag \\ | |
| &= \neg(\neg(\neg ((\neg p\lor q)\textcolor{red}{\,\lor\,}(p\Leftrightarrow\neg q))\land\neg(\neg(r\land(\neg(\neg s\land\neg r)))))) \notag \\ | |
| &= \neg(\neg(\neg (\neg(\neg (\neg p\textcolor{red}{\,\lor\,} q)\land\neg (p\Leftrightarrow\neg q)))\land\neg(\neg(r\land(\neg(\neg s\land\neg r)))))) \notag \\ | |
| &= \neg(\neg(\neg (\neg(\neg (\neg(\neg (\neg p)\land\neg q))\land\neg (p\textcolor{red}{\,\Leftrightarrow\,}\neg q)))\land\neg(\neg(r\land(\neg(\neg s\land\neg r)))))) \notag \\ | |
| &= \neg(\neg(\neg (\neg(\neg (\neg(\neg (\neg p)\land\neg q))\land\neg (\neg(\neg (p\land \neg q)\land\neg (\neg p\land\neg \neg q)))))\land\neg(\neg(r\land(\neg(\neg s\land\neg r)))))) \notag | |
| \end{align} | |
| \section*{Aufgabe 12.4} | |
| $\phi$ muss erst in die richtige Form gebracht werden, das Problem ist hier $\neg(p\lor r)\equiv\neg p\land\neg r$ | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \node at (0,0) (1) {$\phi$}; | |
| \node at (0,-1) (2) {$p$}; | |
| \node at (0,-2) (3) {$(\neg r\land((q\land\neg p)\lor r))\lor((r\land(p\lor\neg q))\land((\neg p\land \neg r)\lor(p\land r)))$}; | |
| \node at (-3,-3) (4) {$\neg r\land((q\land\neg p)\lor r)$}; | |
| \node at (-3,-4) (5) {$\neg r$}; | |
| \node at (-3,-5) (6) {$(q\land\neg p)\lor r$}; | |
| \node at (-4.5,-6) (7) {$r$}; | |
| \node at (-1.5,-6) (8) {$q\land\neg p$}; | |
| \node at (-1.5,-7) (9) {$q$}; | |
| \node at (-1.5,-8) (10) {$\neg p$}; | |
| \node at (3,-3) (11) {$(r\land(p\lor\neg q))\land((\neg p\land \neg r)\lor(p\land r))$}; | |
| \node at (3,-4) (12) {$r\land(p\lor\neg q)$}; | |
| \node at (3,-5) (13) {$(\neg p\land \neg r)\lor(p\land r)$}; | |
| \node at (3,-6) (14) {$r$}; | |
| \node at (3,-7) (15) {$p\lor\neg q$}; | |
| \node at (1.5,-8) (16) {$p$}; | |
| \node at (0,-9) (17) {$\neg p\land\neg r$}; | |
| \node at (0,-10) (18) {$\neg p$}; | |
| \node at (2,-9) (19) {$p\land r$}; | |
| \node at (2,-10) (20) {$p$}; | |
| \node at (2,-11) (21) {$r$}; | |
| \node at (4.5,-8) (22) {$\neg q$}; | |
| \node at (4,-9) (23) {$\neg p\land \neg r$}; | |
| \node at (4,-10) (24) {$\neg p$}; | |
| \node at (6,-9) (25) {$p\land r$}; | |
| \node at (6,-10) (26) {$p$}; | |
| \node at (6,-11) (27) {$r$}; | |
| \draw (1) -- (2) -- (3) -- (4) -- (5) -- (6) -- (7); | |
| \draw (6) -- (8) -- (9) -- (10); | |
| \draw (3) -- (11) -- (12) -- (13) -- (14) -- (15) -- (16) -- (17) -- (18); | |
| \draw (16) -- (19) -- (20) -- (21); | |
| \draw (15) -- (22) -- (23) -- (24); | |
| \draw (22) -- (25) -- (26) -- (27); | |
| \node[red] at (7.south) {$\times$}; | |
| \node[red] at (10.south) {$\times$}; | |
| \node[red] at (18.south) {$\times$}; | |
| \node[red] at (24.south) {$\times$}; | |
| \end{tikzpicture} | |
| \end{center} | |
| \section*{Aufgabe 12.5} | |
| \begin{enumerate}[label=(\alph*)] | |
| \item Hier ist das vollständige semantische Tableau. Die \textcolor{red}{roten} Knoten die Knoten, die dem Tableau aus der Aufgabenstellung fehlen. | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \node at (0,0) (1) {$\phi$}; | |
| \node at (0,-1) (2) {$(\neg r\lor p)\lor(p\land q)$}; | |
| \node at (0,-2) (3) {$p\land((p\land q)\lor\neg r)$}; | |
| \node at (0,-3) (4) {$p$}; | |
| \node at (0,-4) (5) {$(p\land q)\lor\neg r$}; | |
| \node at (-3,-5) (6) {$p\land q$}; | |
| \node at (-3,-6) (7) {$q$}; | |
| \node[red] at (-3,-7) (8) {$p$}; | |
| \node[red] at (-3,-8) (9) {$(\neg r\lor p)\lor(p\land q)$}; | |
| \node[red] at (-4.5,-9) (10) {$\neg r \lor p$}; | |
| \node[red] at (-5,-10) (11) {$\neg r$}; | |
| \node[red] at (-4,-10) (12) {$p$}; | |
| \node[red] at (-1.5,-9) (13) {$p\land q$}; | |
| \node[red] at (-1.5,-10) (14) {$p$}; | |
| \node[red] at (-1.5,-11) (15) {$q$}; | |
| \node at (3,-6) (16) {$(\neg r\lor p)\lor(p\land q)$}; | |
| \node at (1.5,-7) (17) {$\neg r\lor p$}; | |
| \node[red] at (1,-8) (18) {$\neg r$}; | |
| \node[red] at (2,-8) (19) {$p$}; | |
| \node at (4.5,-7) (20) {$p\land q$}; | |
| \node[red] at (4.5,-8) (21) {$p$}; | |
| \node[red] at (4.5,-9) (22) {$q$}; | |
| \node at (3,-5) (v) {$\neg r$}; | |
| \draw (1) -- (2) -- (3) -- (4) -- (5) -- (6) -- (7) -- (8) -- (9) -- (10) -- (11); | |
| \draw (9) -- (13) -- (14) -- (15); | |
| \draw (10) -- (12); | |
| \draw (5) -- (v) -- (16) -- (17) -- (18); | |
| \draw (17) -- (19); | |
| \draw (16) -- (20) -- (21) -- (22); | |
| \end{tikzpicture} | |
| \end{center} | |
| \item ja, z.B. für $w(p)=w(q)=w(r)=1$ | |
| \item nein, z.B. für $w(p)=w(q)=w(r)=0$ ist $w(\phi)=0$ | |
| \end{enumerate} | |
| \end{document} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| \documentclass{article} | |
| \usepackage{amsmath,amssymb} | |
| \usepackage{tikz} | |
| \usepackage{xcolor} | |
| \usepackage[left=2.1cm,right=3.1cm,bottom=3cm,footskip=0.75cm,headsep=0.5cm]{geometry} | |
| \usepackage{enumerate} | |
| \usepackage{enumitem} | |
| \usepackage[utf8]{inputenc} | |
| \renewcommand*{\arraystretch}{1.4} | |
| \title{\textbf{Einführung in die Informatik, Übung 5}} | |
| \author{\textsc{Henry Haustein}} | |
| \date{} | |
| \begin{document} | |
| \maketitle | |
| \section*{Aufgabe 5.1} | |
| \begin{enumerate}[label=(\alph*)] | |
| \item Gewichtsmatrix | |
| \begin{align} | |
| \begin{pmatrix} | |
| \infty & 60 & 20 & 10 & \infty & \infty \\ | |
| \infty & \infty & 20 & \infty & 10 & \infty \\ | |
| 30 & \infty & \infty & \infty & \infty & 30 \\ | |
| \infty & \infty & \infty & \infty & 70 & 50 \\ | |
| \infty & \infty & \infty & 40 & \infty & 30 \\ | |
| \infty & \infty & \infty & 20 & \infty & \infty \\ | |
| \end{pmatrix}\notag | |
| \end{align} | |
| \item \textsc{Dijkstra}'s Algorithmus | |
| \begin{center} | |
| \begin{tabular}{c|ccccccc} | |
| \textbf{Iteration} & $S$ & $v_1$ & $D(b)$ & $D(c)$ & $D(d)$ & $D(e)$ & $D(f)$ \\ | |
| \hline | |
| 0 & $\{a\}$ & & 60 & 20 & \textcolor{red}{10} & $\infty$ & $\infty$ \\ | |
| 1 & $\{a,d\}$ & $d$ & 60 & \textcolor{red}{20} & 10 & 80 & 60 \\ | |
| 2 & $\{a,d,c\}$ & $c$ & 60 & 20 & 10 & 80 & \textcolor{red}{50} \\ | |
| 3 & $\{a,d,c,f\}$ & $f$ & \textcolor{red}{60} & 20 & 10 & 80 & 50 \\ | |
| 4 & $\{a,d,c,f,b\}$ & $b$ & 60 & 20 & 10 & \textcolor{red}{70} & 50 \\ | |
| 5 & $\{a,d,c,f,b,e\}$ & $e$ & 60 & 20 & 10 & 70 & 50 \\ | |
| \end{tabular} | |
| \end{center} | |
| \end{enumerate} | |
| \section*{Aufgabe 5.2} | |
| Zahlen in den einzelnen Knoten sind die Knotengrade | |
| \begin{enumerate}[label=(\alph*)] | |
| \item ohne Waldschlösschenbrücke: alle Knotengrade sind gerade $\Rightarrow$ es gibt einen Eulerkreis $\Rightarrow$ Brückenproblem hat eine Lösung | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \node[circle,draw=black, fill=white] (1) at (0,0) {2}; | |
| \node[circle,draw=black, fill=white] (2) at (3,1) {6}; | |
| \node[circle,draw=black, fill=white] (3) at (4,-1) {8}; | |
| \node[circle,draw=black, fill=white] (4) at (6,1) {2}; | |
| \draw[double] (1) -- (3); | |
| \draw (3) to node[midway,left] {$\times$5} (2); | |
| \draw (2) -- (4); | |
| \draw (3) -- (4); | |
| \end{tikzpicture} | |
| \end{center} | |
| \item mit Waldschlösschenbrücke: nicht alle Knotengrade sind gerade $\Rightarrow$ es gibt keinen Eulerkreis $\Rightarrow$ Brückenproblem hat keine Lösung | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \node[circle,draw=black, fill=white] (1) at (0,0) {2}; | |
| \node[circle,draw=black, fill=white] (2) at (3,1) {6}; | |
| \node[circle,draw=black, fill=white] (3) at (4,-1) {9}; | |
| \node[circle,draw=black, fill=white] (4) at (6,1) {3}; | |
| \draw[double] (1) -- (3); | |
| \draw (3) to node[midway,left] {$\times$5} (2); | |
| \draw (2) -- (4); | |
| \draw[double] (3) -- (4); | |
| \end{tikzpicture} | |
| \end{center} | |
| \end{enumerate} | |
| \section*{Aufgabe 5.3} | |
| \begin{enumerate}[label=(\alph*)] | |
| \item Kantenzahl: 17, Knotenzahl: 7 $\Rightarrow$ $17\not\le 3\cdot 7-6$ $\Rightarrow$ nicht planar | |
| \item nicht planar (zumindest vom Gefühl her) | |
| \end{enumerate} | |
| \section*{Aufgabe 5.4} | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \node[circle,draw=black, fill=white] (a) at (0,0) {$a$}; | |
| \node[circle,draw=black, fill=white] (b) at (-1.5,-1) {$b$}; | |
| \node[circle,draw=black, fill=white] (c) at (-1.5,-2) {$c$}; | |
| \node[circle,draw=black, fill=white] (d) at (0,-3) {$d$}; | |
| \node[circle,draw=black, fill=white] (e) at (1.5,-2) {$e$}; | |
| \node[circle,draw=black, fill=white] (f) at (1.5,-1) {$f$}; | |
| \draw (a) -- (c); | |
| \draw (a) -- (d); | |
| \draw (b) -- (c); | |
| \draw (b) -- (d); | |
| \draw (b) -- (f); | |
| \draw (c) -- (e); | |
| \draw (d) -- (e); | |
| \node at (0,1) {$G_1$}; | |
| \end{tikzpicture} | |
| \hspace*{1cm} | |
| \begin{tikzpicture} | |
| \node[circle,draw=black, fill=white] (a) at (0,0) {$a$}; | |
| \node[circle,draw=black, fill=white] (b) at (-1.5,-1) {$b$}; | |
| \node[circle,draw=black, fill=white] (c) at (-1.5,-2) {$c$}; | |
| \node[circle,draw=black, fill=white] (d) at (-0.66,-3) {$d$}; | |
| \node[circle,draw=black, fill=white] (e) at (0.66,-3) {$e$}; | |
| \node[circle,draw=black, fill=white] (f) at (1.5,-2) {$f$}; | |
| \node[circle,draw=black, fill=white] (g) at (1.5,-1) {$g$}; | |
| \draw (a) -- (d); | |
| \draw (a) -- (g); | |
| \draw (b) -- (c); | |
| \draw (b) -- (d); | |
| \draw (b) -- (g); | |
| \draw (c) -- (g); | |
| \draw (d) -- (e); | |
| \draw (e) -- (f); | |
| \draw (e) -- (g); | |
| \node at (0,1) {$G_2$}; | |
| \end{tikzpicture} | |
| \hspace*{1cm} | |
| \begin{tikzpicture} | |
| \node[circle,draw=black, fill=white] (1) at (0,0) {1}; | |
| \node[circle,draw=black, fill=white] (2) at (-1.5,-1) {2}; | |
| \node[circle,draw=black, fill=white] (3) at (-1.5,-2) {3}; | |
| \node[circle,draw=black, fill=white] (4) at (0,-3) {4}; | |
| \node[circle,draw=black, fill=white] (5) at (1.5,-2) {5}; | |
| \node[circle,draw=black, fill=white] (6) at (1.5,-1) {6}; | |
| \draw (1) -- (5); | |
| \draw (1) -- (4); | |
| \draw (3) -- (5); | |
| \draw (3) -- (4); | |
| \draw (3) -- (2); | |
| \draw (5) -- (6); | |
| \draw (4) -- (6); | |
| \node at (0,1) {$G_3$}; | |
| \end{tikzpicture} | |
| \end{center} | |
| \begin{enumerate}[label=(\alph*)] | |
| \item $G_1$ ist isomorph zu $G_3$ ($G_1\overset{\sim}{=}G_3$) mit folgender Bijektion | |
| \begin{center} | |
| \begin{tabular}{c|cccccc} | |
| $x$ & $a$ & $b$ & $c$ & $d$ & $e$ & $f$ \\ | |
| \hline | |
| $f(x)$ & 1 & 3 & 5 & 4 & 6 & 2 | |
| \end{tabular} | |
| \end{center} | |
| \item $G_1$ und damit auch $G_3$ sind 2-färbbar, $G_2$ ist es nicht, da es einen Kreis ungerader Länge enthält: $b\to g\to c\to b$ | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \node[circle,draw=black, fill=red] (a) at (0,0) {$a$}; | |
| \node[circle,draw=black, fill=red] (b) at (-1.5,-1) {$b$}; | |
| \node[circle,draw=black, fill=blue] (c) at (-1.5,-2) {$c$}; | |
| \node[circle,draw=black, fill=blue] (d) at (0,-3) {$d$}; | |
| \node[circle,draw=black, fill=red] (e) at (1.5,-2) {$e$}; | |
| \node[circle,draw=black, fill=blue] (f) at (1.5,-1) {$f$}; | |
| \draw (a) -- (c); | |
| \draw (a) -- (d); | |
| \draw (b) -- (c); | |
| \draw (b) -- (d); | |
| \draw (b) -- (f); | |
| \draw (c) -- (e); | |
| \draw (d) -- (e); | |
| \node at (0,1) {$G_1$}; | |
| \end{tikzpicture} | |
| \hspace*{1cm} | |
| \begin{tikzpicture} | |
| \node[circle,draw=black, fill=red] (a) at (0,0) {$a$}; | |
| \node[circle,draw=black, fill=red] (b) at (-1.5,-1) {$b$}; | |
| \node[circle,draw=black, fill=green!80!black] (c) at (-1.5,-2) {$c$}; | |
| \node[circle,draw=black, fill=blue] (d) at (-0.66,-3) {$d$}; | |
| \node[circle,draw=black, fill=red] (e) at (0.66,-3) {$e$}; | |
| \node[circle,draw=black, fill=blue] (f) at (1.5,-2) {$f$}; | |
| \node[circle,draw=black, fill=blue] (g) at (1.5,-1) {$g$}; | |
| \draw (a) -- (d); | |
| \draw (a) -- (g); | |
| \draw (b) -- (c); | |
| \draw (b) -- (d); | |
| \draw (b) -- (g); | |
| \draw (c) -- (g); | |
| \draw (d) -- (e); | |
| \draw (e) -- (f); | |
| \draw (e) -- (g); | |
| \node at (0,1) {$G_2$}; | |
| \end{tikzpicture} | |
| \hspace*{1cm} | |
| \begin{tikzpicture} | |
| \node[circle,draw=black, fill=red] (1) at (0,0) {1}; | |
| \node[circle,draw=black, fill=blue] (2) at (-1.5,-1) {2}; | |
| \node[circle,draw=black, fill=red] (3) at (-1.5,-2) {3}; | |
| \node[circle,draw=black, fill=blue] (4) at (0,-3) {4}; | |
| \node[circle,draw=black, fill=blue] (5) at (1.5,-2) {5}; | |
| \node[circle,draw=black, fill=red] (6) at (1.5,-1) {6}; | |
| \draw (1) -- (5); | |
| \draw (1) -- (4); | |
| \draw (3) -- (5); | |
| \draw (3) -- (4); | |
| \draw (3) -- (2); | |
| \draw (5) -- (6); | |
| \draw (4) -- (6); | |
| \node at (0,1) {$G_3$}; | |
| \end{tikzpicture} | |
| \end{center} | |
| \item Bipartit und 2-färbbar sind das gleiche $\Rightarrow$ selbe Antwort wie bei (b) | |
| \end{enumerate} | |
| \end{document} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| \documentclass{article} | |
| \usepackage{amsmath,amssymb} | |
| \usepackage{tikz} | |
| \usepackage{xcolor} | |
| \usepackage[left=2.1cm,right=3.1cm,bottom=3cm,footskip=0.75cm,headsep=0.5cm]{geometry} | |
| \usepackage{enumerate} | |
| \usepackage{enumitem} | |
| \usepackage[utf8]{inputenc} | |
| \renewcommand*{\arraystretch}{1.4} | |
| \title{\textbf{Einführung in die Informatik, Übung 6}} | |
| \author{\textsc{Henry Haustein}} | |
| \date{} | |
| \begin{document} | |
| \maketitle | |
| \section*{Aufgabe 6.1} | |
| \begin{enumerate}[label=(\alph*)] | |
| \item $L=\{ab,abcab,abcab\vert c\vert ab,abcabcab\vert c\vert abcab, abcabcabcabcab\vert c\vert abcabcab\}$ | |
| \item nein, denn $f(0)=f(1)$, aber $0\neq 1$ | |
| \item nein, denn $f(\cdot)\neq c$ | |
| \end{enumerate} | |
| \section*{Aufgabe 6.2} | |
| \begin{enumerate}[label=(\alph*)] | |
| \item nein, denn $ba\in \{a,b\}^\ast$, aber $ba\notin \{a\}^\ast\cdot\{b\}^\ast$ | |
| \item ja, trivial | |
| \item nein, denn $ba\in \{a,b\}^\ast$, aber $ba\notin \{a\}^\ast\cup\{b\}^\ast$ | |
| \end{enumerate} | |
| \section*{Aufgabe 6.3} | |
| \begin{enumerate}[label=(\alph*)] | |
| \item Die Sprache besteht aus den Wörtern $a$, $ba$ und $b$ \\ | |
| $\Rightarrow$ $L=\{a,ba,b\}$ | |
| \item Die Sprache besteht aus dem Wort $a$ und den Wörtern, die mit $b$ enden, wo aber davor mindesten 0 $a$'s stehen \\ | |
| $\Rightarrow$ $L=\{a,a^ib\mid i\ge 0\}$ | |
| \item Die Sprache besteht aus Wörtern, die aus Wiederholungen von $abc$'s gebildet sind, wobei $abc$ mindestens einmal vorkommt \\ | |
| $\Rightarrow$ $L=\{(abc)^n\mid n\ge 1\}$ | |
| \end{enumerate} | |
| \section*{Aufgabe 6.4} | |
| \begin{enumerate}[label=(\alph*)] | |
| \item $(aaa)^\ast$ | |
| \item $(a^+b^+)^5$ | |
| \item $\Sigma^\ast\cdot (aaa)\cdot [\Sigma^\ast\cdot (bab)\cdot\Sigma^\ast\cdot (bab)\cdot\Sigma^\ast]^+\cdot \Sigma^\ast$ | |
| \item $\overline{(abba)}\cdot\Sigma^\ast$ | |
| \item $b^\ast a^\ast$ | |
| \end{enumerate} | |
| \end{document} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| \documentclass{article} | |
| \usepackage{amsmath,amssymb} | |
| \usepackage{tikz} | |
| \usepackage{xcolor} | |
| \usepackage[left=2.1cm,right=3.1cm,bottom=3cm,footskip=0.75cm,headsep=0.5cm]{geometry} | |
| \usepackage{enumerate} | |
| \usepackage{enumitem} | |
| \usepackage[utf8]{inputenc} | |
| \renewcommand*{\arraystretch}{1.4} | |
| \title{\textbf{Einführung in die Informatik, Übung 7}} | |
| \author{\textsc{Henry Haustein}} | |
| \date{} | |
| \begin{document} | |
| \maketitle | |
| \section*{Aufgabe 7.1} | |
| \begin{enumerate}[label=(\alph*)] | |
| \item nein, $abba\notin L(\mathcal{A})$ | |
| \item $w_1$: nein, Endpunkt $q_4$ \\ | |
| $w_2$: nein, von $q_5$ kein Zweig mit $b$ \\ | |
| $w_3$: ja, man bleibt bei $q_6$ | |
| \end{enumerate} | |
| \section*{Aufgabe 7.2} | |
| \begin{enumerate}[label=(\alph*)] | |
| \item $\mathcal{A} = (\{q_0,q_1\},\Sigma,q_0,\Delta_a,\{q_0\})$, mit $\Delta_a$ | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \node[circle,draw=black, fill=white, double] (q0) at (0,0) {$q_0$}; | |
| \node[circle,draw=black, fill=white] (q1) at (3,0) {$q_1$}; | |
| \draw[->] (-1,0) -- (q0); | |
| \draw[->] (q0) to node[midway,above] {$a$} (q1); | |
| \draw[->] (q1) to[bend left=30] node[midway,below] {$a$} (q0); | |
| \draw[->,looseness=4] (q0) to[out=60,in=120] node[midway,above] {$b$} (q0); | |
| \draw[->,looseness=4] (q1) to[out=60,in=120] node[midway,above] {$b$} (q1); | |
| \end{tikzpicture} | |
| \end{center} | |
| \item $\mathcal{B}=(\{q_0,q_1,q_2,q_3\},\Sigma,q_0,\Delta_b,\{q_3\})$ mit $\Delta_b$ | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \node[circle,draw=black, fill=white] (q0) at (0,0) {$q_0$}; | |
| \node[circle,draw=black, fill=white] (q1) at (3,0) {$q_1$}; | |
| \node[circle,draw=black, fill=white] (q2) at (6,0) {$q_2$}; | |
| \node[circle,draw=black, fill=white,double] (q3) at (9,0) {$q_3$}; | |
| \draw[->] (-1,0) -- (q0); | |
| \draw[->] (q0) to node[midway,above] {$b$} (q1); | |
| \draw[->] (q1) to node[midway,above] {$b$} (q2); | |
| \draw[->] (q2) to node[midway,above] {$b$} (q3); | |
| \draw[->,looseness=4] (q0) to[out=60,in=120] node[midway,above] {$a$} (q0); | |
| \draw[->,looseness=4] (q1) to[out=60,in=120] node[midway,above] {$a$} (q1); | |
| \draw[->,looseness=4] (q2) to[out=60,in=120] node[midway,above] {$a$} (q2); | |
| \draw[->,looseness=4] (q3) to[out=60,in=120] node[midway,above] {$a,b$} (q3); | |
| \end{tikzpicture} | |
| \end{center} | |
| \item $\mathcal{C}=(\{q_0,...,q_8\},\Sigma,q_0,\Delta_c,\{q_3,q_6,q_8\})$ mit $\Delta_c$ | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \node[circle,draw=black, fill=white] (q0) at (0,0) {$q_0$}; | |
| \node[circle,draw=black, fill=white] (q1) at (3,1.5) {$q_1$}; | |
| \node[circle,draw=black, fill=white] (q2) at (6,1.5) {$q_2$}; | |
| \node[circle,draw=black, fill=white,double] (q3) at (9,1.5) {$q_3$}; | |
| \node[circle,draw=black, fill=white] (q4) at (3,-1.5) {$q_4$}; | |
| \node[circle,draw=black, fill=white] (q5) at (6,0) {$q_5$}; | |
| \node[circle,draw=black, fill=white,double] (q6) at (9,0) {$q_6$}; | |
| \node[circle,draw=black, fill=white] (q7) at (6,-3) {$q_7$}; | |
| \node[circle,draw=black, fill=white,double] (q8) at (9,-3) {$q_8$}; | |
| \draw[->] (-1,0) -- (q0); | |
| \draw[->] (q0) to node[midway,above left] {$a$} (q1); | |
| \draw[->] (q0) to node[midway,below left] {$b$} (q4); | |
| \draw[->] (q1) to node[midway,above] {$b$} (q2); | |
| \draw[->] (q2) to node[midway,above] {$b$} (q3); | |
| \draw[->] (q4) to node[midway,above left] {$a$} (q5); | |
| \draw[->] (q4) to node[midway,below left] {$b$} (q7); | |
| \draw[->] (q5) to node[midway,above] {$b$} (q6); | |
| \draw[->] (q7) to node[midway,above] {$a$} (q8); | |
| \end{tikzpicture} | |
| \end{center} | |
| \end{enumerate} | |
| \section*{Aufgabe 7.3} | |
| \begin{enumerate}[label=(\alph*)] | |
| \item $\mathcal{A}=(\{q_0,q_1,q_2,q_3\}\times \{p_0,p_1,p_2,p_3\},\Sigma, (q_0,p_0), \Delta_a,\{q_2,q_3\}\times \{p_3\})$ mit $\Delta_a$ | |
| \begin{center} | |
| \begin{tikzpicture}[scale=0.65] | |
| \node[circle,draw=black, fill=white] (q0p0) at (0,0) {$(q_0,p_0)$}; | |
| \node[circle,draw=black, fill=white] (q0p1) at (5,0) {$(q_0,p_1)$}; | |
| \node[circle,draw=black, fill=white] (q0p2) at (10,0) {$(q_0,p_2)$}; | |
| \node[circle,draw=black, fill=white] (q0p3) at (15,0) {$(q_0,p_3)$}; | |
| \node[circle,draw=black, fill=white] (q1p0) at (0,-5) {$(q_1,p_0)$}; | |
| \node[circle,draw=black, fill=white] (q1p1) at (5,-5) {$(q_1,p_1)$}; | |
| \node[circle,draw=black, fill=white] (q1p2) at (10,-5) {$(q_1,p_2)$}; | |
| \node[circle,draw=black, fill=white] (q1p3) at (15,-5) {$(q_1,p_3)$}; | |
| \node[circle,draw=black, fill=white] (q2p0) at (0,-10) {$(q_2,p_0)$}; | |
| \node[circle,draw=black, fill=white] (q2p1) at (5,-10) {$(q_2,p_1)$}; | |
| \node[circle,draw=black, fill=white] (q2p2) at (10,-10) {$(q_2,p_2)$}; | |
| \node[circle,draw=black, fill=white,double] (q2p3) at (15,-10) {$(q_2,p_3)$}; | |
| \node[circle,draw=black, fill=white] (q3p0) at (0,-15) {$(q_3,p_0)$}; | |
| \node[circle,draw=black, fill=white] (q3p1) at (5,-15) {$(q_3,p_1)$}; | |
| \node[circle,draw=black, fill=white] (q3p2) at (10,-15) {$(q_3,p_2)$}; | |
| \node[circle,draw=black, fill=white,double] (q3p3) at (15,-15) {$(q_3,p_3)$}; | |
| \node[gray,circle,draw=gray, fill=white] (q0) at (-5,0) {$q_0$}; | |
| \node[gray,circle,draw=gray, fill=white] (q1) at (-5,-5) {$q_1$}; | |
| \node[gray,circle,draw=gray, fill=white,double] (q2) at (-5,-10) {$q_2$}; | |
| \node[gray,circle,draw=gray, fill=white,double] (q3) at (-5,-15) {$q_3$}; | |
| \node[gray,circle,draw=gray, fill=white] (p0) at (0,5) {$p_0$}; | |
| \node[gray,circle,draw=gray, fill=white] (p1) at (5,5) {$p_1$}; | |
| \node[gray,circle,draw=gray, fill=white] (p2) at (10,5) {$p_2$}; | |
| \node[gray,circle,draw=gray, fill=white,double] (p3) at (15,5) {$p_3$}; | |
| \draw[->] (-1,1) -- (q0p0); | |
| \draw[->] (q0p0) to node[midway,right] {$a$} (q1p0); | |
| \draw[->] (q1p0) to node[midway,right] {$a$} (q2p0); | |
| \draw[->] (q2p0) to node[midway,above right] {$b$} (q3p1); | |
| \draw[->,looseness=4] (q2p0) to[out=150,in=210] node[midway,left] {$a$} (q2p0); | |
| \draw[->,looseness=4] (q3p0) to[out=150,in=210] node[midway,left] {$a$} (q3p0); | |
| \draw[->] (q0p1) to node[midway,above right] {$a$} (q1p3); | |
| \draw[->] (q1p1) to node[midway,above right] {$a$} (q2p3); | |
| \draw[->] (q2p1) to[bend left=20] node[midway,above] {$a$} (q2p3); | |
| \draw[->] (q2p1) to node[midway,above right] {$b$} (q3p2); | |
| \draw[->] (q3p1) to[bend right=30] node[midway,below] {$a$} (q3p3); | |
| \draw[->] (q0p2) to node[midway,above right] {$a$} (q1p3); | |
| \draw[->] (q1p2) to node[midway,above right] {$a$} (q2p3); | |
| \draw[->] (q2p2) to node[midway,above] {$a$} (q2p3); | |
| \draw[->] (q3p2) to node[midway,above] {$a$} (q3p3); | |
| \draw[->] (q0p3) to node[midway,right] {$a$} (q1p3); | |
| \draw[->] (q1p3) to node[midway,right] {$a$} (q2p3); | |
| \draw[->,looseness=4] (q2p3) to[out=30,in=-30] node[midway,right] {$a$} (q2p3); | |
| \draw[->,looseness=4] (q3p3) to[out=30,in=-30] node[midway,right] {$a$} (q3p3); | |
| \draw[gray,->] (-5,1) -- (q0); | |
| \draw[gray,->] (q0) to node[midway,left,gray] {$a$} (q1); | |
| \draw[gray,->] (q1) to node[midway,left,gray] {$a$} (q2); | |
| \draw[gray,->] (q2) to node[midway,left,gray] {$b$} (q3); | |
| \draw[gray,->,looseness=4] (q2) to[out=150,in=210] node[midway,left] {$a$} (q2); | |
| \draw[gray,->,looseness=4] (q3) to[out=150,in=210] node[midway,left] {$a$} (q3); | |
| \draw[gray,->] (-1,5) -- (p0); | |
| \draw[gray,->] (p0) to node[midway,above,gray] {$b$} (p1); | |
| \draw[gray,->] (p1) to node[midway,above,gray] {$b$} (p2); | |
| \draw[gray,->] (p2) to node[midway,above,gray] {$a$} (p3); | |
| \draw[gray,->] (p1) to[bend left=30] node[midway,above,gray] {$a$} (p3); | |
| \draw[gray,->,looseness=4] (p0) to[out=120,in=60] node[midway,above] {$a$} (p0); | |
| \draw[gray,->,looseness=4] (p3) to[out=120,in=60] node[midway,above] {$a$} (p3); | |
| \draw[gray,dashed] (-7,2.5) -- (17,2.5); | |
| \draw[gray,dashed] (-2.7,7) -- (-2.7,-17); | |
| \end{tikzpicture} | |
| \end{center} | |
| \item $\mathcal{B}=(\{q_{01},q_1,q_2,q_3\}\cup \{q_0\},\Sigma,q_0,\Delta_b,\{q_0\})$ mit $\Delta_b$ | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \node[circle,draw=black, fill=white] (q0) at (0,0) {$q_0$}; | |
| \node[circle,draw=black, fill=white] (q01) at (3,0) {$q_{01}$}; | |
| \node[circle,draw=black, fill=white] (q1) at (6,0) {$q_1$}; | |
| \node[circle,draw=black, fill=white,double] (q2) at (9,0) {$q_2$}; | |
| \node[circle,draw=black, fill=white,double] (q3) at (12,0) {$q_3$}; | |
| \draw[->] (-1,0) -- (q0); | |
| \draw[->] (q0) to node[midway,above] {$\varepsilon$} (q01); | |
| \draw[->] (q01) to node[midway,above] {$a$} (q1); | |
| \draw[->] (q1) to node[midway,above] {$a$} (q2); | |
| \draw[->] (q2) to node[midway,above] {$b$} (q3); | |
| \draw[->,looseness=4] (q2) to[out=60,in=120] node[midway,above] {$a$} (q2); | |
| \draw[->,looseness=4] (q3) to[out=60,in=120] node[midway,above] {$a$} (q3); | |
| \draw[->] (q2) to[bend left=20] node[midway,below] {$\varepsilon$} (q0); | |
| \draw[->] (q3) to[bend left=30] node[midway,below] {$\varepsilon$} (q0); | |
| \end{tikzpicture} | |
| \end{center} | |
| Dieser Automat ist noch nicht $\varepsilon$-frei, hier die $\varepsilon$-freie Version: | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \node[circle,draw=black, fill=white] (q0) at (0,0) {$q_0$}; | |
| \node[circle,draw=black, fill=white] (q1) at (3,0) {$q_1$}; | |
| \node[circle,draw=black, fill=white,double] (q2) at (6,0) {$q_2$}; | |
| \node[circle,draw=black, fill=white,double] (q3) at (9,0) {$q_3$}; | |
| \draw[->] (-1,0) -- (q0); | |
| \draw[->] (q0) to node[midway,above] {$a$} (q1); | |
| \draw[->] (q1) to node[midway,above] {$a$} (q2); | |
| \draw[->] (q2) to node[midway,above] {$b$} (q3); | |
| \draw[->,looseness=4] (q2) to[out=60,in=120] node[midway,above] {$a$} (q2); | |
| \draw[->,looseness=4] (q3) to[out=60,in=120] node[midway,above] {$a$} (q3); | |
| \draw[->] (q2) to[bend left=20] node[midway,below] {$a,b$} (q0); | |
| \draw[->] (q3) to[bend left=30] node[midway,below] {$a$} (q0); | |
| \draw[->] (q1) to[bend right=30] node[midway,above] {$a$} (q0); | |
| \end{tikzpicture} | |
| \end{center} | |
| \item $\mathcal{C}=(\{s_0,s_1,s_2,s_3\}\cup \{t_0,...,t_5\}\cup \{q_0\},\Sigma,q_0,\Delta_c, \{s_3\}\cup \{t_3,t_5\})$ mit $\Delta_c$ | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \node[circle,draw=black, fill=white] (q0) at (0,0) {$q_0$}; | |
| \node[circle,draw=black, fill=white] (s0) at (3,3) {$s_0$}; | |
| \node[circle,draw=black, fill=white] (s1) at (6,3) {$s_1$}; | |
| \node[circle,draw=black, fill=white] (s2) at (9,4.5) {$s_2$}; | |
| \node[circle,draw=black, fill=white,double] (s3) at (9,1.5) {$s_3$}; | |
| \node[circle,draw=black, fill=white] (t0) at (3,-3) {$t_0$}; | |
| \node[circle,draw=black, fill=white] (t1) at (6,-3) {$t_1$}; | |
| \node[circle,draw=black, fill=white] (t2) at (6,-6) {$t_2$}; | |
| \node[circle,draw=black, fill=white,double] (t3) at (9,-3) {$t_3$}; | |
| \node[circle,draw=black, fill=white] (t4) at (12,-3) {$t_4$}; | |
| \node[circle,draw=black, fill=white,double] (t5) at (12,-6) {$t_5$}; | |
| \draw[->] (-1,0) -- (q0); | |
| \draw[->] (q0) to node[midway, above left] {$\varepsilon$} (s0); | |
| \draw[->] (q0) to node[midway, below left] {$\varepsilon$} (t0); | |
| \draw[->] (s0) to node[midway,above] {$b$} (s1); | |
| \draw[->] (s1) to node[midway,above left] {$a$} (s2); | |
| \draw[->] (s2) to node[midway,right] {$a$} (s3); | |
| \draw[->] (s3) to node[midway,above right] {$b$} (s1); | |
| \draw[->,looseness=4] (s0) to[out=60,in=120] node[midway,above] {$a$} (s0); | |
| \draw[->] (t0) to node[midway,above] {$a,b$} (t1); | |
| \draw[->] (t1) to[bend left=30] node[midway,right] {$a$} (t2); | |
| \draw[->] (t2) to[bend left=30] node[midway,left] {$a$} (t1); | |
| \draw[->] (t1) to node[midway,above] {$b$} (t3); | |
| \draw[->] (t3) to node[midway,above] {$b$} (t4); | |
| \draw[->] (t4) to node[midway,right] {$b$} (t5); | |
| \draw[->,looseness=4] (t5) to[out=240,in=300] node[midway,below] {$a$} (t5); | |
| \end{tikzpicture} | |
| \end{center} | |
| Dieser Automat ist noch nicht $\varepsilon$-frei, hier die $\varepsilon$-freie Version: | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \node[circle,draw=black, fill=white] (q0) at (0,0) {$q_0$}; | |
| \node[circle,draw=black, fill=white] (s0) at (3,3) {$s_0$}; | |
| \node[circle,draw=black, fill=white] (s1) at (6,3) {$s_1$}; | |
| \node[circle,draw=black, fill=white] (s2) at (9,4.5) {$s_2$}; | |
| \node[circle,draw=black, fill=white,double] (s3) at (9,1.5) {$s_3$}; | |
| \node[circle,draw=black, fill=white] (t0) at (3,-3) {$t_0$}; | |
| \node[circle,draw=black, fill=white] (t1) at (6,-3) {$t_1$}; | |
| \node[circle,draw=black, fill=white] (t2) at (6,-6) {$t_2$}; | |
| \node[circle,draw=black, fill=white,double] (t3) at (9,-3) {$t_3$}; | |
| \node[circle,draw=black, fill=white] (t4) at (12,-3) {$t_4$}; | |
| \node[circle,draw=black, fill=white,double] (t5) at (12,-6) {$t_5$}; | |
| \draw[->] (-1,0) -- (q0); | |
| \draw[->] (q0) to node[midway, above left] {$a$} (s0); | |
| \draw[->] (q0) to node[midway, above right] {$a,b$} (t1); | |
| \draw[->] (s0) to node[midway,above] {$b$} (s1); | |
| \draw[->] (s1) to node[midway,above left] {$a$} (s2); | |
| \draw[->] (s2) to node[midway,right] {$a$} (s3); | |
| \draw[->] (s3) to node[midway,above right] {$b$} (s1); | |
| \draw[->,looseness=4] (s0) to[out=60,in=120] node[midway,above] {$a$} (s0); | |
| \draw[->] (t0) to node[midway,above] {$a,b$} (t1); | |
| \draw[->] (t1) to[bend left=30] node[midway,right] {$a$} (t2); | |
| \draw[->] (t2) to[bend left=30] node[midway,left] {$a$} (t1); | |
| \draw[->] (t1) to node[midway,above] {$b$} (t3); | |
| \draw[->] (t3) to node[midway,above] {$b$} (t4); | |
| \draw[->] (t4) to node[midway,right] {$b$} (t5); | |
| \draw[->,looseness=4] (t5) to[out=240,in=300] node[midway,below] {$a$} (t5); | |
| \end{tikzpicture} | |
| \end{center} | |
| \item $\mathcal{D}=(\{s_0,s_1,s_2,s_3\}\cup \{t_0,...,t_5\},\Sigma,s_0,\Delta_d,\{t_3,t_5\})$ mit $\Delta_d$ | |
| \begin{center} | |
| \begin{tikzpicture}[scale=0.8] | |
| \node[circle,draw=black, fill=white] (s0) at (0,0) {$s_0$}; | |
| \node[circle,draw=black, fill=white] (s1) at (3,0) {$s_1$}; | |
| \node[circle,draw=black, fill=white] (s2) at (6,1.5) {$s_2$}; | |
| \node[circle,draw=black, fill=white] (s3) at (6,-1.5) {$s_3$}; | |
| \node[circle,draw=black, fill=white] (t0) at (9,0) {$t_0$}; | |
| \node[circle,draw=black, fill=white] (t1) at (12,0) {$t_1$}; | |
| \node[circle,draw=black, fill=white] (t2) at (12,-3) {$t_2$}; | |
| \node[circle,draw=black, fill=white,double] (t3) at (15,0) {$t_3$}; | |
| \node[circle,draw=black, fill=white] (t4) at (18,0) {$t_4$}; | |
| \node[circle,draw=black, fill=white,double] (t5) at (18,-3) {$t_5$}; | |
| \draw[->] (-1,0) -- (s0); | |
| \draw[->] (s0) to node[midway,above] {$b$} (s1); | |
| \draw[->] (s1) to node[midway,above left] {$a$} (s2); | |
| \draw[->] (s2) to node[midway,right] {$a$} (s3); | |
| \draw[->] (s3) to node[midway,above right] {$b$} (s1); | |
| \draw[->,looseness=4] (s0) to[out=60,in=120] node[midway,above] {$a$} (s0); | |
| \draw[->] (s3) to node[midway, above left] {$\varepsilon$} (t0); | |
| \draw[->] (t0) to node[midway,above] {$a,b$} (t1); | |
| \draw[->] (t1) to[bend left=30] node[midway,right] {$a$} (t2); | |
| \draw[->] (t2) to[bend left=30] node[midway,left] {$a$} (t1); | |
| \draw[->] (t1) to node[midway,above] {$b$} (t3); | |
| \draw[->] (t3) to node[midway,above] {$b$} (t4); | |
| \draw[->] (t4) to node[midway,right] {$b$} (t5); | |
| \draw[->,looseness=4] (t5) to[out=240,in=300] node[midway,below] {$a$} (t5); | |
| \end{tikzpicture} | |
| \end{center} | |
| Dieser Automat ist noch nicht $\varepsilon$-frei, hier die $\varepsilon$-freie Version: | |
| \begin{center} | |
| \begin{tikzpicture}[scale=0.8] | |
| \node[circle,draw=black, fill=white] (s0) at (0,0) {$s_0$}; | |
| \node[circle,draw=black, fill=white] (s1) at (3,0) {$s_1$}; | |
| \node[circle,draw=black, fill=white] (s2) at (6,1.5) {$s_2$}; | |
| \node[circle,draw=black, fill=white] (s3) at (6,-1.5) {$s_3$}; | |
| \node[circle,draw=black, fill=white] (t0) at (9,0) {$t_0$}; | |
| \node[circle,draw=black, fill=white] (t1) at (12,0) {$t_1$}; | |
| \node[circle,draw=black, fill=white] (t2) at (12,-3) {$t_2$}; | |
| \node[circle,draw=black, fill=white,double] (t3) at (15,0) {$t_3$}; | |
| \node[circle,draw=black, fill=white] (t4) at (18,0) {$t_4$}; | |
| \node[circle,draw=black, fill=white,double] (t5) at (18,-3) {$t_5$}; | |
| \draw[->] (-1,0) -- (s0); | |
| \draw[->] (s0) to node[midway,above] {$b$} (s1); | |
| \draw[->] (s1) to node[midway,above left] {$a$} (s2); | |
| \draw[->] (s2) to node[midway,right] {$a$} (s3); | |
| \draw[->] (s3) to node[midway,above right] {$b$} (s1); | |
| \draw[->,looseness=4] (s0) to[out=60,in=120] node[midway,above] {$a$} (s0); | |
| \draw[->] (s3) to node[midway, below right] {$a,b$} (t1); | |
| \draw[->] (t0) to node[midway,above] {$a,b$} (t1); | |
| \draw[->] (t1) to[bend left=30] node[midway,right] {$a$} (t2); | |
| \draw[->] (t2) to[bend left=30] node[midway,left] {$a$} (t1); | |
| \draw[->] (t1) to node[midway,above] {$b$} (t3); | |
| \draw[->] (t3) to node[midway,above] {$b$} (t4); | |
| \draw[->] (t4) to node[midway,right] {$b$} (t5); | |
| \draw[->,looseness=4] (t5) to[out=240,in=300] node[midway,below] {$a$} (t5); | |
| \end{tikzpicture} | |
| \end{center} | |
| \end{enumerate} | |
| \end{document} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| \documentclass{article} | |
| \usepackage{amsmath,amssymb} | |
| \usepackage{tikz} | |
| \usepackage{xcolor} | |
| \usepackage[left=2.1cm,right=3.1cm,bottom=3cm,footskip=0.75cm,headsep=0.5cm]{geometry} | |
| \usepackage{enumerate} | |
| \usepackage{enumitem} | |
| \usepackage{marvosym} | |
| \usepackage[utf8]{inputenc} | |
| \renewcommand*{\arraystretch}{1.4} | |
| \title{\textbf{Einführung in die Informatik, Übung 8}} | |
| \author{\textsc{Henry Haustein}} | |
| \date{} | |
| \begin{document} | |
| \maketitle | |
| \section*{Aufgabe 8.1} | |
| \begin{enumerate}[label=(\alph*)] | |
| \item $2^Q=\mathcal{P}(Q)=\{\emptyset,\{q_0\},\{q_1\},\{q_2\},\{q_0,q_1\},\{q_0,q_2\},\{q_1,q_2\},\{q_0,q_1,q_2\}\}$, $F'=\{\{q_1\},\{q_0,q_1\},\{q_1,q_2\},\{q_0,q_1,q_2\}\}$ $\Rightarrow$ $\mathcal{A}'=(2^Q,\Sigma,\{q_0\},\delta,F')$ mit $\delta$ | |
| \begin{center} | |
| \begin{tikzpicture}[scale=0.95] | |
| \node[circle,draw=black, fill=white] (q0) at (-6,0) {$\{q_0\}$}; | |
| \node[circle,draw=black, fill=white,double] (q1) at (0,2) {$\{q_1\}$}; | |
| \node[circle,draw=black, fill=white] (q2) at (3,2) {$\{q_2\}$}; | |
| \node[circle,draw=black, fill=white,double] (q0q1) at (-3,0) {$\{q_0,q_1\}$}; | |
| \node[circle,draw=black, fill=white] (q0q2) at (0,-2) {$\{q_0,q_2\}$}; | |
| \node[circle,draw=black, fill=white,double] (q1q2) at (6,0) {$\{q_1,q_2\}$}; | |
| \node[circle,draw=black, fill=white,double] (q0q1q2) at (0,-6) {$\{q_0,q_1,q_2\}$}; | |
| \node[circle,draw=black, fill=white] (e) at (0,6) {$\emptyset$}; | |
| \draw[->] (-7,0) -- (q0); | |
| \draw[->] (q0) to[bend left=30] node[midway,above] {$a$} (q0q1); | |
| \draw[->] (q0q1) to[bend left=30] node[midway,below] {$c$} (q0); | |
| \draw[->] (q0) to node[midway,above left] {$b$} (e); | |
| \draw[->] (q0q1q2) to[bend left=20] node[midway,above right] {$c$} (q0); | |
| \draw[->] (q0q1) to node[midway,below left] {$b$} (q0q2); | |
| \draw[->] (q0q2) to[bend left=30] node[midway,below] {$c$} (q0); | |
| \draw[->] (q0q2) to[bend left=30] node[midway,left] {$b$} (q1); | |
| \draw[->] (q1) to[bend left=30] node[midway,right] {$b$} (q0q2); | |
| \draw[->] (q0q2) to node[midway,left] {$a$} (q0q1q2); | |
| \draw[->] (q1) to node[midway,left] {$a,c$} (e); | |
| \draw[->] (q2) to node[midway,above] {$b$} (q1); | |
| \draw[->] (q1q2) to node[midway,above right] {$a$} (q2); | |
| \draw[->] (q1q2) to node[midway,above left] {$b$} (q0q1q2); | |
| \draw[->] (q1q2) to[bend right=10] node[midway,above right] {$c$} (e); | |
| \draw[->] (q2) to node[midway,below left] {$c$} (e); | |
| \draw[->,looseness=4] (q0) to[out=60,in=120] node[midway,above] {$c$} (q0); | |
| \draw[->,looseness=4] (q0q1) to[out=60,in=120] node[midway,above] {$a$} (q0q1); | |
| \draw[->,looseness=4] (q2) to[out=-60,in=-120] node[midway,below] {$a$} (q2); | |
| \draw[->,looseness=4] (q0q1q2) to[out=-60,in=-120] node[midway,below] {$a,b$} (q0q1q2); | |
| \draw[->,looseness=4] (e) to[out=60,in=120] node[midway,above] {$a,b,c$} (e); | |
| \end{tikzpicture} | |
| \end{center} | |
| \item Den Automaten, der die Sprache $L(\mathcal{A})$ akzeptiert, konstruiert man, indem man den zugehörigen DEA konstruiert (Aufgabe (a)) und die Endzustände anpasst: $F=Q\setminus F$ | |
| \begin{center} | |
| \begin{tikzpicture}[scale=0.95] | |
| \node[circle,draw=black, fill=white,double] (q0) at (-6,0) {$\{q_0\}$}; | |
| \node[circle,draw=black, fill=white] (q1) at (0,2) {$\{q_1\}$}; | |
| \node[circle,draw=black, fill=white,double] (q2) at (3,2) {$\{q_2\}$}; | |
| \node[circle,draw=black, fill=white] (q0q1) at (-3,0) {$\{q_0,q_1\}$}; | |
| \node[circle,draw=black, fill=white,double] (q0q2) at (0,-2) {$\{q_0,q_2\}$}; | |
| \node[circle,draw=black, fill=white] (q1q2) at (6,0) {$\{q_1,q_2\}$}; | |
| \node[circle,draw=black, fill=white] (q0q1q2) at (0,-6) {$\{q_0,q_1,q_2\}$}; | |
| \node[circle,draw=black, fill=white] (e) at (0,6) {$\emptyset$}; | |
| \draw[->] (-7,0) -- (q0); | |
| \draw[->] (q0) to[bend left=30] node[midway,above] {$a$} (q0q1); | |
| \draw[->] (q0q1) to[bend left=30] node[midway,below] {$c$} (q0); | |
| \draw[->] (q0) to node[midway,above left] {$b$} (e); | |
| \draw[->] (q0q1q2) to[bend left=20] node[midway,above right] {$c$} (q0); | |
| \draw[->] (q0q1) to node[midway,below left] {$b$} (q0q2); | |
| \draw[->] (q0q2) to[bend left=30] node[midway,below] {$c$} (q0); | |
| \draw[->] (q0q2) to[bend left=30] node[midway,left] {$b$} (q1); | |
| \draw[->] (q1) to[bend left=30] node[midway,right] {$b$} (q0q2); | |
| \draw[->] (q0q2) to node[midway,left] {$a$} (q0q1q2); | |
| \draw[->] (q1) to node[midway,left] {$a,c$} (e); | |
| \draw[->] (q2) to node[midway,above] {$b$} (q1); | |
| \draw[->] (q1q2) to node[midway,above right] {$a$} (q2); | |
| \draw[->] (q1q2) to node[midway,above left] {$b$} (q0q1q2); | |
| \draw[->] (q1q2) to[bend right=10] node[midway,above right] {$c$} (e); | |
| \draw[->] (q2) to node[midway,below left] {$c$} (e); | |
| \draw[->,looseness=4] (q0) to[out=60,in=120] node[midway,above] {$c$} (q0); | |
| \draw[->,looseness=4] (q0q1) to[out=60,in=120] node[midway,above] {$a$} (q0q1); | |
| \draw[->,looseness=4] (q2) to[out=-60,in=-120] node[midway,below] {$a$} (q2); | |
| \draw[->,looseness=4] (q0q1q2) to[out=-60,in=-120] node[midway,below] {$a,b$} (q0q1q2); | |
| \draw[->,looseness=4] (e) to[out=60,in=120] node[midway,above] {$a,b,c$} (e); | |
| \end{tikzpicture} | |
| \end{center} | |
| \end{enumerate} | |
| \section*{Aufgabe 8.2} | |
| \begin{enumerate}[label=(\alph*)] | |
| \item ist erkennbar, der zugehörige Automat ist $\mathcal{A}=(\{q_0,...,q_5\},\{a,b\},q_0,\Delta_a,\{q_5\})$ mit $\Delta_a$ | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \node[circle,draw=black, fill=white] (q0) at (0,0) {$q_0$}; | |
| \node[circle,draw=black, fill=white] (q1) at (2,0) {$q_1$}; | |
| \node[circle,draw=black, fill=white] (q2) at (4,0) {$q_2$}; | |
| \node[circle,draw=black, fill=white] (q3) at (6,0) {$q_3$}; | |
| \node[circle,draw=black, fill=white] (q4) at (8,0) {$q_4$}; | |
| \node[circle,draw=black, fill=white,double] (q5) at (10,0) {$q_5$}; | |
| \draw[->] (-1,0) -- (q0); | |
| \draw[->] (q0) to node[midway,above] {$b$} (q1); | |
| \draw[->] (q1) to node[midway,above] {$b$} (q2); | |
| \draw[->] (q2) to node[midway,above] {$b$} (q3); | |
| \draw[->] (q3) to node[midway,above] {$b$} (q4); | |
| \draw[->] (q4) to node[midway,above] {$b$} (q5); | |
| \draw[->,looseness=4] (q0) to[out=60,in=120] node[midway,above] {$a$} (q0); | |
| \end{tikzpicture} | |
| \end{center} | |
| \item ist erkennbar, der zugehörige Automat ist $\mathcal{B}=(\{q_0,q_1,q_2,q_3\},\{a\},q_0,\Delta_b,\{q_3\})$ mit $\Delta_b$ | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \node[circle,draw=black, fill=white] (q0) at (0,0) {$q_0$}; | |
| \node[circle,draw=black, fill=white] (q1) at (2,0) {$q_1$}; | |
| \node[circle,draw=black, fill=white] (q2) at (4,0) {$q_2$}; | |
| \node[circle,draw=black, fill=white,double] (q3) at (6,0) {$q_3$}; | |
| \draw[->] (-1,0) -- (q0); | |
| \draw[->] (q0) to node[midway,above] {$a$} (q1); | |
| \draw[->] (q1) to node[midway,above] {$a$} (q2); | |
| \draw[->] (q2) to node[midway,above] {$a$} (q3); | |
| \draw[->] (q3) to[bend left=30] node[midway,below] {$\varepsilon$} (q0); | |
| \end{tikzpicture} | |
| \end{center} | |
| \item ist nicht erkennbar. Angenommen es gäbe einen NEA, der $L_3$ erkennt. Vertauscht man in diesem $a\leftrightarrow b$, so erhält man einen NEA, der $\{a^nb^n\mid n\ge 0\}$ akzeptiert. Da aber $\{a^nb^n\mid n\ge 0\}$ nicht erkennbar ist, kann es dieses Automaten auch nicht geben $\Rightarrow$ \Lightning | |
| \item vom Gefühl her würde ich sagen, dass diese Sprache nicht erkennbar ist | |
| \end{enumerate} | |
| \section*{Aufgabe 8.3} | |
| \begin{enumerate}[label=(\alph*)] | |
| \item nein, denn es ist nicht möglich ein einzelnes $a$ zu erzeugen \\ | |
| ja, denn | |
| \begin{center} | |
| \begin{tikzpicture} | |
| \node at (0,0) (0) {S}; | |
| \node at (1,0) (1) {A}; | |
| \node at (1.5,0) (2) {S}; | |
| \node at (2,0) (3) {B}; | |
| \node at (0.6,-1) (4) {aa}; | |
| \node at (1.3,-1) (5) {D}; | |
| \node at (1.7,-1) (6) {C}; | |
| \node at (2.4,-1) (7) {b}; | |
| \node at (0.7,-2) (8) {d}; | |
| \node at (1,-2) (9) {D}; | |
| \node at (1.7,-2) (10) {c}; | |
| \node at (2,-2) (11) {C}; | |
| \node at (2.3,-2) (12) {c}; | |
| \node at (0.7,-3) (13) {d}; | |
| \node at (1,-3) (14) {D}; | |
| \node at (2,-3) (15) {$\varepsilon$}; | |
| \node at (1,-4) (16) {d}; | |
| \draw[->] (0) -- (1); | |
| \draw[->] (1) -- (4); | |
| \draw[->] (2) -- (1.5,-0.85); | |
| \draw[->] (3) -- (7); | |
| \draw[->] (5) -- (0.85,-1.8); | |
| \draw[->] (6) -- (11); | |
| \draw[->] (9) -- (0.85,-2.8); | |
| \draw[->] (11) -- (15); | |
| \draw[->] (14) -- (16); | |
| \end{tikzpicture} | |
| \end{center} | |
| nein, $c$'s lassen sich nicht erzeugen, ohne $d$'s mit zu erzeugen | |
| \item $L(G)=\{a^{2n}d^mc^kb^n\mid n,m\ge 1,k\ge 0\}$ | |
| \end{enumerate} | |
| \section*{Aufgabe 8.4} | |
| \begin{enumerate}[label=(\alph*)] | |
| \item $G=(\{S,A,B\},\{a,b\},P_a,S)$ mit $P_a=\{S\to AB, A\to a, B\to bb, S\to\epsilon\}$ | |
| \item $G=(\{S,A,B\},\{a,b\},P_b,S)$ mit $P_b=\{S\to aSb,S\to A,S\to B,A\to Aa,A\to a,B\to Bb,B\to b\}$ | |
| \item $G=(\{S,A,B,C,D\},\{a,b,c\},P_c,S)$ mit $P_c=\{S\to ABDCA,D\to BDC,D\to A,A\to\varepsilon,A\to aA,B\to b,C\to c\}$ | |
| \end{enumerate} | |
| \end{document} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| \documentclass{article} | |
| \usepackage{amsmath,amssymb} | |
| \usepackage{tikz} | |
| \usepackage{xcolor} | |
| \usepackage[left=2.1cm,right=3.1cm,bottom=3cm,footskip=0.75cm,headsep=0.5cm]{geometry} | |
| \usepackage{enumerate} | |
| \usepackage{enumitem} | |
| \usepackage{marvosym} | |
| \usepackage{tabularx} | |
| \usepackage[utf8]{inputenc} | |
| \renewcommand*{\arraystretch}{1.4} | |
| \newcolumntype{L}[1]{>{\raggedright\arraybackslash}p{#1}} | |
| \newcolumntype{R}[1]{>{\raggedleft\arraybackslash}p{#1}} | |
| \newcolumntype{C}[1]{>{\centering\let\newline\\\arraybackslash\hspace{0pt}}m{#1}} | |
| \title{\textbf{Einführung in die Informatik, Übung 9}} | |
| \author{\textsc{Henry Haustein}} | |
| \date{} | |
| \begin{document} | |
| \maketitle | |
| \section*{Aufgabe 9.1} | |
| \begin{enumerate}[label=(\alph*)] | |
| \item $(N_1\cup \{S\}\cup N_2 \cup \{T\},\Sigma,P_1\cup \{S\to\varepsilon,S\to SS_1\}\cup P_2\cup \{T\to SS_2\},T)$ | |
| \item Veränderungen in den Grammatiken sind mit \textcolor{red}{rot} dargestellt.\\ | |
| $\cdot$: $(N_1\cup N_2\cup \{S\},\Sigma,P_1\cup P_2\cup \{S\to S_1S_2\},S)$ \\ | |
| $(\cdot)^\ast$: $(N_1\cup N_2\cup \{S\}\cup \textcolor{red}{\{T\}},\Sigma,P_1\cup P_2\cup \{S\to S_1S_2\}\cup \textcolor{red}{\{T\to\varepsilon,T\to TS\}},\textcolor{red}{T})$ \\ | |
| $(\cdot)^\ast\cup$: $(N_1\cup N_2\cup \{S\}\cup \{T\}\cup \textcolor{red}{\{A\}},\Sigma,P_1\cup P_2\cup \{S\to S_1S_2\}\cup \{T\to\varepsilon,T\to TS\}\cup \textcolor{red}{\{A\to T,A\to S_1\}},\textcolor{red}{A})$ | |
| \end{enumerate} | |
| \section*{Aufgabe 9.2} | |
| \begin{enumerate}[label=(\alph*)] | |
| \item $T_1=\{S,R\}$, $T_2=\{S,R,V\}$, $T_3=\{S,R,V,W\}=T_4=...$ | |
| \item $ab\in L(G)\Rightarrow L(G)\neq\emptyset$ (alternative Begründung: $S\in T_3=T_4=...$) | |
| \end{enumerate} | |
| \section*{Aufgabe 9.3} | |
| \begin{center} | |
| \begin{tabular}{l|L{3cm}|L{3cm}|L{3cm}|L{3cm}} | |
| & $P_1$ & $P_2$ & $P_3$ & $P_4$ \\ | |
| \hline | |
| kontextfrei & \checkmark & \checkmark & \checkmark & \checkmark \\ | |
| \hline | |
| rechtslinear & mehr als 1 nichtterminales Symbol & \checkmark & mehr als 1 nichtterminales Symbol & mehr als 1 nichtterminales Symbol \\ | |
| \hline | |
| Chomsky-Normalform & $B\to BB$ geht nicht & $S\to bB$ geht nicht & $A\to aB$ geht nicht & $A\to SC$ geht nicht, wenn $S\to\epsilon\in P_4$ | |
| \end{tabular} | |
| \end{center} | |
| \section*{Aufgabe 9.4} | |
| \begin{enumerate}[label=(\alph*)] | |
| \item siehe Tabelle\\ | |
| \begin{center} | |
| \begin{tabular}{l|L{3cm}|L{3cm}|L{3cm}|L{3cm}} | |
| & \textbf{Typ 0} & \textbf{Typ 1} & \textbf{Typ 2} & \textbf{Typ 3} \\ | |
| \hline | |
| $G_1$ & \checkmark & \checkmark & $Ca\to aC\notin N\times (N\cup\Sigma)^\ast$ & nicht rechtslinear \\ | |
| \hline | |
| $G_2$ & \checkmark & \checkmark & \checkmark & nicht rechtslinear \\ | |
| \hline | |
| $G_3$ & \checkmark & \checkmark & \checkmark & \checkmark | |
| \end{tabular} | |
| \end{center} | |
| \item Vermutung: $G$ vom Typ $i$ $\Leftrightarrow$ $L(G)$ vom Typ $i$. Zumindest für den Typ 3 scheint dies zu stimmen. | |
| \end{enumerate} | |
| \section*{Aufgabe 9.5} | |
| \begin{enumerate}[label=(\alph*)] | |
| \item $aaabba\in L(G)$ | |
| \begin{center} | |
| \begin{tabular}{c|cccccc} | |
| & $a$ & $a$ & $a$ & $b$ & $b$ & $a$ \\ | |
| & 1 & 2 & 3 & 4 & 5 & 6 \\ | |
| \hline | |
| 1 & $A,B$ & $S,M$ & $X$ & $S,M$ & $X$ & $S,M$ \\ | |
| 2 & & $A,B$ & $S,M$ & $X$ & $S,M$ & $X$ \\ | |
| 3 & & & $A,B$ & $S,M$ & $X$ & $\emptyset$ \\ | |
| 4 & & & & $B$ & $\emptyset$ & $\emptyset$ \\ | |
| 5 & & & & & $B$ & $\emptyset$ \\ | |
| 6 & & & & & & $A,B$ | |
| \end{tabular} | |
| \end{center} | |
| \item $aabbaa\notin L(G)$ | |
| \begin{center} | |
| \begin{tabular}{c|cccccc} | |
| & $a$ & $a$ & $b$ & $b$ & $a$ & $a$ \\ | |
| & 1 & 2 & 3 & 4 & 5 & 6 \\ | |
| \hline | |
| 1 & $A,B$ & $S,M$ & $X$ & $S,M$ & $X$ & $\emptyset$ \\ | |
| 2 & & $A,B$ & $S,M$ & $X$ & $\emptyset$ & $\emptyset$ \\ | |
| 3 & & & $B$ & $\emptyset$ & $\emptyset$ & $\emptyset$ \\ | |
| 4 & & & & $B$ & $\emptyset$ & $\emptyset$ \\ | |
| 5 & & & & & $A,B$ & $S,M$ \\ | |
| 6 & & & & & & $A,B$ | |
| \end{tabular} | |
| \end{center} | |
| \end{enumerate} | |
| \end{document} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment