\documentclass{article}

\usepackage{gastex}
\usepackage[usenames]{color}
\usepackage[T1]{fontenc}

\renewcommand{\labelenumi}{\alph{enumi})}
\renewcommand{\labelenumii}{\arabic{enumii})}

\begin{document}

\textbf{Aufgabe 3.2.6.:}\\
Sei $A = (Q, \Sigma, \delta, q_{0}, q_{f})$ ein $\varepsilon$-NEA, derart dass es keine zu $q_{0}$ hinführenden und keine von $q_{f}$ ausgehenden Übergänge gibt. Beschreiben Sie für jede der folgenden Modifikationen  von $A$ die akzeptierte Sprache als Modifikation von $L = L(A)$:\\

\begin{enumerate}
\item%Aufgabe a)
Der Automat, der aus A konstruiert wird, indem ein $\varepsilon$-Übergang von $q_{f}$ nach $q_{0}$ hinzugefügt wird.

\item%Aufgabe b)
Der Automat, der aus A konstruiert wird, indem $\varepsilon$-Übergänge von $q_{0}$ zu jedem Zustand, der von $q_{0}$ erreichbar ist, auf einem Pfad, dessen Beschriftung Zeichen aus $\Sigma$ sowie $\varepsilon$ enthalten können

\item%Aufgabe c)
Der Automat, der aus A konstruiert wird, in dem $\varepsilon$-Übergänge von jedem Zustand zu $q_{f}$ hinzugefügt werden, von denen aus $q_{f}$ auf irgendeinem Pfad erreichbar ist.

\item%Aufgabe d)
Der Automat, der aus A konstruiert wird, indem die unter b) und c) geforderte Modifikationen ausgeführt werden.

\end{enumerate}

\textbf{Lösung:}\\
\begin{enumerate}
%Lösung zu a)-------------------------------------------------------------------------------------------------------------------------------------------
\item
Sei $A_{mod}$ der modifizierte, aus $A$ konstruierte $\varepsilon$-NEA. Wird $\varepsilon$-Übergang von $q_{f}$ nach $q_{0}$ hinzugefügt, dann muss der Automat mindestens einmal Zustand $q_{f}$ erreichen, damit er akzeptiert. Ist er einmal in $q_{f}$ kann er durch den hinzugefügten $\varepsilon$-Übergang "annehmen" die Zeichenreihe sei noch nicht beendet, und erwarten, dass noch einmal die zu $q_{f}$ führende Zeichenreihe folgt. Ist $q_{f}$ erreicht, wiederholt sich dieses Schema jedesmal, wenn eine zu $q_{f}$ führende Zeichenreihe eingegeben wurde.\\
Das bedeutet:\\
\begin{equation}
L(A_{mod}) = L(A)L(A)^{\ast}
\end{equation}

%Lösung zu b)-------------------------------------------------------------------------------------------------------------------------------------------
\item
Der Automat $A$ sehe wie folgt aus.
\begin{center}
    \unitlength=4pt
    \begin{picture}(75, 6)(0,-1)
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=0}
    \thinlines
    \node[Nmarks=i,iangle=180](A0)(0,0){$0$}
    \node(A1)(15,0){$1$}
    \node(A2)(30,0){$2$}
    \node(A3)(45,0){}     
    \node(Anm)(60,0){}      
    \node[Nmarks=r](An)(75,0){$n$}
    \drawedge(A0,A1){$a_1$}
    \drawedge(A1,A2){$a_2$}
    \drawedge(A2,A3){$a_3$}
     \put(50,0){$\ldots$}
    \drawedge(Anm,An){$a_n$}
    \end{picture}
  \end{center}
Dieser Automat akzeptiert alle Zeichenreihen, die die Form $a_{1}a_{2}a_{3}...a_{n}$ haben. Fügt man jetzt $\varepsilon$-Übergänge hinzu, von $q_{0}$ zu jedem Zustand, der von $q_{0}$ erreichbar ist, dann sieht der Automat $A_{mod}$ wie folgt aus:
\begin{center}
    \unitlength=4pt
    \begin{picture}(75, 25)(0,-1)
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=0}
    \thinlines
    \node[Nmarks=i,iangle=180](A0)(0,0){$0$}
    \node(A1)(15,0){$1$}
    \node(A2)(30,0){$2$}
    \node(A3)(45,0){}     
    \node(Anm)(60,0){}      
    \node[Nmarks=r](An)(75,0){$n$}
    \drawedge(A0,A1){$a_1$}
    \drawedge(A1,A2){$a_2$}
    \drawedge(A2,A3){$a_3$}
     \put(50,0){$\ldots$}
    \drawedge(Anm,An){$a_n$}
    
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=5}
    \drawedge(A0,A1){$\varepsilon$}
    
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=10}
    \drawedge(A0,A2){$\varepsilon$}
    
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=15}
    \drawedge(A0,A3){$\varepsilon$}
    
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=20}
    \drawedge(A0,Anm){$\varepsilon$}
    
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=25}
    \drawedge(A0,An){$\varepsilon$}
    \end{picture}
  \end{center}

Dieser Automat akzeptiert alle Zeichenreihen, die folgender Form sind:
\begin{enumerate}
\item[1)]
$a_{1}a_{2}a_{3}...a_{n}$

\item[2)]
$a_{2}a_{3}...a_{n}$

\item[3)]
$a_{3}...a_{n}$
\item[$$]
...

\item[n)]
$a_{n}$

\item[n+1)]
$\varepsilon$
\end{enumerate}
Die Sprache $L(A_{mod})$ ist demnach die Menge aller Suffixe von den Elementen in $L(A)$.

%Lösung zu c)-------------------------------------------------------------------------------------------------------------------------------------------
\item
Der Automat $A$ sehe wie folgt aus.
\begin{center}
    \unitlength=4pt
    \begin{picture}(75, 6)(0,-1)
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=0}
    \thinlines
    \node[Nmarks=i,iangle=180](A0)(0,0){$0$}
    \node(A1)(15,0){$1$}
    \node(A2)(30,0){$2$}
    \node(A3)(45,0){}     
    \node(Anm)(60,0){}      
    \node[Nmarks=r](An)(75,0){$n$}
    \drawedge(A0,A1){$a_1$}
    \drawedge(A1,A2){$a_2$}
    \drawedge(A2,A3){$a_3$}
     \put(50,0){$\ldots$}
    \drawedge(Anm,An){$a_n$}
    \end{picture}
  \end{center}
Dieser Automat akzeptiert alle Zeichenreihen, die die Form $a_{1}a_{2}a_{3}...a_{n}$ haben. Fügt man jetzt $\varepsilon$-Übergänge hinzu, von jedem $q_{i}$ zu $q_{f}$, $q_{f}$ von $q_{i}$ aus auf irgendeinem Pfad erreichbar ist, dann sieht der modifizierte Automat $A_{mod}$ wie folgt aus:
\begin{center}
    \unitlength=4pt
    \begin{picture}(75, 25)(0,-1)
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=0}
    \thinlines
    \node[Nmarks=i,iangle=180](A0)(0,0){$0$}
    \node(A1)(15,0){$1$}
    \node(A2)(30,0){$2$}
    \node(A3)(45,0){}     
    \node(Anm)(60,0){}      
    \node[Nmarks=r](An)(75,0){$n$}
    \drawedge(A0,A1){$a_1$}
    \drawedge(A1,A2){$a_2$}
    \drawedge(A2,A3){$a_3$}
     \put(50,0){$\ldots$}
    \drawedge(Anm,An){$a_n$}
   
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=25}
    \drawedge(A0,An){$\varepsilon$}
    
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=20}
    \drawedge(A1,An){$\varepsilon$}
    
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=15}
    \drawedge(A2,An){$\varepsilon$}
    
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=10}
    \drawedge(A3,An){$\varepsilon$}
    
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=5}
    \drawedge(Anm,An){$\varepsilon$}
    \end{picture}
  \end{center}
  \newpage
 Dieser Automat akzeptiert alle Zeichenreihen, die folgender Form sind:
\begin{enumerate}
\item[1)]
$a_{1}a_{2}a_{3}...a_{n-1}$

\item[2)]
$a_{1}a_{2}a_{3}...a_{n-2}$

\item[3)]
$a_{1}a_{2}a_{3}...a_{n-3}$
\item[$$]
...
\item[n-1)]
$a_{1}a_{2}$
\item[n)]
$a_{1}$

\item[n+1)]
$\varepsilon$
\end{enumerate}
Die Sprache $L(A_{mod})$ ist demnach die Menge aller Prefixe von den Elementen in $L(A)$.

%Lösung zu d)-------------------------------------------------------------------------------------------------------------------------------------------
\item
Der Automat $A$ sehe wie folgt aus.
\begin{center}
    \unitlength=4pt
    \begin{picture}(75, 6)(0,-1)
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=0}
    \thinlines
    \node[Nmarks=i,iangle=180](A0)(0,0){$0$}
    \node(A1)(15,0){$1$}
    \node(A2)(30,0){$2$}
    \node(A3)(45,0){}     
    \node(Anm)(60,0){}      
    \node[Nmarks=r](An)(75,0){$n$}
    \drawedge(A0,A1){$a_1$}
    \drawedge(A1,A2){$a_2$}
    \drawedge(A2,A3){$a_3$}
     \put(50,0){$\ldots$}
    \drawedge(Anm,An){$a_n$}
    \end{picture}
  \end{center}
Dieser Automat akzeptiert alle Zeichenreihen, die die Form $a_{1}a_{2}a_{3}...a_{n}$ haben. Fügt man jetzt $\varepsilon$-Übergänge hinzu, von jedem $q_{i}$ zu $q_{f}$, $q_{f}$ von $q_{i}$ aus auf irgendeinem Pfad erreichbar ist, dann sieht der modifizierte Automat $A_{mod}$ wie folgt aus:
\begin{center}
    \unitlength=4pt
    \begin{picture}(75, 25)(0,-1)
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=0}
    \thinlines
    \node[Nmarks=i,iangle=180](A0)(0,0){$0$}
    \node(A1)(15,0){$1$}
    \node(A2)(30,0){$2$}
    \node(A3)(45,0){}     
    \node(Anm)(60,0){}      
    \node[Nmarks=r](An)(75,0){$n$}
    \drawedge(A0,A1){$a_1$}
    \drawedge(A1,A2){$a_2$}
    \drawedge(A2,A3){$a_3$}
     \put(50,0){$\ldots$}
    \drawedge(Anm,An){$a_n$}
    
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=5}
    \drawedge(A0,A1){$\varepsilon$}
    
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=10}
    \drawedge(A0,A2){$\varepsilon$}
    
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=15}
    \drawedge(A0,A3){$\varepsilon$}
    
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=20}
    \drawedge(A0,Anm){$\varepsilon$}
    
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=25}
    \drawedge(A0,An){$\varepsilon$}
    
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=25}
    \drawedge(A0,An){$\varepsilon$}
    
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=20}
    \drawedge(A1,An){$\varepsilon$}
    
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=15}
    \drawedge(A2,An){$\varepsilon$}
    
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=10}
    \drawedge(A3,An){$\varepsilon$}
    
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=5}
    \drawedge(Anm,An){$\varepsilon$}
    \end{picture}
  \end{center}
  
  Die Sprache $L(A_{mod})$ dieses Automaten akzeptiert alle Zeichenreihen, die Teilzeichenreihen von Elementen in $L(A)$ sind.
\end{enumerate}



\end{document}