\documentclass[10pt]{article}

\usepackage{ngerman,a4}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}
\usepackage{graphicx}

\thispagestyle{empty}

\title{Theoretische Informatik - Übungsblatt 9 \\
        Übungsgruppe 7 - Mi, 16-18 Uhr \\
        Elena Kvassova}
\author{Jan Hendrik Dithmar (Matrikelnummer 2031259) \\
        Dirk Heine (Matrikelnummer 2030941)}
\date{}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\bild}[4]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[width=#1cm]{../#2}\\[0.2cm]
			\caption{#3}
			\label{#4}
	\end{figure}
	}

\maketitle

\newpage

\section*{Aufgabe 1}
Gegeben sind zwei reguläre Sprachen $L_1$ und $L_2$. Für diese Sprachen sei
jeweils ein endlicher Automat $A_1$ bzw. $A_2$ gegeben (die Existenz dieser
Automaten ergibt sich aus der Regularität der Sprachen). Der Automat $A_1$
\begin{itemize}
    \item arbeite auf dem Alphabet $\Sigma_1$,
    \item habe die Zustandsmenge $Q_1 = \{q_0,\ldots,q_n\}$,
    \item habe den Startzustand $q_0$,
    \item habe die Menge $F_1$ der akzeptierenden Endzustände und
    \item habe die Zustandsüberführungsfunktion $\delta_1: Q_1 \times \Sigma_1 \rightarrow Q_1$.
\end{itemize}
Der Automat $A_2$
\begin{itemize}
    \item arbeite auf dem Alphabet $\Sigma_2$,
    \item habe die Zustandsmenge $Q_2 = \{r_0,\ldots,r_m\}$,
    \item habe den Startzustand $r_0$,
    \item habe die Menge $F_2$ der akzeptierenden Endzustände und
    \item habe die Zustandsüberführungsfunktion $\delta_2: Q_2 \times \Sigma_2 \rightarrow Q_2$.
\end{itemize}
Wir können aus diesen beiden Automaten $A_1$ und $A_2$ einen neuen endlichen
Automaten $A$ bauen, der die Sprache $shuffle(L_1,L_2)$ akzeptiert. Dieser
neue Automat $A$
\begin{itemize}
    \item arbeitet auf dem Alphabet $\Sigma = \Sigma_1 \cup \Sigma_2$,
    \item hat die Zustandsmenge $Q = Q_1 \times Q_2 \times \{1,2,3\}$,
    \item hat den Startzustand $(q_0,r_0,1)$,
    \item hat die Menge $F = \{(q_i,r_j,1) \:\:|\:\: q_i \in F_1 \wedge r_i \in F_2\}$ der akzeptierenden Endzustände und
    \item hat die Zustandsüberführungsfunktion $\delta: Q \times \Sigma \rightarrow Q$ (siehe unten).
\end{itemize}
Jeder Zustand von $A$ ist ein Tupel, 
\begin{itemize}
    \item dessen erste Komponente aussagt, in welchem Zustand sich der
          (simulierte) Automat $A_1$ befindet,
    \item dessen zweite Komponente aussagt, in welchem Zustand sich der
          (simulierte) Automat $A_2$ befindet und
    \item dessen dritte Komponente folgende Bedeutung hat:
          \begin{itemize}
              \item der Wert 1 bedeutet, dass $A_1$ das nächste Zeichen
                    verarbeiten muss
              \item der Wert 2 bedeutet, dass $A_2$ das nächste Zeichen
                    verarbeiten muss
              \item der Wert 3 bedeutet, dass bereits ein Fehler aufgetreten
                    ist und dass das Wort auf \emph{keinen} Fall mehr
                    akzeptiert werden kann
          \end{itemize}
\end{itemize}
Indem wir nur Zustände zum Endzustand erklären, für die sowohl der (simulierte)
$A_1$ als auch der (simulierte) $A_2$ jeweils in einem ihrer Endzustände sind
als auch die letzte Komponente des Zustands gleich 1 ist, stellen wir sicher,
dass bei Erreichen eines Endzustandes von $A$ die beiden Automaten $A_1$ und
$A_2$ \emph{gleich viele} Zeichen abgearbeitet haben und beide ihr Teilwort
akzeptiert haben.

\noindent Die Zustandsüberführungsfunktion $\delta: Q \times \Sigma \rightarrow Q$
stellt sich dann wie folgt dar:
$$
    \delta((q_i,r_j,k),a) =
        \begin{cases}
            (\delta_1(q_i,a),r_j,2) & k=1 \wedge a\in\Sigma_1 \\
            (q_i,\delta_2(r_j,a),1) & k=2 \wedge a\in\Sigma_2 \\
            (q_i,r_j,3) & k=3 \vee (k=1 \wedge a\not\in\Sigma_1) \vee (k=2 \wedge a\not\in\Sigma_2)
        \end{cases}
$$
Da wir diesen Automaten $A$ konstruieren konnten, ist offensichtlich die Sprache
$shuffle(L_1,L_2)$ regulär. \QED

\newpage

\section*{Aufgabe 2}
\begin{enumerate}[(a)]
    \item   NFA zu \texttt{10+(0+11)0$^*$1}
            \begin{center}
                \includegraphics[height=.25\textwidth]{info3_9_aufg2a}
            \end{center}
    \item   NFA zu \texttt{01(((10)$^*$+1111)+0)$^*$1}
            \begin{center}
                \includegraphics[height=.25\textwidth]{info3_9_aufg2b}
            \end{center}
\end{enumerate}

\newpage

\section*{Aufgabe 3}
\begin{enumerate}[(a)]
    \item   Der folgende reguläre Ausdruck beschreibt die Sprache der
            Dezimalzahlen von 0 bis 255 ohne führende Nullen: \\
            \texttt{(0+1+2+3+4+5+6+7+8+9) +} \\
            \texttt{( (1+2+3+4+5+6+7+8+9) (0+1+2+3+4+5+6+7+8+9) ) +} \\
            \texttt{( 1 (0+1+2+3+4+5+6+7+8+9) (0+1+2+3+4+5+6+7+8+9) ) +} \\
            \texttt{( 2 (0+1+2+3+4) (0+1+2+3+4+5+6+7+8+9) ) +} \\
            \texttt{( 25 (0+1+2+3+4+5) )}
    \item   Der folgende reguläre Ausdruck beschreibt die Sprache der
            römischen Zahlen von 1 bis 3999: \\
            \texttt{($\varepsilon$ + M + MM + MMM) $\cdot$} \\
            \texttt{($\varepsilon$ + D) $\cdot$} \\
            \texttt{($\varepsilon$ + C + CC + CCC + CD + CM) $\cdot$} \\
            \texttt{($\varepsilon$ + L) $\cdot$} \\
            \texttt{($\varepsilon$ + X + XX + XXX + XL + XC) $\cdot$} \\
            \texttt{($\varepsilon$ + V) $\cdot$} \\
            \texttt{($\varepsilon$ + I + II + III + IV + IX)}
    \item   Der folgende reguläre Ausdruck beschreibt die durch den
            DFA von Aufgabenblatt 7 Aufgabe 1 akzeptierte Sprache. \\
            \texttt{(0+1+2+3+4+5+6+7+8+9)$^*$ $\cdot$ , $\cdot$ (} \\
            \verb#    #\texttt{((14285 + 4285 + 285 + 85 + 5 + $\varepsilon$) $\cdot$ (714285)$^*$ $\cdot$} \\
            \verb#        #\texttt{(7 + 71 + 714 + 7142 + 71428 + 714285)) +} \\
            \verb#    #\texttt{1 + 14 + 142 + 1428 + 14285 + 4 + 42 + 428 + 4285 +} \\
            \verb#        #\texttt{2 + 28 + 285 + 8 + 85 + 5} \\
            \texttt{)}
\end{enumerate}

\newpage
\section*{Aufgabe 4}
\begin{enumerate}[(a)]
    \item   Kontextfreie Grammatik für die Sprache $L = \{a^ib^jc^k \:\:|\:\: i \neq j \vee j \neq k\}$:
            \begin{eqnarray*}
                S & \rightarrow & a \; A \; U \; C \\
                  & \rightarrow & U \; B \; b \; C \\
                  & \rightarrow & A \; b \; B \; V \\
                  & \rightarrow & A \; V \; C \; c \\
                U & \rightarrow & \varepsilon \\
                  & \rightarrow & a \; U \; b \\
                V & \rightarrow & \varepsilon \\
                  & \rightarrow & b \; V \; c \\
                A & \rightarrow & \varepsilon \\
                  & \rightarrow & A \; a \\
                B & \rightarrow & \varepsilon \\
                  & \rightarrow & B \; b \\
                C & \rightarrow & \varepsilon \\
                  & \rightarrow & C \; c \\
            \end{eqnarray*}
    \item   Kontextfreie Grammatik für die Menge aller arithmetischen Ausdrücke
            über $\{+,\star,a,b,c,(,)\}$:
            \begin{eqnarray*}
                S & \rightarrow & S \; + \; M \\
                M & \rightarrow & M \; \star \; A \\
                  & \rightarrow & A \\
                A & \rightarrow & ( \; S \; ) \\
                  & \rightarrow & a \\
                  & \rightarrow & b \\
                  & \rightarrow & c
            \end{eqnarray*}
\end{enumerate}

\end{document}
