\documentclass[a4paper,10pt]{article} \usepackage{ngerman} \usepackage{amsmath, amsfonts, amsthm, amssymb} \usepackage{pstricks, pst-node, pst-text, pst-plot}%, pst-3dplot} \usepackage{stmaryrd} % f{\"u}r \llbracket und \rrbracket \usepackage{glossary} \usepackage{amssymb} \usepackage{a4wide} \usepackage[latin1]{inputenc} \usepackage{graphicx} \usepackage{fancyhdr} \usepackage{color} \usepackage{eurosym} %\usepackage{strike} \usepackage[pdftitle = pdftitel, pdfauthor = pdfautor, pdfsubject = pdfsubject, bookmarksnumbered = true, bookmarksopen = true, colorlinks = false, pdfborder = 0]{hyperref} \newcommand{\tabl}{\left[\begin{tabular}{c}} \newcommand{\tabr}{\end{tabular}\right]} %Rho mit Punkt \newcommand{\rhoo}{\dot{\rho}} %Vereinigung mit Punkt \newcommand{\dotcup}{\mathbin{\dot{\cup}}} %für liegendesE-Symbol \newcommand{\liegendesE}{ \; \rotatebox[origin=c]{270} {$\exists$} \;} %die ganzen zahlenmengensymbole \newcommand{\N}{\ensuremath{\mathbb{N}}} \newcommand{\R}{\ensuremath{\mathbb{R}}} \newcommand{\Z}{\ensuremath{\mathbb{Z}}} \newcommand{\Q}{\ensuremath{\mathbb{Q}}} \newcommand{\X}{\ensuremath{\mathbb{X}}} \newcommand{\Y}{\ensuremath{\mathbb{Y}}} % amsthm theoreme \newtheoremstyle{afsthm} {\topsep} {\topsep} {\normalfont} {} {\bfseries} {} {\newline } {} \newtheoremstyle{nonuthm} {\topsep} {\topsep} {\normalfont} {0pt} {\bfseries} {} {\newline} {\thmname{#1}\thmnumber{}\thmnote{#3}} \theoremstyle{afsthm} \newtheorem{definition}{Definition}[section] \newtheorem{lemma}[definition]{Lemma} \theoremstyle{nonuthm} \newtheorem{bez}{Bezeichnung}[subsection] \newtheorem{bsp}{Beispiel}[section] \newtheorem{beweis}{Beweis}[section] \newtheorem{behauptung}{Behauptung}[section] \newtheorem{note}{Bemerkung}[section] \newtheorem{satz}{Satz}[section] \newtheorem{satz*}{Satz} \newtheorem{lemma*}{Lemma} \newtheorem{definition*}{Definition} \newtheorem{korollar*}{Korollar} \newtheorem{einschub}{Einschub} \title{Formale Aspekte des DNA-Computing} \author{gelesen von\\ Prof. Dr. Dietrich Kuske} \date{im\\ Sommersemester 2005} \begin{document} \maketitle\thispagestyle{empty}\clearpage\tableofcontents\clearpage %%%%%%%%%% %Kapitel 1 %%%%%%%%%% \section{Schematisch -- Chemischer -- Hintergrund} \begin{enumerate} \item Bausteine \begin{center} \includegraphics[scale=0.4]{gfx/abb1.png} \end{center} \item Bindungen \begin{enumerate} \item \textbf{Verbindung der P-\&-OH-Gruppen} \\ \begin{center} \includegraphics[scale=0.3]{gfx/abb2.png} \end{center} $\Rightarrow$ Ergebnis Kette von Nukleotiden ($\neq$ einstr"angige DNA). \\ \texttt{Bezeichnung:} $(5'-)BB'B''\dots$ oder $(3'-)B''B'B \dots$ \\ Nach Konvention kann man das 5' am Anfang auch weglassen. \\ Verkettung von P und OH $\Rightarrow$ kovalent also stabil, d.h. einstr"angige DNA existiert. \item \textbf{Verbindung der Basen}\\ mit ${B,B'}={A,T}$ \\ oder ${B,B'}={C,G}$ \\ Die entstandenen Bindungen sind instabil ($\Rightarrow$ keine Kettenbildung). \begin{center} \includegraphics[scale=0.3]{gfx/abb3.png} \end{center} \end{enumerate} $\Rightarrow$ Gleichzeitige Verwendung beider Verbindungen erzeugt doppelstr"angige DNA \\ \begin{center} \includegraphics[scale=0.3]{gfx/abb4.png} \end{center} \end{enumerate} \subsection{Operationen} \begin{enumerate} \item \textbf{(De)-Naturierung}\\ \texttt{allgemein:} \begin{itemize} \item W"arme zerst"ort Molek"ule \item doppelstr"angige DNA zerlegt sich, bei 85C - 95C, in die 2 Eeinzlstr"ange \end{itemize} \texttt{Naturierung:} Annealing liefert wieder 2-Str"angige DNA, aber unter Umst"anden unvollst"andig (siehe Grafik).\\ \begin{center} \includegraphics[scale=0.5]{gfx/abb5.png} \end{center} \item \textbf{Verk"urzen von DNA} \begin{enumerate} \item Exonucleasen: Entfernen der letzten Nukleotide, ein oder Doppelstr"angiger DNA \item Endonukleasen: Zerschneiden DNA im Inneren \\ \begin{verbatim} ...GATTCG... ...GA TTCG... => & ...CTAAGC... ...CTAA GC... \end{verbatim} \end{enumerate} Auch f"ur einstr"angige DNA m"oglich\\ aber nur lokal, d.h.\\ \begin{center} \includegraphics[scale=0.8]{gfx/abb6.png} \end{center} $\rightarrow$ "Uberh"ange m"ussen die gleiche L"ange haben und komplement"ar sein \item \textbf{Verbinden von DNA (Ligation)} \begin{enumerate} \item F"uhren spezifisch "uberh"ange zusammen \item F"uhren spezifisch vollst"andige Molek"ulenden zusammen. z.B.: \\ %%%%%%%% % %Verstehe das Beispiel nich %%%%%%%% \begin{array}[b]{rcr} \ldots GATT & \& & CG \ldots \\ \ldots GATT & \& & CG \ldots \\ \end{array} \end{enumerate} \textbf{Problem} \\ \texttt{Vorhanden:} L"osung mit Molek"ulen $\alpha \& \beta$ $ (\alpha,\beta \in \{A,G,C,T\}^+)$ \\ \texttt{Ziel:} L"osung mit Molek"ul $\alpha \beta$ aber \underline{nicht} $\alpha \alpha$ \\ \texttt{erste Idee:} Zusammenkippen und vollst"andige Enden verbinden $\rightarrow$ auch $\alpha \alpha$ existiert. Geht also nicht ;0(\\ \texttt{zweite Idee:} Verhindern, dass sich Ende von $\alpha$ mit Anfang von $\alpha$ verbindet.\\ ersetze P-Gruppe am 5'-Ende von $\alpha$ und OH-Atom \\ \texttt{Ergebnis:} $\alpha$' mit linkem Rand \begin{center} \includegraphics[scale=0.4]{gfx/abb7.png} \end{center} so entstehen nach Ligation $\alpha' \beta$ und $\beta \beta$ \\ dann ersetze OH in $\alpha' \beta$ durch $P\curvearrowright \alpha \beta$ \item \textbf{Polymerase}\\ \texttt{Ausgangspunkt:} unvollst"andigie 2-Str"angige DNA \\ z.B.: \begin{verbatim} TCG CGAGCCTAG \end{verbatim} Polymeraseenzyme binden passendes Nukleotid an 3'-Ende des kurzen Strangs\\ es entsteht: \begin{verbatim} TCGGATC CGAGCCTAG \end{verbatim} \item \textbf{Polymerase-Kettenreaktion}\\ \texttt{Ziel:} Vervielf"altigung einer Menge von DNA. \\ \texttt{Ausgangspunkt:} L"osung, die doppelstr"angige DNA mit Str"angen $\alpha$ bzw. $\overline{\alpha}$ enth"alt. \\ \texttt{Zugabe:} \begin{itemize} \item Primer, die koplement"ar zum 5'-Ende von $\alpha$ bzw. $\overline{\alpha}$ sind ($\beta$ und $\overline{\beta}$) \item Nukleotide \item Polymerase. \end{itemize} \texttt{Vorgehen:} \begin{itemize} \item mischen DNA und Zugaben: ${\alpha \choose \overline{\alpha}}$, $\beta$, $\overline{\beta}$ \item Erw"armen auf ca 85C - 95C: \\ \begin{array}[b]{c} \alpha \\ \overline{\alpha} \end{array}, $\beta,\overline{\beta}$ \item leichtes Abk"uhlen: \begin{array}[b]{c} \alpha \\ \overline{\alpha} \end{array} , \includegraphics[scale=0.4]{gfx/abb8.png} , \includegraphics[scale=0.4]{gfx/abb9.png} \end{itemize} \begin{enumerate} \item \textbf{Polymerase- Reaktion}\\ \begin{center} \includegraphics[scale=0.4]{gfx/abb10.png} \end{center} \texttt{Ergebnis:} Anzahl der Molek"ule \begin{array}[b]{c} \alpha \\ \overline{\alpha} \end{array} (ca.) verdoppelt. %%%%%%%%%%%%%%%%%%% %Vorlesung 12.04.05 %%%%%%%%%%%%%%%%%%% \item \textbf{Herausfiltern}\\ \texttt{Ziel:} Herausfiltern aller DNA-Molek"ule, die gegebene Teilsequenz $\beta$ enthalten.\\ \texttt{Methode:} \begin{itemize} \item fixiere Komplement"armolek"ule $\overline{\beta}$ an z.B. Metallkugel \item danach entferne Metallkugel mit daran klebenden DNA-Molek"ulen aus der L"osung \item l"ose durch Denaturierung DNA-Str"ange mit $\beta$ von $\overline{\beta}$ \end{itemize} \item \textbf{Gel-Elektorphorese}\\ \texttt{Ziel:} Festellen der vorkommenden L"angen von DNA-Molek"ulen in einer L"osung.\\ \texttt{Grundlage:} \begin{itemize} \item DNA-Molek"ule sind negativ geladen \item kurze DNA-Str"ange wandern leichter durch ein Gel zum pos. Pol eines Feldes \end{itemize} \texttt{Versuchsanordnung:} \begin{center} \includegraphics[scale=0.3]{gfx/abb11.png} \end{center} nach gewisser Zeit:\\ \begin{center} \includegraphics[scale=0.3]{gfx/abb12.png} \end{center} $\Rightarrow$ aus Zeit, Ort und Stromst"arke l"asst sich die L"ange der DNA-Fragmente berechnen oder auch auftragen eines Makers $\rightarrow$ es wird die relative Lage betrachtet \end{enumerate} \end{enumerate} %%%%%%%%%% %Kapitel 2 %%%%%%%%%% \newpage \section{Klassische DNA-Berechnung} \subsection{Adlemans Experiment (Since '94)} betrachte folgenden Graphen:\\ \begin{figure}[h] \centering \includegraphics[scale=0.5]{gfx/abb13.png} \end{figure} (nicht planar da 1,3,5 und 2,4,6 ein $K_{3,3}$ bilden)\\ \textbf{Frage:}\\ Existiert ein Hamiltonscher Pfad (Es gibt einen Pfad durch den Graphen bei dem jeder Knoten genau einmal besucht wird [0,1,2,3,4,5,6]) in diesem Graphen?\\ \\ \textbf{Idee:} \begin{itemize} \item Rate alle Tupel von Knoten auf einmal \item sortiere diejenigen Tupel um, die kein Hamiltonscher Pfad sind \end{itemize} \textbf{Realisierung:} \begin{itemize} \item f"ur jeden Knoten i w"ahle ein DNA-Molek"ul der L"ange 20 \item z.B. \begin{align*} & s_2 = TATCGGATCG|GTATATCCGA\\ & s_5 = GGCTAGGTAC|CAGCATGCTT\\ \end{align*} \textbf{Bedingung:}\\ kein Anfangs- oder Endst"uck der L"ange 10 darf 2-mal auftreten \item f"ur jede Kante (z.B. 5$\rightarrow$2): \begin{itemize} \item zerlege $s_2 = s_2's_2''$ und $s_5's_5''$ der L"ange 10\\ \item bilde Komplement $e_{5\rightarrow 2}$ von $s_5''s_2'$\\ $\Rightarrow s_{2K}' = ATAGCCTAGC; s_{5K}'' = GTCGTACGAA$ (K steht f"ur Komplement)\\ $e_{5\rightarrow 2} = GTCGTACGAA|ATAGCCTAGC$ \end{itemize} \item stelle L"osung her, die genau die Molek"ule $s_i(0\leq i \leq 6)$ und $e_{i\rightarrow j}$ f"ur (i,j) $\in$ E enth"alt und f"uhre Ligation herbei \end{itemize} \textbf{Ergebnis:}\\ in der L"osung befinden sich dann z.B. die Molek"ule\\ \begin{center}\includegraphics[scale=0.6]{gfx/abb14.png}\end{center} \begin{center}und\end{center} \begin{center}\includegraphics[scale=0.6]{gfx/abb15.png}\end{center} d.h. jedes Molek"ul beschreibt einen Pfad und jeder Pfad der L"ange n hat gleiche Wahrscheinlichkeit des Vorkommens. Hinreichend viel L"osung sichert, dass jeder Pfad der L"ange 7 mit hoher Wahrscheinlichkeit vorkommt. Jetzt werden die folgenden Schritte ausgef"uhrt: \begin{itemize} \item Herausfiltern der Str"ange der L"ange $7\cdot 20 =140$ \item Herausfiltern der Str"ange die $s_0$ enthalten \item Herausfiltern der Str"ange die $s_1$ enthalten \item $\dots$ \item Herausfiltern der Str"ange die $s_6$ enthalten \end{itemize} Wenn jetzt ein DNA-Molek"ul in der L"osung verbleibt, so hat der Graph einen Hamiltonschen Pfad. \subsection{Sticker-Modelle (Roveis et al '96)} \textbf{Idee:} \begin{itemize} \item betrachte \underline{partiell} 2-str"angige Molek"ule der Form\\ \begin{center} \includegraphics [scale=0.5]{gfx/abb16.png} \end{center} als Kodierung von 0-1-Vektoren (Position n besitzt Komplement $\triangleq$ Vektor der an Stelle n eine 1 enth"alt). \item damit sind alle Vektoren in L"osung gleichzeitig kodierbar \item Beispiel: SAT (jeder 0-1-Vektor ist eine geratene Variable)\\ \begin{enumerate} \item erzeuge 1-str"angige DNA der L"ange = Anzahl der Variablen $\cdot$ Stickerl"ange \item erzeuge Komplemente der Stickerpositionen \item hieran erzeuge durch Annealing alle partiellen 2-str"angigen DNA-Molek"ule \item f"ur jede Klausel aus Formel mit n Variablen \begin{itemize} \item teile L"osung in n gleiche Teile \item teile jedes Teil in 2 Teile: \begin{itemize} \item im 1. Teil ist Stickerposition i besetzt \item im 2. Teil nicht \end{itemize} \item kommt Variable $x_i$ in Klause positiv vor, so behalte ersten Teil sonst den zweiten \item vermische die verbleibenden Teile \end{itemize} \item teste am Ende, ob ein DNA-Molek"ul in der L"osung verbleibt\\ $\Rightarrow$ dieses kodiert ggf. eine g"ultige Belegung der Formel \end{enumerate} \end{itemize} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newpage %%%%%%%%%% %Kapitel 3 %%%%%%%%%% \section{Stickersysteme} Haben nichts mit den Stickermodellen zu tun!!!\\ \\ \underline{\textbf{Grundbausteine der Berechnung:}} \\ DNA-Molek"ule der Form \begin{figure}[h] \centering \includegraphics[scale=0.5]{gfx/abb17.png} \end{figure}\\ \texttt{'Berechnung'} kombiniert diese Bausteine zu komplexeren Molek"ulen. Das \texttt{Ergebnis der Berechnung} ist die Menge der vollst"andigen Molek"ule, die so entstehen (bzw. deren obere Schranke).\\ \\ \underline{\textbf{Verallgemeinerung:}} \\ \begin{itemize} \item nicht nur 4 Basen, sondern Basenmenge V \item Komplentarit"at $\rho \subseteq V \times V$ nicht unbedingt eindeutig, noch notwendig symmetrisch ($\curvearrowright$ A$|$T ist nicht muss) \end{itemize} \subsection{Dominos (Bausteine) \& deren Verkettung} V $\dots$ (endliches, nichtleeres) Alphabet $\rightarrow$ V\{A,G,C,T\}\\ \\ $\rho \subseteq V \times V \dots$ Komplementarit"atsrelation $\rightarrow$ $\rho$ = \{(A,T),(T,A),(G,C),(C,G)\}\\ \\ $V^* \dots$ Menge der W"orter "uber V inklusive $\epsilon$\\ \\ $V^*\times V^* \dots$ Menge der Paare von W"ortern\\ bin"ar Operation $(u,v) \cdot (\overline{u},\overline{v}) = (u,\overline{u})(v,\overline{v})$\\ \textbf{Schreibweise:}\\ \begin{align*} & (u,v) \textnormal{ f"ur } {{u} \choose {v}} \in V^* \times V^*\\ & {X \choose Y} \textnormal{ f"ur } X \times Y \textnormal{; mit } X,Y \subseteq V^*\\ & {X \choose u} \textnormal{ f"ur } {X \choose \{u\}} \textnormal{; falls }u \in V^*, x \leq V^*\\ \end{align*} $\rho ^{*} \dots$ Menge der W"orter "uber $\rho$,\\ $\rho ^+ = \rho ^* \backslash \{\epsilon\} \rightarrow {A \choose T}, {T \choose A}, {G \choose C} \rightarrow$ Wort der L"ange 3\\ \textbf{Schreibweise:}\\ \begin{align*} & {{x_1} \choose {y_1}} {{x_2} \choose {y_2}} \dots {{x_n} \choose {y_n}} = \left[ {{x_1}\choose {y_1}} {{x_2}\choose {y_2}} \dots {{x_n}\choose {y_n}} \right];\\ & \textnormal{falls} {x_i \choose y_i}\in \rho, \textnormal{ f"ur } 1\leq i \leq n\\ \end{align*} $\left. \begin{tabular}{l} $\rho ^* \dots$ W"orter von Paaren\\ ${V^* \choose V^*} \dots$ Paare von W"ortern\\ \end{tabular} \right\rbrace \rho ^* \nsubseteq {{V^*} \over {V^*}} $ \\ \\ $O(V) \dots$ Menge der einstr"angigen Dominos\\ \begin{align*} O(V) = & {V^* \choose \epsilon} \cup {\epsilon \choose V^*}\\ = & \left\lbrace {u \choose v}: u,v\in V^*, u=\epsilon \textnormal{ oder } v = \epsilon \right\rbrace \\ \textnormal{wobei } & {u \choose \epsilon} \neq {\epsilon \choose u}\textnormal{; falls }u \neq \epsilon \\ \end{align*} $W(V,\rho) = W_{\rho}(V) = (O(V) \times \rho ^+ \times O(V)) \cup O(V)$\\ \hspace*{15mm}(W Watson-Crick Domain (Menge der Dominos)) \begin{bsp} \begin{align*} & W(V, \rho) \ni \left({{AG} \choose \epsilon}, \left[\begin{tabular}{c} ACT\\ TGA \end{tabular}\right], {\epsilon \choose {AG}} \right) = \includegraphics[scale=0.3]{gfx/abb18.jpg}\\ &\\ & W(V, \rho) \ni {{Ag} \choose \epsilon} = \includegraphics[scale=0.3]{gfx/abb19.jpg} = 5-AG\\ & W(V, \rho) \ni {\epsilon \choose {GA}} = \includegraphics[scale=0.3]{gfx/abb20.jpg} = 3-GA = 5-AG\\ & \textnormal{\underline{\underline{aber }}} {{AG} \choose {\epsilon}} \neq {{\epsilon} \choose {GA}} \textnormal{ obwohl sie das selbe Molek"ul modellieren.}\\ \end{align*} \end{bsp} \textbf{Schreibweise}\\ \begin{align*} & \left({{u_1}\choose {v_1}}, \left[\begin{tabular}{c} $u_2$\\ $v_2$\end{tabular} \right], {{u_1}\choose {v_1}}\right) = {{u_1}\choose {v_1}} \left[\begin{tabular}{c} $u_2$\\ $v_2$ \end{tabular}\right] {{u_3}\choose {v_3}}\\ & {{\epsilon}\choose {\epsilon}} \left[\begin{tabular}{c}$u_2$\\$v_2$\end{tabular}\right] {{u_3}\choose {v_3}} = \left[\begin{tabular}{c} $u_2$\\$v_2$\end{tabular}\right] {{u_3}\choose {v_3}}\\ & {{u_1}\choose {v_1}} \left[\begin{tabular}{c}$u_2$\\$v_2$\end{tabular}\right] {{\epsilon}\choose {\epsilon}} = {{u_1}\choose {v_1}} \left[\begin{tabular}{c} $u_2$\\$v_2$\end{tabular}\right]\\ & {{\epsilon}\choose {\epsilon}} \left[\begin{tabular}{c}$u_2$\\$v_2$\end{tabular}\right] {{\epsilon}\choose {\epsilon}} = \left[\begin{tabular}{c} $u_2$\\$v_2$\end{tabular}\right]\\ \end{align*} $\Rightarrow$ wir betrachten $\rho ^+$ als Teilmenge von $W(V, \rho)$\\ f"ur $m \in W(V,\rho)$ sei h(m) die "uberhangl"ange definiert durch:\\ \begin{align*} h(m) = \left\lbrace \begin{tabular}{l} max \{$|u|,|v|$\}; falls m = ${u \choose v} \in O(V)$ \\ max \{$|u_1|,|v_1|,|u_3|,|v_3|$\}; falls $m={u_1 \choose v_1} \tabl $u_2$\\$v_2$ \tabr {u_3 \choose v_3}$\\ \end{tabular} \right.\\ \end{align*} \begin{bsp} \begin{align*} & \tabl AG\\TC \tabr \rhoo \tabl GCA \\ CGT \tabr = \tabl AGGCA \\ TCCGT \tabr\\ & \tabl AG \\ TC \tabr {CA\choose \epsilon} \rhoo {\epsilon \choose GT} = \tabl AGCA \\ TCGT \tabr\\ & {AA \choose \epsilon} \rhoo {\epsilon \choose TT} \textnormal{ undefiniert}\\ & \tabl AG \\ TC \tabr {CA \choose \epsilon} \rhoo {\epsilon \choose TG} \textnormal{ undefiniert}\\ \end{align*} $\rhoo$ entspricht dem Verkn"upfungsoperator \end{bsp} \begin{definition}[Verkettung von Dominos] Die Verkettung von Dominos "uber $(V, \rho)$:\\ \begin{enumerate} \item $ {{u_1}\choose{\epsilon}} \rhoo {{u_2}\choose {\epsilon}} = {{u_1u_2}\choose{\epsilon}} \textnormal{ und } {{\epsilon}\choose{v_1}} \rhoo {{\epsilon} \choose {v_2}} = {{\epsilon}\choose{v_1v_2}}\\ $ \item $ \left({{u_1}\choose{u_2}} \left[ \begin{tabular}{c} $v_1$ \\ $v_2$ \end{tabular} \right] {{w_1}\choose{w_2}} \right) \rhoo \underbrace{{{x_1}\choose{x_2}}}_{\in O(V)} = {{u1}\choose{u2}} \left[ \begin{tabular}{c}$v_1 y_1$\\$v_2 y_2$\end{tabular} \right] {{z_1}\choose{z_2}}\\$ \begin{itemize} \item mit $w_1x_1 = y_1z_1$ und $w_2x_2 = y_2z_2$ \item $|y_1| = |y_2| = min \{|w_1x_1|,|w_2x_2|\}$ \item und $\left[ \begin{tabular}{c}$y_1$ \\ $y_2$ \end{tabular} \right]$\\ \end{itemize} \item $ {{x_1}\choose{x_2}} \rhoo \left( {{u_1}\choose{u_2}} \left[ \begin{tabular}{c}$v_1$ \\ $v_2$ \end{tabular} \right] {{w_1}\choose{w_2}}\right) \textnormal{ analog}\\ $ \item $ {{u_1}\choose{u_2}} \left[ \begin{tabular}{c}$v_1$\\$v_2$\end{tabular} \right] {{w_1}\choose{w_2}} \rhoo {{x_1}\choose{x_2}} \left[ \begin{tabular}{c}$y_1$\\$y_2$\end{tabular} \right] {{z_1}\choose{z_2}} = {{u_1}\choose{u_2}} \left[{v_1 w_1 x_1 y_1}\choose{v_2 w_2 x_2 y_2}\right] {{z_1}\choose{z_2}}\textnormal{; falls } \left[{w_1x_1}\choose{w_2x_2}\right] \in \rho ^*\\ $ \item $m \cdot m'$ ist undefiniert wenn keiner der F"alle 1. - 4. zutrifft\\ \end{enumerate} \end{definition} \begin{definition}[Stickersystem] Ein \underline{Stickersystem} ist ein Quadrupel $\gamma = (V,\rho,A,D)$, wobei \begin{itemize} \item V ein Alphabet \item $\rho \subseteq V^2$ eine Komplementarit"atsrelation \item $A \subseteq LR_{\rho}(V) := W_{\rho} (V)\backslash O(V)$ eine endliche Menge von \underline{Axiomen} (Startsymbol) und \item $D \subseteq W_{\rho}(V) \times W_{\rho} (V)$ eine endliche Menge von \underline{Regeln} ist \end{itemize} Sei $\gamma \in (V,\rho, A, D)$ Stickersystem und $x,y \in LR_{\rho}(V)$\\ $x \rightarrow _\gamma y : \Leftrightarrow$ sei Regel $(u,v) \in D$ mit $y = u \cdot \rho x \cdot \rho v$ \end{definition} \begin{definition}[Molek"ulsprache] Sei $\gamma= (V,\rho, A,D)$ ein Stickersystem. Die \underline{Molek"ulsprache} $LM(\gamma)$ ist die Menge der vollst"andigen Dominos $y \in \rho ^+$, die aus Axiomen abgeleitet werden k"onnen: \begin{align*} & LM(\gamma) := \{ y \in \rho^+ : \exists x \in A: x \rightarrow ^* _\gamma y \}\\ \end{align*} Die \underline{Sprache} $L(\gamma)$ ist die Menge der oberen Str"ange von Elementen von $LM(\gamma)$: \begin{align*} & L(\gamma) := \left\lbrace u \in V^+: \exists v \in V^+: \left[\begin{tabular}{c} u\\v \end{tabular}\right] \in LM(\gamma)\right\rbrace \\ \end{align*} \end{definition} %%%%%%%%% %26.4.05% %%%%%%%%% %Einr"uckung innerhlalb der des Beispiels \begin{bsp}[ 3.4] \begin{align*} & LM(\gamma) \textnormal{ mit Stickersystem }\gamma=(V,\rho,A,D)\\ & V = \{a,b,c,d\}\\ & \rho = \{(a,a),(b,b)(c,c),(d,d)\}\\ & A = \left\lbrace \tabl c\\c \tabr \right\rbrace \\ & D = \left\lbrace \left({b \choose \epsilon}, {d\choose \epsilon}\right), \left( {a \choose \epsilon}, {\epsilon \choose \epsilon} \right), \left( {\epsilon \choose b}, {\epsilon \choose \epsilon}\right), \left({\epsilon \choose a}, {\epsilon \choose d} \right) \right\rbrace \\ & Sei\\ & L_1 = \left\lbrace \tabl a\\ a \tabr^* \tabl b\\ b \tabr^* \tabl c\\ c \tabr \tabl d\\ d \tabr \right\rbrace \textnormal{ und}\\ & L_2 = \left\lbrace \tabl a\\ a \tabr^m \tabl b\\ b \tabr^m \tabl c\\ c \tabr \tabl d\\ d \tabr^m : m \in \N \right\rbrace \\ \end{align*} \begin{behauptung} $LM(\gamma) \cap L_1 = L_2$ \end{behauptung} \begin{beweis} $\leq$\\ \\ Sei $x = \tabl a\\ a \tabr^k \tabl b\\ b \tabr^l \tabl c\\ c \tabr \tabl d\\ d \tabr^m \in LM(\gamma) \cap L_1$\\ wegen $x \in LM(\gamma)$ existiert $x_i$ $W(V,\rho)$ mit $x_0 \in A$, $x_i \rightarrow x_{i+1}, x_n = x$ f"ur $0 \leq i < n$\\ $\Rightarrow$ da $\left( {\epsilon \choose a}, {\epsilon \choose d} \right)$ die einzige Regel ist, die a im 2. Strang einf"uhrt, folgt m=k.\\ Da $\left( {b \choose \epsilon}, {d \choose \epsilon} \right)$ einzige Regel, die b bzw. d im 1. Strang einf"uhrt, gilt auch l = m\\ $\Rightarrow x \in L_2,\\ \Rightarrow \textnormal{d.h. } LM(\gamma) \cap L_1 \subseteq L_2$\\ \\ $\geq$\\ \\ \begin{tabular}{l|l} Schritt & angewendete Regel\\ \hline $\tabl c\\c \tabr$ & $\left( {\epsilon \choose b}, {\epsilon \choose \epsilon}\right)$\\ $\rightarrow^m {\epsilon \choose b} \tabl c\\c \tabr {\epsilon \choose \epsilon}$ & $\left( {b \choose \epsilon}, {d \choose \epsilon}\right)$\\ $\rightarrow ^m \tabl b\\b \tabr^n \tabl c\\c \tabr {d\choose \epsilon}^m$ & $\left( {\epsilon \choose a}, {\epsilon \choose d}\right)$\\ $\rightarrow ^m {\epsilon\choose a}^m \tabl b\\b \tabr ^m \tabl c\\c \tabr \tabl d\\d \tabr^m$ & $\left({a \choose \epsilon}, {\epsilon \choose \epsilon}\right)$\\ $\rightarrow^m \tabl a\\a \tabr^m \tabl b\\b \tabr^m \tabl c\\c \tabr \tabl d\\d \tabr^m$ & \end{tabular}\\ \\ $\Rightarrow L_2 \subseteq LM(\gamma) \cap L_1$\\ \\ \begin{flushright}\texttt{damit ist die Behauptung gezeigt}\end{flushright} \end{beweis} \begin{behauptung} $L(\gamma)$ ist kontextfrei \end{behauptung} \begin{beweis} angenommen $L(\gamma)$ w"are kontextfrei\\ $\Rightarrow LM(\gamma) \cap L_1$ kontextfrei ("ubung 2.3)\\ Widerspruch zu $L_2$ nicht kontextfrei ("ubung 2.2) \begin{flushright}\texttt{q.e.d.}\end{flushright} \end{beweis} \end{bsp} \subsection{Erzeugte Sprachen} Jede Stickersprache ist kontextsensitiv $\rightarrow$ sie wird somit von einem LBA akzeptiert \begin{lemma*}[ 3.5 (Peter Weigel '04)] Sei $\gamma$ ein Stickersystem. Dann gilt $L(\gamma) \in NL$. \begin{note} $NL \subseteq NP \subseteq CS = NSPACE(n) \textnormal{ und } NL \subsetneq CS$ \end{note} \end{lemma*} \begin{beweis} Sei $w=a_1,a_2, \dots a_n \in V^*$\\ f"ur $1 \leq i \leq j \leq n$ sei $w[i,j] = a_i a_{i+1} \dots a_{j-1}$\\ f"ur $i < 1$ oder $j > n+1$: Aufruf $w(i,j)$ durch return FEHLGESCHLAGEN entspricht Laufzeitfehler (weiter siehe Kopie)\\ Variable:\\ $l_1,l_2,r_1,r_2 \in \{-k,-k+1, \dots, n, \dots, n+k\}$ wobei k die Gr"o"se des gr"o"sten Dominos in $\gamma$ ist.\\ $x_1, x_2, y_1, y_2, z_1, z_2 \in V^{\leq k}$\\ $x,y \in W(V,\rho)$; $|x|,|y| \leq k$\\ Platzbedarf:\\ $4 \cdot log (2k + n) +c \in O(log n)$ (c h"angt nur von $\gamma$, aber nicht von der Eingabe w ab) \begin{flushright}\texttt{q.e.d.}\end{flushright} \end{beweis} Jede Stickersprache l"asst sich von einem k-Kopfautomaten erkennen.\\ Nach Bsp. 3.4 $\Rightarrow$ es gibt nicht kontextfrei Stickersprache, also insbesondere eine nicht-regul"are.\\ \begin{einschub} Erl"auterung zu k-Kopfautomaten \begin{center} \includegraphics[scale=0.5]{gfx/abb21.png} \end{center} \begin{itemize} \item 1 Kopf nur zum Lesen \item ein Kopf wei"s nicht ob er rechts oder links von einem anderen ist \item mit 4 K"opfen lassen sich Stickersprachen erkennen \item $L(\gamma)$ lassen sich mit 6 Kopfautomaten erkennen \item $\bigcup_{k \in \N}$ L(k-Kopfautomaten)$\subseteq NL$ \item je mehr K"opfe desto schw"acher der Automat \end{itemize} \end{einschub} \begin{definition*} Ein Stickersystem $\gamma = (V,\rho,A,D)$ hei"st \underline{einseitig}, wenn f"ur jede Regel $(x,y) \in D$ gilt: $$x = {\epsilon\choose \epsilon} \textnormal{ oder } y={\epsilon\choose \epsilon}$$ \end{definition*} vgl. Grammatik:\\ G = (N,T,S,R) mit\\ N = \{S,S'\}, T = \{a,b\}, R = \{$S \rightarrow S'b, S' \rightarrow aS, S \rightarrow \epsilon$ \}\\ $L(G) = \{a^n b^n: n\in N\}$ nicht regul"ar. \begin{lemma*}[3.6] Sei $G=(N,T,S,R)$ kontextfreie Grammatik mit $N = N_l \dotcup N_r \dotcup \{S\}$ und\\ $R \subseteqq (\{S\} \times N_l T^* N_r) \cup (N_l \times N_l T^*) \cup (N_r \times T^* N_r) \cup (N \times \{\epsilon\})$.\\ Dann ist L(G) regul"ar obwohl die Grammatik nicht regul"ar ist. \end{lemma*} \begin{beweis} f"ur $p=(S,X_lwX_r) \in R$ definiere Grammatik\\ $G^p _l = (N_l, T, X_l R\cap (N_l \times (N_l \cup T)^*))$\\ und\\ $G^p _r = (N_r, T, X_r, R\cap(N_r \times (N_r \cup T)^*))$\\ $\Rightarrow G^p _l$ ist linksregul"ar und $G^p _r$ ist rechtsregul"ar\\ $L(G)\backslash\{\epsilon\} = \cup_{p=(S,X_lwX_r) \in R} L(G^p _l) \cdot w \cdot L(G^p _r)$\\ Da $G^p_l$ und $G^p _r$ regul"ar sind, ist auch $L(G)\backslash \epsilon$ regul"ar.\\ $\Rightarrow$ L(G) regul"ar \begin{flushright}\texttt{q.e.d.}\end{flushright} \end{beweis} %%%%%%%%%%%%%%%% %Vorlesung 3.05.05 %%%%%%%%%%%%%%%% \begin{lemma*}[3.7] Sei $\gamma =(V,\rho,A,D)$ ein einseitiges Stickersystem. Dann ist $L(\gamma)$ regul"ar. \end{lemma*} \begin{beweis} Wir konstruieren Grammatik G mit $L(G) = L(\gamma)$, die die Bedingungen von Lemma 3.6 erf"ullt.\\ \textbf{Idee:}\\ w"ahle $d \in N$ mit $h(x) \leq d$ f"ur alle $x \in A, (x,y),(y,x) \in D$, dann ist jedes $x \in LM(\gamma)$ durch eine Ableitung $A \ni x_0 \rightarrow _{\gamma} x_1 \rightarrow _{\gamma} x_2 \rightarrow _{\gamma} \dots \rightarrow _{\gamma} x_n = x$ herleitbar mit $h(x_i) \leq d$ f"ur alle i. Die "Uberl"ange von $x_i$ werden die Nichtterminale: $$N = \left(\left\lbrace c \in {V^* \choose \epsilon} \cup {\epsilon \choose V^*}: |x| \leq d \right\rbrace \times \{l,r\} \right) \cup \{S\}$$ $$T = \rho$$ P enth"alt folgende Regeln:\\ \begin{enumerate} \item $ S \rightarrow (x,l) y(z,r) \textnormal{ ist Regel, falls }\\ x,z \in {V^*\choose \epsilon} \cup {\epsilon \choose V^*}$; $|x|,|z| \leq d$; $y \in \rho^+$; $x,y,z \in A$ \\ $\Rightarrow (x,l)$ und $(z,r)$ sind "Uberh"ange \item $ (y,l) \rightarrow (y',l) z \textnormal{ ist Regel falls }\\ y,y' \in {V^*\choose \epsilon} \cup {\epsilon \choose V^*}$; $|y|,|y'| \leq d$; $z \in \rho^* \textnormal{ und es gibt }\\ (x, \epsilon) \in D, \textnormal{ und } \tabl a \\ b \tabr \in \rho \textnormal{ mit } x \cdot y \cdot \tabl a\\b \tabr = y'z \tabl a\\b \tabr\\ $ \item $ (y,r) \rightarrow x(y',r) \textnormal{ ist Regel, falls }\\ y,y' \in {V^* \choose \epsilon} \cup {\epsilon \choose V^*}$; $|y|,|y'| \leq d$; $x \in \rho^* \textnormal{ und es gibt }\\ (\epsilon, z) \textnormal{ und } \tabl a\\b \tabr \in \rho \textnormal{ mit } \tabl a\\b \tabr y \cdot z = \tabl a\\b \tabr x\cdot y'\\ $ \item $ (\epsilon, l) \rightarrow \epsilon\\ (\epsilon, r) \rightarrow \epsilon\\ $ \end{enumerate} Die Grammatik $G = (N,T,S,P)$ erf"ullt die Bedingungen aus Lemma 3.6, also ist L(G) regul"ar.\\ %%%%%%%% %nochmal nach pr"ufen!!! %%%%%%%% \\ \texttt{Wir zeigen zun"achst:} $L(G) = L(M) (\gamma)$\\ Sei $x \in L(G) \rightarrow$ es gibt Ableitung in G der Gestalt \begin{align*} & S \rightarrow_G (x_1,l)y(z_1,r)\rightarrow_G (x_2,l)y_2(z_2,r) \dots \rightarrow_G (x_n, l)y_n(z_n, r) \rightarrow_G y_n(z_n,r) =x\\ & \Rightarrow x_1y_1z_1 \in A\\ & x_i y_i z_i \rightarrow_{\gamma} x_{i+1},y_{i+1},z_{i+1}\textnormal{ f"ur }1 \leq i \leq n-1\\ & \Rightarrow x_ny_nz_n = y_n \in LM(\gamma)\textnormal{, also }L(G) \leq LM(\gamma)\\ \end{align*} Es sei $x \in LM(\gamma)$\\ $\Rightarrow$ es gibt Ableitung: \begin{align*} & A \ni x_1 \rightarrow_{\gamma} x_2 \rightarrow_{\gamma} x_3 \dots \rightarrow_{\gamma} x_n = x \textnormal{ mit } h(x_i) \leq d\\ & \textnormal{Sei } x_i^1,x_i^3 \in {V^* \choose \epsilon} \cup {\epsilon \choose v^*}, x_i^2 \in \rho^+ \textnormal{ mit } x_i=x_i^1x_i^2x_i^3\\ \end{align*} Regeln aus P genau so, dass\\ \begin{align*} & S \rightarrow G (x_1^1,l)x_1^2(x_1^3,r) \rightarrow_G (x_2^1,l)x_2^2(x_2^3,r) \dots \rightarrow_G (x_n^1,l)x_n^2(x_n^3,r)\\ & x = x_n = x_n^1x_n^2x_n^3 \in \rho^+\\ & \Rightarrow x_n^1,x_n^3={\epsilon \choose \epsilon}\\ & \Rightarrow (x_n^1,l)x_n^2(x_n^3,r) \rightarrow_G ^* x_n^2=x_n=x\\ & \Rightarrow x \in L(G)\textnormal{, also } LM(\gamma) \leq L(G)\\ & \Rightarrow LM(\gamma)\textnormal{ regul"ar.}\\ & \textnormal{Sei }\eta : \rho^* \rightarrow V^* \textnormal{Homomorphismus mit }\eta \left(\tabl a\\b \tabr \right) = a\textnormal{ f"ur }\tabl a\\b \tabr \in \rho\\ & \Rightarrow \eta(LM(\gamma))\textnormal{ ist regul"ar und gleich } L(\gamma)\\ \end{align*} \begin{flushright}\texttt{q.e.d.}\end{flushright} \end{beweis} \begin{lemma*}[3.8] Sei $G = (N,T,S,P)$ rechtsregul"are Grammatik. Dann existiert ein einseitiges Stickersystem $\gamma$ mit $L(G) = L(\gamma)$. \end{lemma*} \begin{beweis} o.E.\\ $N = \{X_1,X_2,\dots,X_k\}$\\ $(X_i w X_j)$ oder $(X_i,w)$ Regel $\rightarrow |w| \leq 1$\\ \textbf{Idee:}\\ ist $a_1, \dots ,a_n X_i$ ableitbare Satzform, so kodiere diese durch Domino\\ \\ \fbox{ \begin{tabular}{cccccc} $a_1$ & $a_2$ & $\dots$ & $a_{n-i}$ & $\dots$ & $a_n$\\ \end{tabular} }\\ \fbox{ \begin{tabular}{cccc} $a_1$ & $a_2$ & $\dots$ & $a_{m-i}$\\ \end{tabular} }\\ \\ \textbf{Formal:}\\ $V = T\\ \rho = \left\lbrace {a \choose a}, a\in V \right\rbrace $\\ $A = \left\lbrace \tabl x\\x \tabr {u \choose \epsilon}: S \rightarrow^*_G xuX_{|u|}, |xu| = k+1 \right\rbrace \cup \left\lbrace \tabl x\\x \tabr : x \in L(G), |x| < k+1 \right\rbrace$\\ $D = \left\lbrace \left( {\epsilon \choose \epsilon}, {\epsilon \choose v} \tabl x\\x \tabr {u \choose \epsilon} \right): |xu| = k+1, X_{|v|} \rightarrow ^*_G xuX_{|u|}\right\rbrace \cup \left\lbrace \left( {\epsilon \choose \epsilon}, {\epsilon \choose v} \tabl x\\x \tabr \right): |x| \leq k, X_{|v|} \rightarrow _G^* x \right\rbrace$\\ Dann ist $\gamma = (V,\rho,A,D)$ einseitiges Stickersystem.\\ \\ \textbf{Nun zu zeigen:}\\ \begin{align*} & L(G) = L(\gamma)\\ & 'L(\gamma) \leq L(G)'\textnormal{ ohne Beweis}\\ & 'L(G) \leq L(\gamma)'\\ \end{align*} Sei $w \in L(G)$\\ Es gibt folgende F"alle:\\ \begin{enumerate} \item $|w| \leq k \Rightarrow \tabl w\\w \tabr \in A \cap \rho^+ \Rightarrow w \in L(\gamma)$ \item $|w| > k$\\ $\Rightarrow$ es gibt $w_i \in V^+$ mit $|w_i| = k+1$ f"ur $1 \leq i \leq n$ und $w = w_1w_2w_3 \dots w_nw_{n+1}, w_{|n+1|} \leq k$\\ und es gibt $j_i = k$ mit $ S \rightarrow_G^* w_1X_{j_1} \rightarrow_G^* w_1w_2X_{j_2} \dots \rightarrow_G^* w_1w_2\dots w_nX_{j_n} \rightarrow^*_G w_1w_2 \dots w_nw_{n+1} = w$\\ wegen $|w_i| = k+1$ existiert $u_i,x_i \in V^+: w_i=x_iu_i, |u_i| =j_i$ f"ur $1\leq i \leq n$\\ $\Rightarrow$ %%%%%%%% %nochmal anschauen wegen den Indexverhau %%%%%%%% \begin{enumerate} \item $\tabl $x_1$\\$x_2$ \tabr {u_1\choose \epsilon} \in A$\\ \item $\textnormal{f"ur } 2 \leq i \leq n\\ X_{j_{i-1}} \rightarrow w_iX_{j_i, j_{i-1}} = |u_{i-1}|, j_i = |u_i|\\ \Rightarrow \left( {\epsilon \choose \epsilon}, {\epsilon \choose u_{i-1}} \tabl $x_i$\\$x_i$\tabr {u_i \choose \epsilon}\right) \in D$\\ \item $X_{j_n} \rightarrow_G^* w_{n+1}, |w_{n+1}| \leq k\\ \Rightarrow \left( {\epsilon \choose \epsilon}, {\epsilon \choose u_n} \tabl $w_{n+1}$\\$w_{n+1}$\tabr \right) \in D\\ \Rightarrow \tabl $x_1$\\$x_2$ \tabr {n_1 \choose \epsilon}\rightarrow_{\gamma} \tabl $x_1u_1x_2$\\$x_1u_1x_2$ \tabr {u_2 \choose \epsilon}\\ \textnormal{(Regel der Form 2)} \rightarrow_{\gamma}^* \tabl $x_1u_1 \dots u_{n-1} x_n$ \\ $x_1u_1 \dots u_{n-1}x_n$ \tabr {u_n \choose \epsilon}\\ \textnormal{(Regel der Form 3)} \rightarrow_{\gamma}^* \tabl $x_1u_1 \dots u_n w_{n+1}$ \\ $x_1u_1 \dots u_n w_{n+1}$ \tabr = \tabl w\\w \tabr\\ \Rightarrow w \in L(\gamma)$\\ \end{enumerate} \end{enumerate} \begin{flushright}\texttt{q.e.d.}\end{flushright} \end{beweis} %%%%%%%%%%%%%%%% %Vorlesung 11.05.05 %%%%%%%%%%%%%%%% \begin{satz} [ 3.9] Es gelte die folgende Beziehung\\ \\ \begin{tabular}{c c c} & $CS = NSPACE(id)$ & \\ & \rotatebox[origin=c]{90} {$\subsetneq$} &\\ \rotatebox[origin=c]{45} {$\nsubseteq$} & SL := & \rotatebox[origin=c]{135}{$\nsubseteq$}\\ & $\{L(\gamma):\gamma \textnormal{ SSys}\}$ & \\ SSL := & $ \nsupseteq$ & OSL = REG =:\\ $\{L(\gamma):\gamma \textnormal{ einf SSys}\}$ & $\nsubseteq$ & $\{L(\gamma):\gamma \textnormal{ eins SSys}\}$\\ \rotatebox[origin=c]{135} {$\nsubseteq$}& & \rotatebox[origin=c]{45} {$\nsubseteq$}\\ & SOSL := &\\ & $\{L(\gamma):\gamma \textnormal{ einf \& eins SSys}\}$& \\ \end{tabular}\\ \\ (Abk"urzungen: SSys = Stickersystem, einf = einfaches, eins = einseitiges) \end{satz} \begin{beweis} $SL \subsetneq CS$: Lemma 3.5\\ $OSL = REG$: Lemma 3.7 \& 3.8\\ $SOSL \neq SSL$: "ubung $ab^*a \in SSL \backslash SOSL$\\ $SOSL \neq REG$: $ab^*a \in REG \backslash SOSL$\\ $SSL \nsubseteq REG$: Bsp 3.4 (SSL enth"alt eine Sprache, die nicht kontextfrei ist)\\ $\Rightarrow SL \neq OSL$ $REG \nsubseteq SSL$: $a^* \cup {b} \in REG \backslash SSL \Rightarrow SSL \subsetneq SL$\\ (Weigel \& Keilwagen '04)\\ \begin{flushright}\texttt{q.e.d.}\end{flushright} \end{beweis} \subsection{Turing- m"achtige Erweiterungen} nach Lemma 3.5 existiert insbesondere eine rekursiv aufz"ahlbare Menge L, die sich von keinem Stickersystem erzeugen l"asst.\\ \\ \textbf{Frage:}\\ existiert vielleicht ein '"Ubersetzungs-' oder 'Anzeigemachanismus' g so, dass f"ur jede rekursiv aufz"ahlbare (im weiteren Verlauf abgek"urzt durch r.e.) Sprache L ein Stickersystem $\gamma$ existiert mit $L = g(L(\gamma))$.\\ \texttt{hier:} generalized sequential machines (gsm) \begin{definition*}[3.10] Ein Tupel $g=(Q,V_1,V_2, \iota, F,\delta)$ ist eine \underline{det. gsm}, falls:\\ \begin{itemize} \item Q eine endliche Menge von Zust"anden \item $V_1$, $V_2$ Ein- \& Ausgabealphabete \item $\iota \in Q$ der Initialzustand \item F $\subseteq$ Q eine Menge von Finalzust"anden und \item $\delta: Q \times V_1 \rightarrow (Q \times V_2 ^*)$ eine "Uberf"uhrungsfunktion ist.\\ \end{itemize} \end{definition*} F"ur die det. gsm g sei $R(g) \subseteq V_1^* \times V_2^*$ definiert durch:\\ \begin{align*} & (a_1a_2 \dots a_n,w) \in R(g)\\ & \textnormal{ mit } a_i \in V_1 \textnormal{ \& } w \in V_2^* \Leftrightarrow \exists q_i \in Q, v_i \in V_2^*: \\ & q_0 = \iota, \delta (q_i, a_{i+1}) = (q_{i+1}v_{i+1}) \textnormal{ f"ur } i=0,\dots, n-1\\ & q_n \in F \textnormal{ und } w =v_1v_2 \dots v_n\\ \end{align*} \begin{note} Sind $(v,w), (v,w') \in R(g)$, so gilt $w=w'$\\ $\Rightarrow R(g)$ ist partielle Funktion von $V_1 ^*$ nach $V_2 ^*$\\ $\Rightarrow$ Schreibweise $g(v) = w$ f"ur $(v,w) \in R(g)$ \end{note} \begin{align*} & V_1 ^* \underrightarrow{g} V_2 ^* \underrightarrow{h} V_3 ^*\\ & V_1 ^* \underrightarrow{h \circ g} V_3 ^*\\ \end{align*} \begin{lemma*}[3.11] Seien $g_i = (Q_i, V_i, V_{i+1}, \iota_i, \delta_i)$ f"ur i = 1,2 det. gsms. Dann existiert eine det. gsm g mit $R(g) =R(g_1) \circ R(g_2)$\\ $Rightarrow$ g ist Verkettung von $g_1$ und $g_2$ \end{lemma*} \begin{note} $h \circ g(u):=h(g(u))$; $u \in V_1^*$\\ $R(g_1) \circ R(g_2) = \{(u,v) \in V_1^* \times v_3^*: \exists v \in V_2^*: (u,v) \in R(g_1), (v,w) \in R(g_2)\}$ \end{note} \begin{beweis} Beweisskizze:\\ \begin{center} $\underrightarrow{a_1a_2a_3}$ \begin{tabular}{|c|}\hline $g_1$\\ \hline \end{tabular} $\rightarrow$ \begin{tabular}{|c|}\hline $v_1$\\ \hline $v_2$\\ \hline $v_3$\\ \hline \end{tabular} $\rightarrow$ \begin{tabular}{|c|}\hline $g_2$\\ \hline \end{tabular} $\rightarrow$ $g_2(v_1v_2v_3)$ \end{center} \begin{align*} & Q = Q_1 \times Q_2\\ & \delta((q_1,q_2), a)= ((r_1,r_2),w) \textnormal{ mit }\\ &\delta_1 (q_1,a) = (r_1,v) \textnormal{und}\\ & \delta_2 ^*(q_2,v) = (r_2,w) \textnormal{ f"ur ein } v \in V_2^*\\ & \iota = (\iota_1, \iota_2)\\ & F =F_1 \times F_2\\ \end{align*} Setze $g = (Q,V_1,V_3, \iota, F, \delta)$ Dann gilt:\\ $$R(g) = R(g_1) \circ R_(g_2)$$\\ \begin{flushright}\texttt{o.B.\\ q.e.d.}\end{flushright} \end{beweis} \begin{note} \begin{align*} & \delta_2 ^* (q_2,v) = (r_2,w)\\ & \delta_2 ^* (q_2,v) = (r,\epsilon)\\ & \delta_2 ^* (q_2,au) = (r'',vw)\\ & \textnormal{falls } \delta_2(r,a) = (r',v)\\ & \textnormal{und } \delta_2 ^*(r',u) = (r'',w) \end{align*} \end{note} \textbf{weiteres Vorgehen:} \begin{enumerate} \item Konstruktion eines \underline{einfachen Stickersystems} \& einer deterministischen gsm $g_1$ mit $TS_v = g_1(L(\gamma))$ \item f"ur L r.e. existiert det. gsm $g_2$ mit $L=g_2(TS_v) = \underbrace{g_2(g_1}_{g}(L(\gamma))) = g(L(\gamma))$ \end{enumerate} \begin{definition*} [ 3.12 Twin-Shuffel-Sprache] V Alphabet\\ \begin{itemize} \item $\overline{V} = \{\overline{a}: a \in V\}$ wir nehmen an, dass $V \cap \overline{V} = \oslash$ \item $u,v \in V^*$\\ $u \liegendesE v = \{u_1v_1u_2v_2 \dots u_nv_n: u_1u_2 \dots u_n =u, v_1v_2 \dots v_n=v$\\ ist der \underline{Schuffel} von u \& v \item $a_1,a_2,\dots a_n \in V: \overline{a_1a_2 \dots a_n} = \overline{a_1}, \overline{a_2}, \overline{a_3}, \dots, \overline{a_n}$ \end{itemize} $$TS_V = \bigcup_{w \in V^*} w \liegendesE \overline{w}$$\\ \hspace*{50mm} ist die \underline{Twin-Schuffel-Sprache} "uber V \end{definition*} \begin{note} \begin{align*} & |v| = 1: TS_v \textnormal{ kontextfrei} & |v| > 1: TS_v \textnormal{ kontextsensitiv, aber nicht kontextfrei} \end{align*} \end{note} \begin{bsp} aab \liegendesE \textcolor{blue}{ca} = \{aab\textcolor{blue}{ca} \textcolor{blue}{ca}aab, \textcolor{blue}{c}aab\textcolor{blue}{a}, aa\textcolor{blue}{c}b\textcolor{blue}{a}, aa\textcolor{blue}{ca}b, $\dots$\} %mach zu hause \end{bsp} %%%%%%%%%%%%%%%%% %Vorlesung 24.05.05 %%%%%%%%%%%%%%%%% \begin{lemma*}[ 3.13] Sei X endliche Menge. Dann existiert ein einfaches Stickersystem $\gamma = (V,\rho,A,D)$ und eine det. gsm g mit $TS_{X} = g(L(\gamma))$ \end{lemma*} \begin{center} \includegraphics[scale=0.4]{gfx/abb22.png} \end{center} Das Bild zeigt $v \liegendesE \overline{v}$. Die wei"sen K"astchen sind $v \in X^*$ und die grauen $\overline{v} \in \overline{X^*}$. Es gilt au"serdem $|$grau$| = |$wei"s$|$. Die gesammte Grafik ist $\in TS_x$ \begin{beweis} \textbf{Idee:} \begin{enumerate} \item wir erzeugen mit $\gamma$ die Sprache L aller W"orter $v^{rev}\#w$ mit $v \in X^*, w \in v \liegendesE \overline{v}$ \item $g(v^{rev} \# w) = w$ \end{enumerate} zu 1.\\ \begin{align*} & V = X \cup \overline{X} \dotcup \{\#\}\\ & \delta = \left\lbrace {a \choose a}: a \in V\right\rbrace \\ & A = \left\lbrace \tabl \#\\ \# \tabr \right\rbrace\\ & D = \{R_a, R_{\overline{a}}: a \in X\} \cup \left\lbrace \left({\epsilon \choose \epsilon}, {\epsilon \choose a}\right) : a \in X \cup \overline{X} \right\rbrace\\ & R_a = \left( {a \choose \epsilon}, {a \choose \epsilon}\right), R_{\overline{a}}= \left({\epsilon \choose a}, {\overline{a} \choose \epsilon}\right)\\ & \gamma = (V,\delta,A,D) \textnormal{ ist einfaches, aber nicht einseitiges Stickersystem.} \end{align*}\\ \texttt{zu zeigen:} $L \subseteq L(\gamma)$\\ \\ Sei $w^{rev} \# v \in L$, d.h. $w \in X^*$, $v \in w \liegendesE \overline{w}$\\ definiere Homomorphismus \begin{align*} & f:&(X \cup \overline{X}) \rightarrow X^*\\ & a \rightarrow a\\ & \overline{a} \rightarrow \epsilon (\textnormal{f"ur }a \in X)\\ & g:(X \cup \overline{X})^* \rightarrow X^*\\ & a \rightarrow \epsilon\\ & \overline{a} \rightarrow a\\ \end{align*} f"ur $0\leq i\leq |v|$ sei $v_i$ der Pr"afix von v der L"ange i\\ \begin{align*} W_{\delta}(V) \ni & \textnormal{\fbox{$f(v_i)^{rev}\#v_i$}} \rightarrow_{\gamma} \textnormal{\fbox{$f(v_{i+1})^{rev} \# v_{i+1}$}}\\ & \textnormal{\fbox{$g(v_i)^{rev}\#$}} \hspace{10mm} \textnormal{\fbox{$g(v_{i+1})^{rev} \#$}}\\ \end{align*} insbesondere also $\tabl \# \\ \# \tabr \rightarrow_{\gamma} ^* \tabl $f(v)^{rev}\#$ \\ $g(v)^{rev}\#$ \tabr {v \choose \epsilon} \rightarrow_{\gamma} ^* \tabl $w^{rev} \# v$ \\ $w^{rev} \# v$ \tabr$\\ $\Rightarrow w^{rev}\#v \in L(\gamma)$, also $L \subseteq L(\gamma)$.\\ \\ \texttt{zu zeigen:} $L(\gamma) \subseteq L$\\ \begin{note} alle Elemente von $LM(\gamma)$ haben Form $\tabl $w^{rev} \# v$ \\ $w^{rev} \# v$ \tabr$ mit $w \in X^*, v \in (X \cup \overline{X})^*$. \end{note} Sei also $w^{rev} \# v \in L(\gamma)$, also\\ $\underbrace{\tabl $\#$\\ $\#$ \tabr \rightarrow_{\gamma} ^* \tabl $w^{rev} \#$ \\ $w^{rev} \#$ \tabr {v \choose \epsilon}}_{\textnormal{nur Regel der Form} R_a \textnormal{ und } R_{\overline{a}}} \rightarrow_{\gamma} ^* \tabl $w^{rev} \# v$ \\ $w^{rev} \# v$ \tabr$\\ Reihenfolge dieser Regelanwendungen: v\\ Reihenfolge der Anwendung von $\{R_a : a \in X\}$: w\\ \hspace*{51mm}$\{R_{\overline{a}} : a \in X\}$: w\\ $\Rightarrow v \in w \liegendesE \overline{w}$, also $w^{rev} \# v \in L$\\ $\Rightarrow L(\gamma) \subseteq L$\\ zu 2.\\ \begin{center} \includegraphics[scale=0.5]{gfx/abb23.png} \end{center} \begin{flushright}\texttt{q.e.d.}\end{flushright} \end{beweis} \begin{lemma*} [ 3.14] Sei L eine r.e. Sprache. Dann existiert det. gsm g und eine endliche Menge X mit $L=g(TS_x)$. \end{lemma*} \begin{beweis} Sei $G = (N,T,S,P)$ Grammatik mit L = L(G).\\ \textbf{Idee:} \begin{enumerate} \item erfinde Kodierung von G -- Ableitung durch W"orter "uber $X \cup \overline{X} \rightarrow$ Menge $C \subseteq (X \cup \overline{X})^*$ \item zeige $C=L_1 \cap TS_x$ f"ur eine reg. Menge $L_1$ \item f"ur $w \in C$ kann abgeleitetes Wort durch det. gsm berechnet werden. \end{enumerate} zum Beweis:\\ $$X:= N \cup T \dotcup \{\textnormal{\euro{}} \}$$ \begin{enumerate} \item Kodierung:\\ Sei $S=w_0 \rightarrow_G w_1 \rightarrow_G w_2 \dots \rightarrow_G w_1 \in T^*$ G -- Ableitung\\ $\Rightarrow$ es gibt $u_i, v_i \in (N \cup T)^*, (l_i,r_i) \in P$ mit\\ \hspace*{5mm}$w_i = u_il_iv_i$ \& $w_{i+1}=u_ir_iv_i$ f"ur $0 \leq i < n$\\ kodiere Ableitung wie folgt: \begin{align*} \textnormal{\euro{}} w_n & \textnormal{\euro{}} \overbrace{u_{n-1} l_{n-1} v_{n-1}}^{w_{n-1}} \textnormal{\euro{}} \overbrace{ u_{n-2}l_{n-2} v_{n-2}}^{w_{n-2}} \dots \textnormal{\euro{}} \overbrace{ u_0l_0v_0}^{w_{0}}\\ & \overline{\textnormal{\euro{}}} \underbrace{\overline{u_{n-1}}\overline{r_{n-1}}\overline{v_{n-1}}}_{\overline{w_n}} \overline{\textnormal{\euro{}}} \underbrace{\overline{u_{n-2}}\overline{r_{n-2}}\overline{v_{n-2}}}_{\overline{w_{n-1}}} \dots \overline{\textnormal{\euro{}}} \underbrace{\overline{u_0}\overline{r_0}\overline{v_0}}_{\overline{w_1}} \overline{\textnormal{\euro{}}} \overline{w_0}\\ \end{align*} um Wort "uber $X \cup \overline{X}$ zu erhalten:\\ \begin{itemize} \item mische $u_i$ und $\overline{u_i}$ 'fair' (analog f"ur $v_i$ \& $\overline{v_i}$) \item ersetze ${\textnormal{\euro{}} \over \textnormal{\euro{}}}$ durch $\overline{\textnormal{\euro{}}} \textnormal{\euro{}}$ \end{itemize} $f: X^* \rightarrow (X \cup \overline{X})^*$ mit $f(a) = a\overline{a}$ f"ur $a \in X$\\ $C = \{\textnormal{\euro{}} w_n \overline{\textnormal{\euro{}}} \textnormal{\euro{}} f(u_{n-1}) l_{n-1} \overline{r_{n-1}} f(v_{n-1}) \overline{\textnormal{\euro{}}} \textnormal{\euro{}} f(u_{n-2}) l_{n-2} \overline{r_{n-2}} f(v{_n-2}) \overline{\textnormal{\euro{}}} \textnormal{\euro{}} \dots \overline{\textnormal{\euro{}}} \textnormal{\euro{}} f(n_0) l_0 \overline{r_0} f(v_0) \overline{\textnormal{\euro{}}} \overline{w_0}$\\ $S=W_0 \rightarrow w_1 \dots \rightarrow w_n \in T^*$ \textnormal{ Ableitung in G} $\} \subseteq TS_X$ \begin{itemize} \item nicht regul"ar \item nicht kontextfrei \item kontextsensitiv \end{itemize} %%%%%%%% %Vorlesung 31.05.2005 %%%%%%%% \item $C =L_1 \cap TS_x$ f"ur eine regul"are Menge $L_1$.\\ $Y := \{a\overline{a}=f(a): a \in N \cup T\}$\\ $R:=\{l\overline{r}: (l,r) \in P \}$\\ $L_1= \textnormal{\euro{}}T^* \overline{\textnormal{\euro{}}} (\textnormal{\euro{}} Y^* R Y^* \overline{\textnormal{\euro{}}})^* \overline{S}$\\ $L_1$ist regul"ar\\ $C \subseteq L_1 \cap TS_x$ leicht zu sehen\\ \texttt{zu zeigen:} $L_1 \cap TS_x \subseteq C$ ohne Beweis \item Konstruktion der deterministischen gsm g mit $L=g(TS_x)$\\ leicht f"ur $L=g_1(TS_x \cap L_1)$: \begin{center} \includegraphics[scale=0.4]{gfx/abb24.png} \end{center} $L_1$ regul"ar $\Rightarrow$ es gibt einen deterministischen endlichen Automaten $A = (Q, \iota, \delta, F)$ mit $L_1=L(A)$\\ $g_2 = (Q, X\cup \overline{X}, X \cup \overline{X}, \iota, \delta ', F)$ mit $\delta '(p,a)=(\delta(p,a),a)$ ist deterministische gsm mit $dom g_2 = L_1$ und $g_2(u)=u$ f"ur $u \in L_1$ (d.h. $R(g_2)=\{(u,u): u \in L_1\}$)\\ $\Rightarrow g_1 \circ g_2(TS_x) = g_1(TS_x \cup L_1) = L$\\ nach Lemma 3.11 existiert deterministische gsm g mit $g = g_1 \circ g_2$, also $L=g(TS_x)$\\ \begin{flushright}\texttt{q.e.d}\end{flushright} \end{enumerate} \end{beweis} \begin{satz*} [ 3.15] Sei L r.e. Sprache. Dann existiert ein einfaches Stickersystem $\gamma$ und eine deterministische gsm g mit $L=g(L(\gamma))$. \end{satz*} \begin{beweis} Nach: \begin{itemize} \item Lemma 3.14: $L=g_1(TS_x)$ f"ur eine endliche Menge X \& eine deterministische gsm $g_1$ \item Lemma 3.13: $TS_x = g_2(L(\gamma))$ f"ur ein einfaches Stickersystem $\gamma$ und eine deterministische gsm $g_2$ \end{itemize} $\Rightarrow$ es gibt deterministische gsm g mit: $$g(L(\gamma))=g_1 \circ g_2(L(\gamma))=g_1(TS_x)=L$$ \begin{flushright}\texttt{q.e.d}\end{flushright} \end{beweis} \textbf{n"achstes Ziel:} jede Stickersprache ist gsm-Bild einer Stickersprache "uber nat"urlicher Komplementarit"at.\\ \begin{lemma*}[ 3.16] $V_1, V_2$ Alphabete, $k \in \N$, $L_a \subseteq V_1 ^k$ f"ur $a \in V_2$ und $L_a$ paarweise disjunkt. Dann existiert eine deterministische gsm g mit:\\ $g(u) = a_1a_2 \dots a_n$ f"ur $u \in L_{a_1} L_{a_2} \dots L_{a_n}$ und $g(u)$ undefiniert falls u nicht von dieser Gestalt. \end{lemma*} \begin{beweis} \textbf{Idee:} \begin{itemize} \item merke dir die letzten Buchstaben \item nach k Buchstaben wei"s man, was ausgegeben werden muss. \end{itemize} \begin{align*} & L:= \bigcup_{a \in V_2} L_a \subseteq V_1 ^k \textnormal{ endl.}\\ & Q:= \{u \in V_1 ^*: |u| \leq k-1\} \cup \{\bot\}\\ & \iota := \epsilon\\ & \delta(u,a) = \left\lbrace \begin{tabular}{ll} $(ua,\epsilon)$, & falls $|ua| \leq k-1$ \\ $(\epsilon, b)$ , & falls $ua \in L_b$\\ $(\bot, \epsilon)$ & falls $|ua| = k, ua \notin L$\\ \end{tabular} \right.\\ & \delta(\bot,a) = (\bot, \epsilon)\\ & F = \{\epsilon\}\\ \end{align*} $g = (Q,V_1,V_2, \delta, \iota, F)$ deterministische gsm da $\{L_a: a \in V_2\}$ paarweise disjunkt. \begin{flushright}\texttt{q.e.d}\end{flushright} \end{beweis} Ein Stickersystem $\gamma = (V, \delta A', D)$ hei"st \underline{nat"urlich}, falls $V = \{A,G,C,T\}$ und $\delta = \left\lbrace {A \choose T}, {T \choose A} {G \choose C} {C \choose G} \right\rbrace$. \begin{satz*} [ 3.17] Sei $\gamma_2 = (V_2, \delta_2, A_2 ', D_2)$ ein Stickersystem. Dann existiert ein nat"urliches Stickersystem $\gamma_1 = (V_1, \gamma_1, A_1 ', D_1)$ und eine deterministische gsm g mit $L(\gamma_2) = g(L(\gamma_1))$. Ist $\gamma_2$ einfach$\backslash$ einseitig, so kann $\gamma_1$ einfach$\backslash$ einseitig gew"ahlt werden. \end{satz*} \begin{beweis} Sei $\delta_2 = \{(a_i, b_i) 1 \leq i \leq k\}$ $(a_1 = a_2 \textnormal{ oder } a_1 = b_5 \textnormal{mgl.})$ f"ur $a \in V_2$ sei $L_a = \{ G^i C^{k-i}: a_i = a\} \cup \{C^j G^{k-j}\} \subseteq V_1 ^k$\\ Sei g deterministische gsm aus Lemma 3.16, d.h.:\\ $$g: \left( \bigcup_{a \in V_2} L_a \right) ^* \rightarrow V_2 ^*$$\\ Sei ${u_1 \choose u_2} \tabl $v_1$ \\ $v_2$ \tabr {w_1 \choose w_2} \in W_{\rho_1}(V_1)$ mit $u_i, v_i, w_i \in (\bigcup_{a \in V_2} L_a)^*$\\ $\Rightarrow {g(u_1) \choose g(u_2)} \tabl $g(v_1)$ \\ $g(v_1)$ \tabr {g(w_1) \choose g(w_2)} \in W_{\rho_2}(V_2)$\\ wir schreiben $g^* \left( {u_1 \choose u_2} \tabl $v_1$ \\ $v_2$ \tabr {w_1 \choose w_2} \right)$ f"ur dieses Molek"ul.\\ %%%%%%%% %Mit Alex verglichen %%%%%%%% %%%%%%%% %Vorlesung 07.06.2005 %%%%%%%% $V_1 =\{A,G,C,T\}$\\ $\delta_1 = \{(A,T),(T,A),(G,C),(C,G)\}$\\ $A_1 = \{x \in W_{\delta_1}(V_1):g^*(x)\in A_2\}$\\ $D_2 = \{(x,y) \in W_{\delta_1}(V_1)^2 : (g^*(x), g^*(y)) \in D_2\}$\\ $\gamma_1 := (V_1, \delta_1, A_1, D_1)$ nat"urliches Stickersystem.\\ \\ \texttt{zu zeigen:} $g(L(\gamma_1)) = L(\gamma_2)$\\ Seien $x,y \in W_{\delta_1} (V_1)$ mit $x \rightarrow_{\gamma_1} y$ und $g^*(x), g^*(y)$ definiert, da komplement"are Paare aus $\bigcup L_a$ auf komplement"are Paare aus $V_2$ abgebildet werden, gilt $g^*(x) \rightarrow_{\gamma_2} g^* (y)$.\\ \\ damit:\\ $y \in LM(\gamma_1) \Rightarrow$ es gibt $x \in A_1$ mit $x \rightarrow_{\gamma_1}^* y$\\ $\Rightarrow$ es gibt $x \in A_1$ mit $g^*(x) \rightarrow_{\gamma_2} ^* g^*(y) \& g^*(x) \in A_2$\\ $\Rightarrow g^*(y) \in LM(\gamma_2)$\\ \\ also:\\ $w \in L(\gamma_1) \Rightarrow g(w) \in L(\gamma_2)$, d.h. $g(L(\gamma_1)) \subseteq L(\gamma_2)$\\ \\ umgekehrt sei $w' \in L(\gamma_2)$. Dann existiert $y' = \tabl $w'$ \\ $w''$ \tabr \in LM(\gamma_2)$\\ $\Rightarrow$ es gibt $1 \leq i_e \leq k$ f"ur $1 \leq l \leq |w_1|$ mit\\ \begin{align*} & y' = \tabl $a_{i_1}$ \\ $b_{i_1}$ \tabr \tabl $a_{i_2}$ \\ $b_{i_2}$ \tabr \dots \tabl $a_{i_{|w'|}}$ \\ $b_{i_{|w'|}}$ \tabr\\ & y := \tabl $G^{i_1} C^{k-i_1}$ \\ $C^{i_1} G^{k-i_1}$\tabr \tabl $G^{i_2} C^{k-i_2}$ \\ $C^{i_2} G^{k-i_2}$\tabr \dots \tabl $G^{i_n} C^{k-i_n}$ \\ $C^{i_n} G^{k-i_n}$ \tabr \textnormal{ mit } n = |w'|\\ \end{align*} dann gilt $g^*(y) = y'$, da $y'$ in $\gamma_2$ ableitbar aus einem Axiom, ist y in $\gamma_1$ aus einem Axiom ableitbar, also $L(\gamma_2) \subseteq g(L(\gamma_1))$\\ \textbf{Beobachtung:} ist $\gamma_2$ einfach bzw. einseitig, so ist unser $\gamma_1$ ebenfalls einfach bzw. einseitig. \begin{flushright} \texttt{q.e.d} \end{flushright} \end{beweis} \textbf{Beobachtung:}\\ $\gamma$ einseitiges Stickersystem\\ \hspace*{10mm}$\Rightarrow$ es gibt regul"are Grammatik G mit $L(\gamma) = L(G)$ und diese kann berechnet werden \hspace*{15mm}(vgl. Beweis von Lemma 3.6 und 3.7)\\ \hspace*{10mm}$\Rightarrow$ es gibt endlichen Automaten A mit $L(A) = L(G)$ und dieser kann berechnet werden.\\ $L(A) \neq \oslash$ gdw, ein Finalzustand in A von einem Initialzustand aus erreicht werden kann und dies kann effektiv entschieden werden. Also ist die Frage $L(\gamma) = \oslash$? f"ur einseitiges Stickersysteme entscheidbar (in P l"osbar).\\ \\ \textbf{Frage:} Was ist im allgemeinen Fall?\\ \\ \underline{\textbf{Posts Korrespondenzproblem (PCP):}}\\ \\ \texttt{Eingabe: } endliche Menge von Paaren $(u_i,v_i)$ von W"ortern\\ \texttt{Frage: } existieren Indizes $i_1, i_2, \dots, i_n$ f"ur eine Zahl $n > 0$ mit $u_{i_1}u_{i_2} \dots u_{i_n} = v_{i_1} v_{i_2} \dots v_{i_n}$\\ \begin{satz*} [ 3.18] PCP ist unentscheidbar. \end{satz*} \begin{satz*} [ 3.19] Das Leerheitsproblem f"ur einfache Stickersysteme ist unentscheidbar. \end{satz*} \begin{beweis} wir reduzieren PCP auf Leerheitsproblem\\ Seien $(u_i,v_i) 1 \leq i \leq n$ Paare von W"ortern "uber X\\ $V = X \dotcup \{\# 1,2, \dots , n\}$\\ $\delta = \left\lbrace {a \choose a} : a \in V \right\rbrace $\ \texttt{Idee:}\\ wir konstruieren einfaches Stickersystem $\gamma$ mit $L(\gamma) = \{i_e, i_{e-1} \dots i_1 \# u_{i_1} u_{i_2} \dots u_{i_e} : 1 \leq i_j \leq n_j; u_{i_1}u_{i_2} \dots u_{i_e} = v_{i_1}v_{i_2} \dots v_{i_e}\} =: L$\\ \begin{align*} & A = \left\lbrace {i \choose \epsilon} \tabl \# \\ \# \tabr {u_i \choose \epsilon}: 1 \leq i \leq n \right\rbrace\\ & D = \left\lbrace \left( {i \choose \epsilon}, {u_i \choose \epsilon}\right), \left( {\epsilon \choose i}, {\epsilon \choose v_i}\right) : 1 \leq i \leq n\right\rbrace\\ \end{align*} Sei $\gamma = (V, \delta, A, D)$.\\ \texttt{zu zeigen: } $L\subseteq L(\gamma)$\\ Sei $(i_1, i_2, \dots, i_e)$ L"osung der PCP-Instanz\\ $u_{i_1} u_{i_2} \dots u_{i_n} = v_{i_1} v_{i_2} \dots v_{i_l} => {u_{i_1} \dots u_{i_l} \choose v_{i_1} \dots v_{i_n}} \in W_\delta (V)$\\ f"ur $i \leq j \leq l$\\ \fbox{$i_{j-1} i_{j-2} \dots i_1 \# u_{i_1} u_{i_2} \dots u_{i_{j-1}}$ \hspace{10 mm}}\\ \fbox{$i_{j-1} i_{j-2} \dots i_1 \# V_{i_1} v_{i_2} \dots v_{i_{j-1}}$}\\ \\ $\rightarrow_{\gamma}$\\ \\ \includegraphics[scale=0.3]{gfx/abb25.png}\\ \\ $\rightarrow_{\gamma}$\\ \\ \includegraphics[scale=0.3]{gfx/abb26.png}\\ \\ $\Rightarrow i_{e} i_{e-1} \dots i_1 \# u_{i_1} u_{i_e} \in L(\gamma)$, also $L \subseteq L(\gamma)$. %%%%%%%% %Vorlesung 14.06.05 %%%%%%%% $L(\gamma) \subseteq L$\\ Sei $x \in LM(\gamma)$. Dann gibt es $a,b \in \{1,\dots,n\}^*, u,v \in X^*, x = \tabl $a^{rev} \# u$\\$b^{rev} \# v$ \tabr$ wegen der Gestalt von ??? gilt $a=b$ oder $u=v$.\\ betrachte eine beliebige Herleitung von x aus $\tabl $\#$ \\ $\#$ \tabr$\\ Reihenfolge der Anwendungen von $\left( {i \choose \epsilon}, {u_i \choose \epsilon}\right)$ ist a\\ Reihenfolge der Anwendungen von $\left( {\epsilon \choose i}, {\epsilon \choose v_i}\right)$ ist b\\ \texttt{also:}\\ $u = u_{a_1} u_{a_2} \dots u_{a_n}$ mit $a=a_1a_2 \dots a_n$ und $v = v_{a_1} v_{a_2} \dots v_{a_n}$ wegen $a=b$.\\ Da $u=v$ gilt $a^{rev} \# v \in L \Rightarrow L(\gamma) \subseteq L$\\ $\Rightarrow L(\gamma) = L$\\ also $L(\gamma) \neq \oslash$ gdw. PCP Instanz eine L"osung hat.\\ $\Rightarrow L(\gamma) \neq \oslash ?$ ist unentscheidbar f"ur einfache Stickersysteme.\\ \end{beweis} \begin{korollar*} [ 3.19] Das Leerheitsproblem f"ur nat. und einfache Stickersysteme ist unentscheidbar. \end{korollar*} \begin{beweis} Wir reduzieren das Leerheitsproblem einfacher Stickersysteme auf das obige Problem.\\ Sei $\gamma$ einfaches Stickersystem\\ Satz 3.17 $\Rightarrow \exists$ nat. Stickersystem $\gamma^{'}$ (einfach)\\ \hspace*{19mm} $\exists$ deterministische gsm g mit $L(\gamma) = g(L(\gamma^{'}))$ und im Beweis von Satz 3.17 werden ??? $\gamma$ und g effektiv konstruiert $g(v)$ ist definiert f"ur alle $v\in L(\gamma^{'})$\\ also $L(\gamma) = \oslash$ gdw. $L(\gamma) = \oslash$ \end{beweis} \newpage %%%%%%%% %Kapitel 4 %%%%%%%% \section{Watson -- Crick -- Automaten} \textbf{Idee:} Automat mit 2 Lesek"opfen, die "uber die Str"ange des DNS - Molek"uls vom 3'-Ende zum 5'-Ende laufen.\\ \begin{center} \includegraphics[scale=0.4]{gfx/abb27.png} \end{center} \subsection{Akzeptierte Sprachen} \begin{definition} [ Watson - Crick - Automat] Ein \underline{Watson - Crick - Automat} (WK - Automat) ist ein Tupel $A=(V,\rho,Q,\iota,T,F)$, wobei \begin{itemize} \item V ein Alphabet; \item $\rho \subseteq V^2$ eine Komplementarit"atsrelation; \item Q endliche Zustandsmenge; \item $\iota \in Q$ Initialzustand; \item $T \subseteq Q \times V^* \times V^* \times Q$ endliche Menge von Transitionen; \item $F \subseteq Q$ eine Menge von Finalzust"anden \end{itemize} ist.\\ Eine \underline{Berechnungsfolge} in A ist eine endliche Folge von Transitionen $p = t_1t_2t_3 \choose t_n$ aus T mit $t_i = (q_i,u_i,v_i,q_{n+1})$ f"ur $1 \leq i \leq n$.\\ Sie ist \underline{erfolgreich}, falls $q_i = i$ und $q_{n+1} \in F$ und ${u_1u_2\dots u_n \choose v_1v_2\dots v_n} \in \rho^*$. Das Paar ${u_1u_2\dots v_n \choose v_1v_2 \dots v_n} \in {V^* \choose V^*}$ hei"st die \underline{Beschriftung von p}. \end{definition} \begin{bsp} [ 4.2] $Q = \{q_1, \dots, q_4\}, i = q_1, F=Q$\\ $V = \{a,b\}, \rho = \left\lbrace {a \choose a}, {b \choose b}\right\rbrace$\\ \begin{center} \includegraphics[scale=0.4]{gfx/abb28.png} \end{center} ${u \choose v}$ Beschriftung eines erfolgreichen Pfades\\ $v,u \in a*b*$, d.h. $\exists n, m \in \N$ mit $u=v=a^m b^n$\\ Angenommen dieser Pfad endet im:\\ \hspace*{10mm} $q_1: v=\epsilon \Rightarrow u=\epsilon$ da (u = v)\\ \hspace*{10mm} $q_2: m > 0$, da Transition von $q_1$ nach $q_2$ in Pfad entahlen wegen $u=v$ wird Transition \\ \hspace*{15mm} von $q_1$ nach $q_2$ genau m-mal durchlaufen.\\ \hspace*{15mm}$\Rightarrow$ Transition von $q_2$ nac $q_3$ wird genau m-mal durchlaufen\\ \hspace*{15mm}$\Rightarrow n=m>0$ f"uhrt dazu, dass v keine b's enth"alt.\\ \hspace*{10mm} $q_3:$ u enth"alt aber das v nicht $\rightsquigarrow m u=v$\\ \hspace*{10mm} $q_4: m=n>0$\\ $\Rightarrow L(A) \geq \{a^m b^m | m\in \N\}$ sogar $=L(A)$ also nicht regul"ar.\\ \end{bsp} f"ur $V=\{a_1,\dots, a_n\}$ und $w\in V^*$ sei $\#aw$ die Anzahl der Vorkommen des Buchstaben $a \in V$ in w und $\psi(w) = (\#a_1w, \#a_2w,\dots , \#a_nw) \subseteq \N ^n$\\ Eine Menge $X \subseteq \N ^n$ hei"st \underline{semilinear}, wenn es ein $k \in \N \wedge \overrightarrow{x_i}, \overrightarrow{y_i} \in \N ^n$ f"ur $1\leq i \leq k$ gibt mit\\ $$X= \bigcup_{1\leq i \leq k} \overrightarrow{x_i} + \{l \cdot \overrightarrow{y_i} | l \in \N\}$$ \begin{note} Vereinigung und Schnitt semilinearer Mengen sind semilinear. \end{note} \begin{satz} [ von Parikh 4.3] Sei $L \subseteq V^*$ kontextfrei. Dann ist $\psi(L) \subseteq \N ^{|V|}$ semilinear. \end{satz} %%%%%%%% %Vorlesung 21.06.05 %%%%%%%% \begin{lemma*} [ 4.4] Sei A WK - Automat mit $L(A) \subseteq a^*$. Dann ist $L(A)$ regul"ar. \end{lemma*} \begin{beweis} Sei $A=(V,\rho, Q, \iota, F,T)$ WL - Automat mit $L(A) \subseteq a^*$\\ $A:=\{b \in V: {a \choose b} \in \rho\}$\\ wir konstruieren eine lineare/kontextfreie Grammatik\\ $G = (N,\{a,b\},S,P)$\\ $\curvearrowright$\\ $N=Q$\\ $S = \iota$\\ $P = \{q \rightarrow \epsilon :q\in F\} \cup \{q \rightarrow a^i q' b^j\textnormal{: es gibt }(q,{a \choose v },q') \in T, |v| = j, v \in A^*\}$ \end{beweis} \begin{behauptung} $\{a^m b^m : a^m \in L(A)\} = L(G) \cap \{a^n b^n : n \in \N\}$ \end{behauptung} \begin{beweis} "'$\subseteq$"' Sei $a^m \in L(A)$\\ $\Rightarrow$ es gibt $v \in V^*$ komplement"ar zu $a^m$ und ein erfolgreicher Pfad mit Beschriftung $\tabl $a_m$ \\ b \tabr$\\ $\iota = q_0 \underrightarrow{u_1v_1} q_1 \underrightarrow{u_2v_2} q_2 \dots \underrightarrow{u_nv_n} q_n \in F$\\ $\curvearrowright u_1u_2 \dots u_n = a^m$\\ $\curvearrowright v_1v_2 \dots v_n = v \in A^*$\\ $\Rightarrow (q_i \rightarrow u_{i+1} q_{i+1} b^{v_{i+1}}) \in P$\\ $\Rightarrow \iota \rightarrow u_1q_1b^{v_1} \rightarrow u_1u_2 q_2 b^{v_2} b^{v_1} \dots \rightarrow u_1u_2 \dots u_n q_n b^{v_n v_{n-1} \dots v_1}$\\ $\rightarrow a^mb^m$\\ also "'$\subseteq$"' ist gezeigt. \end{beweis} \begin{beweis} "'$\supseteq$"'\\ Sei $\iota = q_0 \rightarrow_G a^{m_1}q_1 b^{n_1} \rightarrow_G a^{m_1} a^{m_2} q_2 b^{n_2} b^{n_1} \dots \rightarrow_G a^{m_1} a^{m_2} \dots a^{m_k} q_{k} b^{n_k} b^{n_{k-1}} \dots b^{n_1} \rightarrow_G a^{m_1 \dots m_k} b^{n_1 + n_2 \dots n_k} \in \{a^n b^n: n \in \N\}$ Ableitung in G\\ $\Rightarrow q_k \in F$\\ es gibt Transitionen $(q_i,a^{m_{i+1}}, v_{i+1}, q_{i+1}) \in T$ mit $ v_{i+1} \in A^*, |v_{i+1}| = u_{i+1}$\\ $q_0 \underrightarrow{(a^{m_1 v_1})} q_1 \underrightarrow{(a^{m_2} v_2)} q_2 \dots \underrightarrow{a^{m_k}v_k} q_k$\\ ist ein Pfad in A.\\ $q_0 = \iota$\\ $q_k \in F$\\ $v = v_1v_2 \dots v_k \in A^*$\\ $|v| = n_1 + n_2 \dots + n_k = m_1 + m_2 + \dots m_k = m$\\ also ist die Beschriftung ${a^m \choose v} \in \rho^*$\\ $\Rightarrow$ Pfad erfolgreich $\Rightarrow a^m \in L(A)$\\ \hspace*{30mm} $\Rightarrow a^mb^m \in$ linker Seite\\ f"ur $w \in \{a,b\}^*$ sei $\psi(w) = (\#_a w, \#_m w)$\\ $\curvearrowright$ Anwendung des Satz von Parikh: $\psi (L(G))$ semilinear\\ $\Rightarrow \psi (L(G)) \cap \{(p,p):p \in \N\}$ ist semilinear\\ $\Rightarrow_{Behauptung} \psi (\{a^m b^m : a^m \in L(A)\}) = \{(m,m): a^m \in L(A)\}$\\ $\Rightarrow \{m:a^m \in L(A)\}$ semilinear\\ $\Rightarrow L(A) \cap a^* = L(A)$ regul"ar\\ \begin{flushright} \texttt{q.e.d.}\end{flushright} \end{beweis} \begin{satz*} [ 4.5] $\{L(A)\textnormal{: A WL - Automat}\} \subseteq CS$ \end{satz*} \begin{beweis} $L = \{a^p\textnormal{: p Primzahl}\} \in CS \backslash REG$\\ Nach Lemma 4.4 sind die Sprachklassen also verschieden.\\ Mitgliedschaft von $L(A)$ in CS wird durch linear platzbeschr"ankte TM (LBA) bewiesen\\ \begin{flushright} \texttt{q.e.d.}\end{flushright} \end{beweis} Ein WK - Automat $A = (V,\rho, Q, \iota, F,T)$ hei"st \underline{einfach}, falls f"ur jedes Tupel $(p,u,v,q) \in T$ gilt $ u = \epsilon$ oder $v = \epsilon$\\ \begin{lemma*} [ 4.6] $A'=(V,\rho,Q',\iota',F',T')$ mit $L(A') = L(A) \cup \{\epsilon\}$ und $Q'=F'$ \end{lemma*} \begin{beweis} \texttt{1. Idee:}\\ Kopf 1 immer auf ungerader Position\\ Kopf 2 immer auf gerader\\ (au"ser am Anfang und bei Akzeptanz)\\ \texttt{2. Idee:}\\ K"opfe immer schon weiter rechts, unbearbeiteter Teil der Eingabe im Zustand gemerkt.\\ \\ %%%%%%%% %Vorlesung 28.06.05 %%%%%%%% w"ahle $m \geq 0$ so, dass alle W"orter in Transitionen von A k"urzer sind (d.h. $T \leq Q \times V^{