\documentclass{paper}

\setlength {\parindent} {0 pt}
\setlength {\parskip} {1.5 ex plus 0.5 ex minus 0.2 ex}

\usepackage{ngerman}
\usepackage{fullpage}
\usepackage{eurosym}
\usepackage {amssymb}
\usepackage {amsmath}
\usepackage {amsthm}
\usepackage {graphicx}
%\usepackage {wasysym}
\usepackage [usenames] {color}

\usepackage {enumerate}
\usepackage {cite}
\usepackage{float}
\usepackage {xspace}


\floatstyle{ruled}
\newfloat{algorithm}{thp}{alg}
\floatname{algorithm}{Algorithm}


%\usepackage {hyperref}

\newcommand{\mathset}[1]{\ensuremath {\mathbb {#1}}}
\newcommand{\R}{\mathset {R}}
\newcommand{\N}{\mathset{N}}
\newcommand {\Q} {\mathset {Q}}
\newcommand {\Z} {\mathset {Z}}
\newcommand {\EX} {\mathbf {E}}
\newcommand {\script} [1] {\ensuremath {\mathcal {#1}}}
\newcommand {\etal} {\textit {et al.}}
\newcommand {\eps} {\varepsilon}
\newcommand {\eqdef} {:=}
\newcommand {\boruvka}{Bor\r{u}vka}
\newcommand {\wspd}{\texttt{wspd}}
\DeclareMathOperator {\emst}{emst}
\DeclareMathOperator {\conv}{CH}
\DeclareMathOperator {\argmin}{argmin}
\DeclareMathOperator {\DT}{DT}
\DeclareMathOperator {\UC}{UC}
\DeclareMathOperator {\LC}{LC}

\newtheorem{theorem}{Satz}
\newtheorem{inv}[theorem]{Invariante}
\newtheorem{fact}[theorem]{Fakt}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{obs}[theorem]{Beobachtung}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{definition}[theorem]{Definition}


\title{Die Myhill-Nerode Relation}
\author{Wolfgang Mulzer}

\begin{document}
\maketitle

\thispagestyle{empty}

Sei $\N = \{1, 2, 3, \dots \}$ die Menge der nat\"urlichen Zahlen 
und $\N_0 = \{ 0 \} \cup \N$.
Sei $\Sigma$ ein Alphabet und $L \subseteq \Sigma^*$.
Die \emph{Myhill-Nerode Relation} $\sim_L$ f\"ur $L$ ist eine 
Relation auf $\Sigma^*$. Seien $x, y \in \Sigma^*$. Dann ist
\[
  x \sim_L y \text{ definitionsgem\"a\ss{} genau dann, wenn f\"ur 
  alle $z \in \Sigma^*$ gilt: } xz \in L \Leftrightarrow yz \in L.
\]
Man sieht leicht, dass $\sim_L$ eine \"Aquivalenzrelation ist.

Sei nun $\Sigma = \{0, 1\}$ und $L = \{0^n 1^n \mid n \in \N\}$. Wir  
bestimmen die \"Aquivalenzklassen von $\sim_L$.
\begin{itemize}
  \item $[\eps]_L = \{\eps\}$. Es gilt f\"ur $z \in \Sigma^*$:
      $\eps z \in L \Leftrightarrow z \in L \Leftrightarrow 
           z = 0^n1^n$, f\"ur ein $n \in \N$.
      Wie man leicht nachpr\"uft, ist das leere Wort $\eps$ 
      das einzige Wort mit dieser Eigenschaft.
  \item $[01]_L = \{0^n 1^n \mid n \in \N\}$.
    Es gilt f\"ur $z \in \Sigma^*$: 
    $01z \in L \Leftrightarrow z = \eps$. Alle W\"orter mit dieser 
      Eigenschaft m\"ussen in $L$ liegen, und alle W\"orter 
      in $L$ besitzen diese Eigenschaft. Damit ist $[01]_L = L$.
  \item $[1]_L = (\Sigma^* \setminus L(0^*1^*)) \cup 
    \{ 0^m 1^n \mid m \in \N_0, n \in \N, m < n \}$.
    Es gilt f\"ur alle $z \in \Sigma^*$: $1z \not\in L$.
    Die W\"orter $x$ mit dieser Eigenschaft lassen sich wie folgt 
    charakterisieren: Fall 1: $x \in \Sigma^* \setminus L(0^*1^*)$,
    also enth\"alt $x$ den Teilstring $10$.
    Dann ist $xz \not\in L$, f\"ur alle $z \in \Sigma^*$, somit 
    $x \in [1]_L$.
    Fall 2:  $x \in L(0^*1^*)$, also hat
    hat $x$ die Form $0^a 1^b$,  mit $a, b \in \N_0$. 
    Wenn $a < b$ ist, dann ist $xz \not\in L$, f\"ur alle 
    $z \in \Sigma^*$. Also ist dann $x \in [1]_L$.
    Wenn aber $a \geq b$  ist,
    kann man ein Wort an $x$ anh\"angen, mit dem man nach 
    $L$ kommt: $01$ f\"ur $a = b = 0$, $\eps$ f\"ur 
    $a = b > 0$, und  $1^{a-b}$ f\"ur $a > b$.
  \item F\"ur $n \in \N$: 
    $[0^n]_L = \{0^n\}$. Es gilt f\"ur $z \in \Sigma^*$:
    $0^nz \in L \Leftrightarrow 
      z \in \{0^a 1^{n + a} \mid a \in \N_0\}$. 
      Wie man leicht sieht, ist $0^n$ das einzige Wort mit dieser 
      Eigenschaft.
  \item F\"ur $n \in \N$: 
    $[0^{n + 1}1]_L = \{0^{n + m}1^m \mid m \in \N\}$.
    Es gilt f\"ur $z \in \Sigma^*$:
    $0^{n + 1}1z \in L \Leftrightarrow 
      z = 1^n$.
      Wie man leicht sieht, haben diese Eigenschaft genau die 
      W\"orter der Form $0^a1^b$, $a,b \in \N$ mit $a - b = n$.
\end{itemize}
Wir \"uberpr\"ufen noch einmal, dass es sich wirklich um eine 
Partition handelt.
Sei $x \in \{0, 1\}^*$. Falls $x$ \emph{nicht} die Form 
$0^a1^b$, $a, b \in \N_0$, hat  dann ist 
$x \in \Sigma^* \setminus L(0^*1^*)$, also ist $x$ genau  in $[1]_L$.
Nehmen wir nun an, $x$ habe die Form $0^a1^b$, $a,b \in \N_0$.
Falls $a = b = 0$ ist, so ist $x = \eps$, and $x$ ist genau in $[\eps]_L$.
Falls $a = b > 0$ ist, so ist $x$ genau in $[01]_L$.
Falls $a < b$ ist, so ist $x$ genau in $[1]_L$.
Falls $a > b = 0$ ist, so ist $x$ genau in $[0^a]_L$.
Falls $a > b > 0$ ist, so ist $x$ genau in $[0^{a-b+1}1]_L$.
\end{document}