diff options
Diffstat (limited to 'mc')
| -rw-r--r-- | mc/n1.lyx | 25 | ||||
| -rw-r--r-- | mc/n2.1.dot | 4 | ||||
| -rw-r--r-- | mc/n2.1.tex | 4 | ||||
| -rw-r--r-- | mc/n2.lyx | 351 | ||||
| -rw-r--r-- | mc/n3.lyx | 200 | ||||
| -rw-r--r-- | mc/n4.lyx | 37 | ||||
| -rw-r--r-- | mc/n5.lyx | 125 | ||||
| -rw-r--r-- | mc/n6.lyx | 39 | ||||
| -rw-r--r-- | mc/n7.lyx | 153 | ||||
| -rw-r--r-- | mc/n8.lyx | 88 |
10 files changed, 471 insertions, 555 deletions
@@ -103,7 +103,7 @@ cadena \end_inset es un elemento de -\begin_inset Formula $\Sigma^{*}\coloneqq \bigcup_{n\in\mathbb{N}}\Sigma^{n}$ +\begin_inset Formula $\Sigma^{*}\coloneqq\bigcup_{n\in\mathbb{N}}\Sigma^{n}$ \end_inset , que solemos escribir como @@ -136,7 +136,11 @@ concatenación \begin_inset Formula $\Sigma^{*}$ \end_inset - es un monoide con la concatenación de cadenas. + es un monoide con la concatenación de cadenas, y llamamos +\begin_inset Formula $\epsilon$ +\end_inset + + a su elemento neutro. Dada \begin_inset Formula $u=u_{1}\cdots u_{n}\in\Sigma^{*}$ \end_inset @@ -902,7 +906,7 @@ Para dibujar un NFA \begin_inset Formula $q\in Q$ \end_inset - con su etiqueta dentro, o un círculo doble si + con su etiqueta dentro, o un doble círculo si \begin_inset Formula $q\in F$ \end_inset @@ -966,7 +970,7 @@ También podemos representar un NFA con una tabla con un estado por fila, \begin_inset Formula $\epsilon$ \end_inset - cuyas celdas contienen los valores de la función de transición. +, cuyas celdas contienen los valores de la función de transición. \end_layout \begin_layout Section @@ -2154,7 +2158,7 @@ Demostración: es final. Finalmente, -\begin_inset Formula $L\cap M=\overline{\overline{L}\cap\overline{M}}$ +\begin_inset Formula $L\cap M=\overline{\overline{L}\cup\overline{M}}$ \end_inset y @@ -2248,7 +2252,7 @@ Demostración: \end_inset con -\begin_inset Formula $|w|\geq p$ +\begin_inset Formula $n\coloneqq|w|\geq p$ \end_inset y @@ -2259,7 +2263,8 @@ Demostración: \begin_inset Formula $q_{i+1}=\delta(q_{i},w_{i+1})$ \end_inset -, como +. + Como \begin_inset Formula $\{q_{0},\dots,q_{p}\}\subseteq Q$ \end_inset @@ -2293,7 +2298,7 @@ Demostración: \end_inset , -\begin_inset Formula $|y|\geq0$ +\begin_inset Formula $|y|>0$ \end_inset , @@ -2388,8 +2393,8 @@ pumping length \end_layout \begin_layout Standard -Los autómatas sencillos son demasiado sencillos como para teorizar sobre - lo computable o no computable debido a su falta de memoria. +Los autómatas finitos son demasiado sencillos para teorizar sobre lo computable + o no computable debido a su falta de memoria. \end_layout \end_body diff --git a/mc/n2.1.dot b/mc/n2.1.dot index c7c9b48..59eb2ff 100644 --- a/mc/n2.1.dot +++ b/mc/n2.1.dot @@ -5,8 +5,8 @@ digraph G { q4[shape=doublecircle, label=""] begin -> q1 q1 -> q2[label="e, e->$",texlbl="$\epsilon, \epsilon \to \$$"] - q2 -> q2[label="0, e->0",texlbl="$\begin{matrix}0, \epsilon \to 0\\1, \epsilon \to 1\\\ \end{matrix}$"] + q2 -> q2[label="0, e->#",texlbl="$0, \epsilon \to \#$"] q2 -> q3[label="c, e->e",texlbl="$c, \epsilon \to \epsilon$"] - q3 -> q3[label="0, 0->x",texlbl="$\begin{matrix}0, 0 \to \epsilon\\1, 1 \to \epsilon\\\ \end{matrix}$"] + q3 -> q3[label="1, #->e",texlbl="$1, \# \to \epsilon$"] q3 -> q4[label="e, $->e",texlbl="$\epsilon, \$ \to \epsilon$"] } diff --git a/mc/n2.1.tex b/mc/n2.1.tex index 3feb215..2a38805 100644 --- a/mc/n2.1.tex +++ b/mc/n2.1.tex @@ -9,13 +9,13 @@ \draw (120.6bp,29.5bp) node {$\epsilon, \epsilon \to \$$}; % Edge: q2 -> q2 \draw [->] (172.45bp,37.167bp) .. controls (169.37bp,47.664bp) and (172.76bp,58.0bp) .. (182.6bp,58.0bp) .. controls (189.06bp,58.0bp) and (192.74bp,53.549bp) .. (192.75bp,37.167bp); - \draw (182.6bp,65.5bp) node {$\begin{matrix}0, \epsilon \to 0\\1, \epsilon \to 1\\\ \end{matrix}$}; + \draw (182.6bp,65.5bp) node {$0, \epsilon \to \#$}; % Edge: q2 -> q3 \draw [->] (200.79bp,22.0bp) .. controls (220.49bp,22.0bp) and (253.02bp,22.0bp) .. (286.44bp,22.0bp); \draw (243.6bp,29.5bp) node {$c, \epsilon \to \epsilon$}; % Edge: q3 -> q3 \draw [->] (294.45bp,37.167bp) .. controls (291.37bp,47.664bp) and (294.76bp,58.0bp) .. (304.6bp,58.0bp) .. controls (311.06bp,58.0bp) and (314.74bp,53.549bp) .. (314.75bp,37.167bp); - \draw (304.6bp,65.5bp) node {$\begin{matrix}0, 0 \to \epsilon\\1, 1 \to \epsilon\\\ \end{matrix}$}; + \draw (304.6bp,65.5bp) node {$1, \# \to \epsilon$}; % Edge: q3 -> q4 \draw [->] (322.86bp,22.0bp) .. controls (342.7bp,22.0bp) and (375.68bp,22.0bp) .. (410.35bp,22.0bp); \draw (366.6bp,29.5bp) node {$\epsilon, \$ \to \epsilon$}; @@ -196,7 +196,7 @@ PDA \series default ) es una tupla -\begin_inset Formula $(Q,\Sigma,\Gamma,\delta,A_{0},q_{0},F)$ +\begin_inset Formula $(Q,\Sigma,\Gamma,\delta,A_{0},q_{0})$ \end_inset similar a un PDA pero sin @@ -371,7 +371,8 @@ Podemos suponer que una transición añade o elimina más de un elemento de \begin_inset Formula $\delta:Q\times\Sigma_{\epsilon}\times\Gamma^{*})\to{\cal P}(Q\times\Gamma^{*})$ \end_inset -), lo que equivale a añadir algunos estados intermedios en la transición. +), lo que equivale a tener varios estados intermedios en la transición para + primero quitar elementos y luego añadir. \end_layout \begin_layout Standard @@ -544,31 +545,31 @@ GLC \begin_inset Formula $(V,\Sigma,{\cal R},S)$ \end_inset -, donde -\begin_inset Formula $\Sigma$ -\end_inset - - es un alfabeto de + formada por un \series bold -símbolos terminales +alfabeto de variables \series default -, + \begin_inset Formula $V$ \end_inset - es un alfabeto de +, un alfabeto de \series bold -variables +símbolos terminales \series default + +\begin_inset Formula $\Sigma$ +\end_inset + disjunto de \begin_inset Formula $V$ \end_inset -, +, un conjunto finito \begin_inset Formula ${\cal R}$ \end_inset - es un conjunto finito de + de \series bold reglas de producción \series default @@ -580,14 +581,14 @@ reglas de producción \begin_inset Formula $S\to w$ \end_inset -, y -\begin_inset Formula $S\in V$ -\end_inset - - es la +, y una \series bold variable inicial \series default + +\begin_inset Formula $S\in V$ +\end_inset + . Se puede representar con una línea por cada variable \begin_inset Formula $T\in V$ @@ -602,7 +603,7 @@ variable inicial \end_inset , donde -\begin_inset Formula $\{w_{1},\dots,w_{n}\}=\{w\mid(T,w)\in V\}$ +\begin_inset Formula $\{w_{1},\dots,w_{n}\}=\{w\mid(T,w)\in{\cal R}\}$ \end_inset . @@ -625,22 +626,6 @@ Dadas \begin_inset Formula $(R\to x)\in{\cal R}$ \end_inset -, y -\begin_inset Formula $v\Rightarrow^{*}w$ -\end_inset - - si -\begin_inset Formula $v=w$ -\end_inset - - o existe -\begin_inset Formula $x\in(V\cup\Sigma)^{*}$ -\end_inset - - tal que -\begin_inset Formula $v\Rightarrow x\Rightarrow^{*}w$ -\end_inset - . Una \series bold @@ -658,6 +643,18 @@ derivación \begin_inset Formula $v_{i}\Rightarrow v_{i+1}$ \end_inset +, y escribimos +\begin_inset Formula $v\Rightarrow w$ +\end_inset + + si existe una derivación que empieza por +\begin_inset Formula $v$ +\end_inset + + y termina por +\begin_inset Formula $w$ +\end_inset + . El \series bold @@ -709,8 +706,8 @@ Dada una GLC \begin_inset Formula $uRv\Rightarrow uxv$ \end_inset - en la derivación de -\begin_inset Formula $S$ + en la derivación +\begin_inset Formula $S\Rightarrow^{*}w$ \end_inset , aristas de @@ -726,7 +723,7 @@ Dada una GLC \series bold derivación por la izquierda \series default - es una derivación en la que, en cada paso + es una en la que, en cada paso \begin_inset Formula $uRv\Rightarrow uxv$ \end_inset @@ -805,7 +802,7 @@ Para{$A \backslash to \backslash -lambda +epsilon \backslash in{ \backslash @@ -818,7 +815,7 @@ cal R}$}{ \backslash to \backslash -varepsilon$ de ${ +epsilon$ de ${ \backslash cal R}$ \backslash @@ -859,16 +856,11 @@ cal R}$ para cada $w'$ resultante de \begin_layout Plain Layout - excepción de que si habíamos eliminado $B + excepción de que no añadimos $B \backslash to \backslash -lambda$ no la -\end_layout - -\begin_layout Plain Layout - - volvemos a añadir +epsilon$ \backslash ; \end_layout @@ -1234,17 +1226,21 @@ in F$}{% \begin_layout Plain Layout - añadir $(q_{ + añadir $q \backslash -text a}, +to^{ \backslash -epsilon)$ a $ +epsilon, \backslash -delta(q, +epsilon \backslash -epsilon, +to +\backslash +epsilon}q_{ \backslash -epsilon)$} +text a}$ a $ +\backslash +delta$} \end_layout \begin_layout Plain Layout @@ -1275,17 +1271,21 @@ Gamma$}{% \begin_layout Plain Layout - añadir $(q_{ + añadir $q_{ \backslash -text a}, +text a} \backslash -epsilon)$ a $ +to^{ \backslash -delta(q_{ +epsilon,x \backslash -text a}, +to +\backslash +epsilon}q_{ +\backslash +text a}$ a $ \backslash -epsilon,x)$} +delta$} \end_layout \begin_layout Plain Layout @@ -1532,19 +1532,23 @@ epsilon \begin_layout Plain Layout - (r,u) + p \backslash -in +to^{q, \backslash -delta(p,a, +epsilon \backslash -epsilon);(q, +to u}r,s \backslash -epsilon) +to^{b,u +\backslash +to +\backslash +epsilon}q \backslash in \backslash -delta(s,b,u)% +delta% \end_layout \begin_layout Plain Layout @@ -1624,18 +1628,10 @@ Nótese que sólo probamos \end_inset equivale al PDAD -\begin_inset Formula $(Q,\Sigma,\{\$\},\delta',\$,q_{0},F)$ -\end_inset - - con -\begin_inset Formula -\begin{align*} -\delta'(q,a\in\Sigma,\epsilon) & =\{(\delta(q,a),\epsilon)\}; & \delta'(q,a,x) & =\emptyset. -\end{align*} - +\begin_inset Formula $(Q,\Sigma,\{\$\},\{(q,a,\epsilon,\delta(q,a),\epsilon)\}_{q\in Q}^{a\in\Sigma},\$,q_{0},F)$ \end_inset -(En esta notación se usa la primera expresión aplicable, por columnas.) +. \end_layout \begin_layout Description @@ -1646,7 +1642,21 @@ Nótese que sólo probamos \begin_inset Formula $L=\{0^{n}c1^{n}\}_{n\in\mathbb{N}}$ \end_inset - no es un lenguaje regular. + es reconocido por el PDAD +\size small +de la figura +\begin_inset CommandInset ref +LatexCommand ref +reference "fig:pdad" +plural "false" +caps "false" +noprefix "false" + +\end_inset + + +\size default +, pero no es regular. Si lo fuera, tendría una \emph on \lang english @@ -1686,18 +1696,18 @@ pumping length \end_inset . - Sin embargo, -\begin_inset Formula $L$ -\end_inset - -, es reconocido por el -\size small -PDAD \end_layout \begin_deeper \begin_layout Standard \align center +\begin_inset Float figure +wide false +sideways false +status open + +\begin_layout Plain Layout +\align center \begin_inset ERT status open @@ -1734,6 +1744,33 @@ end{tikzpicture} \end_layout +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +\begin_inset CommandInset label +LatexCommand label +name "fig:pdad" + +\end_inset + +PDAD de +\begin_inset Formula $\{0^{n}c1^{n}\}_{n\in\mathbb{N}}$ +\end_inset + +. +\end_layout + +\end_inset + + +\end_layout + +\end_inset + + +\end_layout + \end_deeper \begin_layout Description \begin_inset Formula $2\subseteq3]$ @@ -1760,10 +1797,9 @@ end{tikzpicture} con \begin_inset Formula -\begin{align*} -\delta'(q_{\text{s}},\epsilon,\epsilon) & =\{(q_{0},A_{0})\}; & \delta'(q\in F,\epsilon,\epsilon) & =\delta(q,\epsilon,\epsilon)\cup\{(q_{\text{e}},\epsilon)\};\\ -\delta'(q_{\text{e}},\epsilon,x) & =\{(q_{\text{e}},\epsilon)\}; & \delta'(q\in Q,a,x) & =\delta(q,a,x); & \delta'(q,a,x) & =\emptyset. -\end{align*} +\[ +\delta'\coloneqq\delta\cup\{(q_{\text{s}},\epsilon,\epsilon,q_{0},A_{0})\}\cup\{(q,\epsilon,a,q_{\text{e}},\epsilon)\}_{q\in F\cup\{q_{\text{e}}\}}^{a\in\Gamma}. +\] \end_inset @@ -1922,10 +1958,9 @@ En efecto, si con \begin_inset Formula -\begin{align*} -\delta'(q_{\text{s}},\epsilon,\epsilon) & =\{(q_{0},A_{0})\}; & \delta'(q\in Q,a,x\in\Sigma\cup\{\epsilon\}) & =\delta(q,a,x);\\ -\delta'(q\in Q,\epsilon,\$) & =\{(q_{\text{e}},\epsilon)\}; & \delta'(q,a,x) & =\emptyset. -\end{align*} +\[ +\delta'\coloneqq\delta\cup\{(q_{\text{s}},\epsilon,\epsilon,q_{0},A_{0})\}\cup\{(q,\epsilon,\$,q_{\text{e}},\epsilon)\}_{q\in Q}. +\] \end_inset @@ -2056,7 +2091,7 @@ noprefix "false" , luego para que siempre que se acepte una cadena, se pueda aceptar con la pila vacía, y finalmente para que todas las transiciones añadan o eliminen - un elemento de la pila pero no ambos, usando estados intermedios. + un elemento de la pila pero no ambos. Entonces queremos ver que, para \begin_inset Formula $p,q\in Q$ \end_inset @@ -2385,10 +2420,9 @@ Si la secuencia de acciones tiene 0 pasos, debe ser de la forma con \begin_inset Formula -\begin{align*} -\delta(s,\epsilon,A_{0}) & =(l,A_{0}S); & \delta(l,\epsilon,x\in V) & =\{(l,w^{\text{R}})\}_{(x,w)\in{\cal R}};\\ -\delta(l,a,a) & =(l,\epsilon); & \delta(l,\epsilon,A_{0}) & =(e,\epsilon); & \delta(q,a,x) & =\emptyset -\end{align*} +\[ +\delta\coloneqq\{(s,\epsilon,A_{0},l,A_{0}S),(\ell,\epsilon,A_{0},e,\epsilon)\}\cup\{(\ell,a,a,\ell,\epsilon)\}_{a\in\Sigma}\cup\{(\ell,\epsilon,x,l,w^{\text{R}})\}_{(x,w)\in{\cal R}} +\] \end_inset @@ -2586,15 +2620,16 @@ Sean \series bold Lema del bombeo \series default - ( + o \series bold \emph on \lang english pumping lemma -\series default \emph default \lang spanish -): Si +: +\series default + Si \begin_inset Formula $L\in{\cal CF}$ \end_inset @@ -2647,11 +2682,11 @@ Demostración: \begin_inset Formula $b\coloneqq\max_{(A\to v)\in{\cal R}}|v|$ \end_inset -, en cualquier árbol de derivación por +, en cualquier árbol de derivación de \begin_inset Formula $G$ \end_inset -, ningún nodo tiene más de + ningún nodo tiene más de \begin_inset Formula $b$ \end_inset @@ -2700,7 +2735,7 @@ Demostración: \begin_inset Formula $w$ \end_inset - con número de nodos mínimo, cuya altura sera al menos + con número de nodos mínimo, cuya altura será al menos \begin_inset Formula $|V|+1$ \end_inset @@ -2834,7 +2869,7 @@ Demostración: \end_inset una descomposición en las condiciones de dicho lema. - Si o + Si \begin_inset Formula $v$ \end_inset @@ -2859,7 +2894,7 @@ Demostración: \end_inset contienen cada una un sólo tipo de símbolo y, como al menos una de las - 2 no es vacía y hay un tipo de símbolo no contenido en ninguna, + 2 no es vacía, hay un tipo de símbolo no contenido en ninguna, luego \begin_inset Formula $uv^{2}xy^{2}z\in L$ \end_inset @@ -2871,23 +2906,15 @@ Demostración: \end_layout \begin_layout Standard -Dados -\begin_inset Formula $L_{1},L_{2}\in{\cal CF}$ -\end_inset - -: -\end_layout - -\begin_layout Enumerate -\begin_inset Formula $L_{1}\cup L_{2}\in{\cal CF}$ +\begin_inset Formula ${\cal CF}$ \end_inset -. -\end_layout - -\begin_deeper -\begin_layout Standard -Dadas gramáticas + es cerrado para la unión, concatenación y clausura. + +\series bold +Demostración: +\series default + Dadas gramáticas \begin_inset Formula $(V_{1},\Sigma_{1},{\cal R}_{1},S_{1})$ \end_inset @@ -2937,19 +2964,7 @@ Dadas gramáticas \end_inset . -\end_layout - -\end_deeper -\begin_layout Enumerate -\begin_inset Formula $L_{1}L_{2}\in{\cal CF}$ -\end_inset - -. -\end_layout - -\begin_deeper -\begin_layout Standard -La gramática + \begin_inset Formula $G\coloneqq(V_{1}\sqcup V_{2}\sqcup\{S\},\Sigma_{1}\cup\Sigma_{2},{\cal R}_{1}\cup{\cal R}_{2}\cup\{S\to S_{1}S_{2}\},S)$ \end_inset @@ -3011,19 +3026,7 @@ La gramática \end_inset . -\end_layout - -\end_deeper -\begin_layout Enumerate -\begin_inset Formula $L_{1}^{*}\in{\cal CF}$ -\end_inset - -. -\end_layout - -\begin_deeper -\begin_layout Standard -La gramática + Finalmente, \begin_inset Formula $G\coloneqq(V_{1}\sqcup\{S\},\Sigma_{1},{\cal R}_{1}\cup\{S\to S_{1}S,S\to\epsilon\},S)$ \end_inset @@ -3104,17 +3107,16 @@ La gramática . \end_layout -\end_deeper -\begin_layout Enumerate -En general -\begin_inset Formula $L_{1}\cap L_{2}\notin{\cal CF}$ +\begin_layout Standard +\begin_inset Formula ${\cal CF}$ \end_inset -. -\end_layout - -\begin_deeper -\begin_layout Standard + no es cerrado para la intersección, el complemento y la diferencia. + +\series bold +Demostración: +\series default + \begin_inset Formula $L_{1}\coloneqq\{a^{n}b^{n}c^{m}\}_{n,m\in\mathbb{N}}$ \end_inset @@ -3153,49 +3155,18 @@ B & \to bBc\mid\epsilon \end_inset . -\end_layout - -\end_deeper -\begin_layout Enumerate -En general -\begin_inset Formula $\overline{L_{1}}\notin{\cal CF}$ -\end_inset - -. -\end_layout - -\begin_deeper -\begin_layout Standard -Si lo fuera, sería siempre -\begin_inset Formula $L_{1}\cap L_{2}=\overline{\overline{L_{1}}\cup\overline{L_{2}}}\in{\cal CF}\#$ -\end_inset - -. -\end_layout - -\end_deeper -\begin_layout Enumerate -En general -\begin_inset Formula $L_{1}\setminus L_{2}\notin{\cal CF}$ -\end_inset - -. -\end_layout - -\begin_deeper -\begin_layout Standard -Si lo fuera, como -\begin_inset Formula $\Sigma^{*}\in{\cal CF}$ + Si fuera cerrado para la diferencia, lo sería para el complemento ya que + +\begin_inset Formula $\overline{L}=\Sigma^{*}\setminus L$ \end_inset - sería siempre -\begin_inset Formula $\overline{L_{1}}=\Sigma^{*}\setminus L_{1}\in{\cal CF}$ +, y entonces lo sería para la intersección ya que +\begin_inset Formula $L_{1}\cap L_{2}=\overline{\overline{L_{1}}\cup\overline{L_{2}}}$ \end_inset . \end_layout -\end_deeper \begin_layout Standard Los autómatas de pila no son un buen modelo de computación, pues un ordenador puede reconocer si una cadena está en @@ -111,8 +111,7 @@ Cambridge \lang spanish probaron, de forma independiente, que no. Para ello tuvieron que definir formalmente este tipo de procesos, llamados - algoritmos. - Church a partir de su + algoritmos, Church a partir de su \series bold cálculo \series default @@ -312,37 +311,25 @@ posición de la cabeza de lectura/escritura . Podemos representar una configuración -\begin_inset Formula $(c_{0}\cdots c_{n}\text{BB}\cdots\text{B}\cdots,q,k)$ -\end_inset - -, donde -\begin_inset Formula $k\leq n$ -\end_inset - - y solo se da -\begin_inset Formula $c_{n}=\text{B}$ -\end_inset - - si -\begin_inset Formula $c_{j}=\text{B}$ -\end_inset - - para todo -\begin_inset Formula $c_{j}\geq k$ +\begin_inset Formula $(c,q,p)$ \end_inset -, como + como \begin_inset Quotes cld \end_inset -\begin_inset Formula $c_{0}\cdots c_{k-1}qc_{k}\cdots c_{n}$ +\begin_inset Formula $c_{0}\cdots c_{p-1}qc_{p}\cdots c_{n}$ \end_inset \begin_inset Quotes crd \end_inset +, donde +\begin_inset Formula $n\ge\max(\{n\mid c_{n}\neq\text{B}\}\cup\{p-1\})$ +\end_inset + . \end_layout @@ -356,19 +343,7 @@ configuración inicial \end_inset es -\begin_inset Formula $(c,q_{0},0)$ -\end_inset - - con -\begin_inset Formula $c_{0},\dots,c_{|w|-1}=w$ -\end_inset - - y -\begin_inset Formula $c_{k}=\text{B}$ -\end_inset - - para -\begin_inset Formula $k\geq|w|$ +\begin_inset Formula $q_{0}w$ \end_inset . @@ -448,7 +423,7 @@ rechaza \begin_inset Formula $w$ \end_inset -, o bien no termina. +, y puede no terminar. \end_layout \begin_layout Standard @@ -556,11 +531,11 @@ Ejecutar una u otra instrucción según el símbolo leído y los \begin_inset Formula $n$ \end_inset - anteriores para cierto + anteriores para \begin_inset Formula $n$ \end_inset -. + fijo. \end_layout \begin_deeper @@ -586,7 +561,7 @@ Se mueve \begin_inset Formula $\overline{x_{1}x_{2}}$ \end_inset -, etc., hasta llegar a la posición inicial en el estado +, etc., hasta llegar al estado \begin_inset Formula $\overline{x_{1}\cdots x_{n}}$ \end_inset @@ -600,7 +575,7 @@ Ejecutar una instrucción mientras el símbolo leído cumpla una condición. \begin_deeper \begin_layout Standard -Para estos símbolos, pasar a la instrucción, que termina volviendo a la +Para estos símbolos, pasar a la instrucción, que al terminar vuelve a la comprobación. Para el resto, pasar a la siguiente. \end_layout @@ -629,7 +604,7 @@ Se añade un nuevo estado inicial \begin_inset Formula $\$$ \end_inset - y, en bucle, se mueve a la derecha y se escribe el símbolo en la posición + y, en bucle, se mueve a la derecha y se escribe el símbolo de la posición anterior, hasta que este sea B. Entonces se va moviendo a la izquierda hasta encontrar \begin_inset Formula $\$$ @@ -644,7 +619,7 @@ Se añade un nuevo estado inicial \begin_inset Formula $\$$ \end_inset - al principio, de modo que detectar el límite izquierdo de la cinta es detectar + al principio, con lo que detectar el límite izquierdo de la cinta es detectar \begin_inset Formula $\$$ \end_inset @@ -684,12 +659,8 @@ Se usan estados en ciclo. Mientras no se lea B, se pasa al estado siguiente si se lee el símbolo o al mismo en otro caso, y se mueve a la derecha. - En el último estado, antes de hacer esto, si se detecta el símbolo se hace - la acción a realizar cada -\begin_inset Formula $n$ -\end_inset - - apariciones. + En el último estado, antes de hacer esto, se detecta si está el símbolo + y se actúa en consecuencia. \end_layout \end_deeper @@ -838,7 +809,7 @@ menos expresivo \begin_inset Formula $\text{MOD}_{1}$ \end_inset -; +, en cuyo caso es \series bold equivalente \series default @@ -851,10 +822,6 @@ equivalente \end_inset , si -\begin_inset Formula $\text{MOD}_{1}\preceq\text{MOD}_{2}$ -\end_inset - - y \begin_inset Formula $\text{MOD}_{2}\preceq\text{MOD}_{1}$ \end_inset @@ -870,15 +837,7 @@ estrictamente menos expresivo \begin_inset Formula $\text{MOD}_{1}\prec\text{MOD}_{2}$ \end_inset -, si -\begin_inset Formula $\text{MOD}_{1}\preceq\text{MOD}_{2}$ -\end_inset - - pero -\begin_inset Formula $\text{MOD}_{2}\npreceq\text{MOD}_{1}$ -\end_inset - -. +, en otro caso. \end_layout \begin_layout Standard @@ -944,7 +903,6 @@ stay \begin_deeper \begin_layout Standard -Claramente \begin_inset Formula $\text{MT}\subseteq\text{SMT}$ \end_inset @@ -956,7 +914,7 @@ Claramente \begin_inset Formula $\text{MT}$ \end_inset - sustituyendo una transición con S con una que primero se mueve a la derecha + cambiando cada transición con S por una que primero se mueve a la derecha y luego a la izquierda. \end_layout @@ -1136,60 +1094,56 @@ máquinas de Turing multicinta \end_inset es -\begin_inset Formula $(q_{0},w\text{B}\cdots,(\text{B}\cdots)^{k-1})$ +\begin_inset Formula $(q_{0},(w\text{B}\cdots,0),(\text{B}\cdots,0)^{k-1})$ \end_inset . - Definiendo -\begin_inset Formula $\nu:(\Gamma^{\mathbb{N}}\times\mathbb{N})\times(\Gamma\times\{\text{L},\text{R}\})\to\Gamma^{\mathbb{N}}\times\mathbb{N}$ -\end_inset - - de forma que, para -\begin_inset Formula $a,b\in\Gamma$ + Una configuración +\begin_inset Formula $(q,(u_{1},n_{1}),\dots,(u_{k},n_{k}))$ \end_inset -, -\begin_inset Formula $n\in\mathbb{N}$ + lleva a otra +\begin_inset Formula $(r,(v_{1},m_{1}),\dots,(v_{k},m_{k}))$ \end_inset -, -\begin_inset Formula $u\in\Gamma^{n}$ + si, siendo +\begin_inset Formula $\delta(q,u_{1n_{1}},\dots,u_{kn_{k}})=(r,(c_{1},d_{1}),\dots,(c_{k},d_{k}))$ \end_inset - y -\begin_inset Formula $v\in\Gamma^{\mathbb{N}}$ +, para +\begin_inset Formula $i\in\{1,\dots,k\}$ \end_inset , -\begin_inset Formula $\nu((uav,n),(b,\text{R}))=(ubv,n+1)$ +\begin_inset Formula $v_{i}$ \end_inset - y, si -\begin_inset Formula $n>0$ + es como +\begin_inset Formula $u_{i}$ \end_inset -, -\begin_inset Formula $\nu((uav,n),(b,\text{L}))=(ubv,n-1)$ + pero cambiando el término +\begin_inset Formula $n_{i}$ \end_inset -, una configuración -\begin_inset Formula $(q,(u_{1},n_{1}),\dots,(u_{k},n_{k}))$ +-ésimo por +\begin_inset Formula $c$ \end_inset - lleva a otra -\begin_inset Formula $(r,(v_{1},m_{1}),\dots,(v_{k},m_{k}))$ + y, bien +\begin_inset Formula $d_{i}=\text{L}$ \end_inset - dada por -\begin_inset Formula $\delta(q,u_{1n_{1}},u_{2n_{2}},\dots,u_{kn_{k}})=(r,t_{1},\dots,t_{k})$ + y +\begin_inset Formula $m_{i}=n_{i}-1$ \end_inset - y -\begin_inset Formula $(v_{i},m_{i})=\nu((u_{i},n_{i}),t_{i})$ +, bien +\begin_inset Formula $d_{i}=\text{R}$ \end_inset - para cada -\begin_inset Formula $i$ + y +\begin_inset Formula $m_{i}=n_{i}+1$ \end_inset . @@ -1261,7 +1215,7 @@ Claramente una \end_inset por -\begin_inset Formula $\#w(\#\dot{\text{B}})^{k-1}$ +\begin_inset Formula $\#\dot{w}_{1}w_{2}\cdots w_{|w|}(\#\dot{\text{B}})^{k-1}$ \end_inset , vuelve al principio y pasa a @@ -1325,7 +1279,7 @@ Si \end_inset por -\begin_inset Formula $a_{i}$ +\begin_inset Formula $s_{i}$ \end_inset . @@ -1346,6 +1300,22 @@ Si \begin_inset Formula $\dot{x}$ \end_inset +, o si +\begin_inset Formula $x=\#$ +\end_inset + +, rechazar si +\begin_inset Formula $d_{i}=\text{L}$ +\end_inset + + o insertar antes +\begin_inset Formula $\dot{\text{B}}$ +\end_inset + + desplazando el resto a la derecha si +\begin_inset Formula $d_{i}=\text{R}$ +\end_inset + . \end_layout @@ -1473,8 +1443,8 @@ Toda \begin_inset Formula $(Q,\Sigma,\Gamma,\delta,q_{0},q_{\text{F}})$ \end_inset - e intentamos convertirla en una 3-MT, que guardará la entrada en la cinta - 1, simulará la + y la convertimos en una 3-MT, que guardará la entrada en la cinta 1, simulará + la \begin_inset Formula $\text{MTND}$ \end_inset @@ -1500,7 +1470,7 @@ Escribir \begin_inset Formula $c\gets\text{FALSE}$ \end_inset -en el estado del 3-MT. + en el estado. \end_layout \begin_layout Enumerate @@ -1510,7 +1480,7 @@ name "enu:begin-step" \end_inset -Copiar la cinta 1 en la cinta 2, escribiendo +Copiar la cinta 1 en la 2, escribiendo \begin_inset Formula $\#$ \end_inset @@ -1578,7 +1548,7 @@ noprefix "false" \begin_inset Formula $i>|\delta(q,a)|$ \end_inset -, escribir B y moverse a la izquierda en la cinta 3 e ir al paso +, escribir B, moverse a la izquierda en la cinta 3 e ir al paso \begin_inset CommandInset ref LatexCommand ref reference "enu:next-step" @@ -1725,7 +1695,7 @@ Kurt Gödel tesis de Church-Turing \series default , que afirma que esta definición de algoritmo se corresponde con la noción - intuitiva, o la máquina de Turing es el modelo de computación más expresivo + intuitiva, o que la máquina de Turing es el modelo de computación más expresivo posible y todos los modelos suficientemente expresivos son equivalentes a este. \end_layout @@ -1744,12 +1714,12 @@ máquinas con infinitos registros \series bold lenguaje S \series default - (simple), todas equivalentes a las máquinas de Turing. + (simple), todas equivalentes a MT. Un lenguaje de programación es \series bold Turing completo \series default - si es equivalente a las máquinas de Turing. + si es equivalente a MT. \end_layout \begin_layout Section @@ -1820,7 +1790,6 @@ Si se lee B, rechazar (longitud 0). \begin_layout Enumerate Si solo hay un 0, se acepta. - Se vuelve al principio. \end_layout \begin_layout Enumerate @@ -1879,7 +1848,7 @@ Se va leyendo la cadena de izquierda a derecha y, si hay una \begin_inset Formula $c$ \end_inset -, aceptando si no hay ninguno, se vuelve al principio de la cinta, se marca +, aceptando si no hay ninguna, se vuelve al principio de la cinta, se marca con \begin_inset Formula $\#$ \end_inset @@ -2112,8 +2081,7 @@ Tomamos una \begin_inset Formula $\text{MTND}$ \end_inset - que al inicio, de forma no determinista, se quede donde está ejecute una - + que al inicio, de forma no determinista, ejecute una \begin_inset Formula $\text{MT}$ \end_inset @@ -2121,7 +2089,7 @@ Tomamos una \begin_inset Formula $L_{1}$ \end_inset - o una que ejecute + o una que enumere \begin_inset Formula $L_{2}$ \end_inset @@ -2154,11 +2122,7 @@ Sean \begin_inset Formula ${\cal M}_{2}$ \end_inset - una -\begin_inset Formula $\text{MT}$ -\end_inset - - que enumera + una que enumera \begin_inset Formula $L_{2}$ \end_inset @@ -2171,7 +2135,7 @@ Sean \end_inset a la vez sobre dos copias de la entrada (alternándolas), aceptando cuando - ambas hayan aceptado y rechazando si una termina. + ambas hayan aceptado y rechazando si una rechaza. \end_layout \end_deeper @@ -2200,11 +2164,11 @@ Similar al caso decidible pero haciendo todas las simulaciones en paralelo: \begin_deeper \begin_layout Standard -\begin_inset Formula $L_{1}^{*}=\{\lambda\}\cup(L_{1}\setminus\{\lambda\})^{*}$ +\begin_inset Formula $L_{1}^{*}=\{\epsilon\}\cup(L_{1}\setminus\{\epsilon\})^{*}$ \end_inset , por lo que si la entrada es -\begin_inset Formula $\lambda$ +\begin_inset Formula $\epsilon$ \end_inset aceptamos y, en otro caso, hacemos como en el caso anterior pero iterando @@ -2228,8 +2192,8 @@ Algoritmos \end_layout \begin_layout Standard -Las máquinas de Turing y mecanismos generales no solo permiten reconocer - cadenas, sino ejecutar algoritmos en general. +Las máquinas de Turing no solo permiten reconocer cadenas, sino ejecutar + algoritmos en general. La entrada siempre es una cadena, por lo que para que otro tipo de objeto actúe de entrada hay que representarla como una cadena y la máquina de Turing debe decodificar esta representación. @@ -2245,7 +2209,7 @@ Las máquinas de Turing y mecanismos generales no solo permiten reconocer \begin_inset Formula $O$ \end_inset -, y dados objetos + en cierta representación, y dados objetos \begin_inset Formula $O_{1},\dots,O_{n}$ \end_inset @@ -2257,7 +2221,7 @@ Las máquinas de Turing y mecanismos generales no solo permiten reconocer \begin_inset Formula $(O_{1},\dots,O_{n})$ \end_inset -, en cierta representación. +. La \begin_inset Formula $\text{MT}$ \end_inset @@ -439,7 +439,7 @@ input \end_inset que reconoce -\begin_inset Formula $K\coloneqq\{\langle{\cal A},w\rangle\mid \text{la MT \ensuremath{{\cal A}} acepta \ensuremath{w}}\}$ +\begin_inset Formula $K\coloneqq\{\langle{\cal A},w\rangle\mid\text{la MT \ensuremath{{\cal A}} acepta \ensuremath{w}}\}$ \end_inset . @@ -1953,7 +1953,7 @@ Algunos lenguajes decidibles: \end_layout \begin_layout Enumerate -\begin_inset Formula $\text{Acc}^{\text{DFA}}\coloneqq\{\langle{\cal A},w\rangle\mid \text{el DFA \ensuremath{{\cal A}} acepta la cadena \ensuremath{w}}\}$ +\begin_inset Formula $\text{Acc}^{\text{DFA}}\coloneqq\{\langle{\cal A},w\rangle\mid\text{el DFA \ensuremath{{\cal A}} acepta la cadena \ensuremath{w}}\}$ \end_inset . @@ -2044,7 +2044,7 @@ fun m q0 finals w -> contains (==) (sim m w q0) finals \end_deeper \begin_layout Enumerate -\begin_inset Formula $\text{Acc}^{\text{NFA}}\coloneqq\{\langle{\cal A},w\rangle\mid \text{el NFA \ensuremath{{\cal A}} acepta la cadena \ensuremath{w}}\}$ +\begin_inset Formula $\text{Acc}^{\text{NFA}}\coloneqq\{\langle{\cal A},w\rangle\mid\text{el NFA \ensuremath{{\cal A}} acepta la cadena \ensuremath{w}}\}$ \end_inset . @@ -2275,7 +2275,7 @@ fun (states, syms, m, r0, finals) -> \end_layout \begin_layout Enumerate -\begin_inset Formula $\text{Acc}^{\text{PDA}}\coloneqq\{\langle{\cal A},w\rangle\mid \text{el PDA \ensuremath{{\cal A}} acepta la cadena \ensuremath{w}}\}$ +\begin_inset Formula $\text{Acc}^{\text{PDA}}\coloneqq\{\langle{\cal A},w\rangle\mid\text{el PDA \ensuremath{{\cal A}} acepta la cadena \ensuremath{w}}\}$ \end_inset . @@ -2322,7 +2322,7 @@ forma normal de Chomsky \end_layout \begin_layout Enumerate -\begin_inset Formula $\text{Empty}^{\text{DFA}}\coloneqq\{\langle{\cal A}\rangle\mid \text{el DFA }{\cal A}\text{ no acepta ninguna cadena}\}$ +\begin_inset Formula $\text{Empty}^{\text{DFA}}\coloneqq\{\langle{\cal A}\rangle\mid\text{el DFA }{\cal A}\text{ no acepta ninguna cadena}\}$ \end_inset . @@ -2433,7 +2433,7 @@ fun (trans, q0, finals) -> anystring trans finals nil (cons q0 nil) \end_deeper \begin_layout Enumerate -\begin_inset Formula $\text{Empty}^{\text{NFA}}\coloneqq\{\langle{\cal A}\rangle\mid \text{el NFA }{\cal A}\text{ no acepta ninguna cadena}\}$ +\begin_inset Formula $\text{Empty}^{\text{NFA}}\coloneqq\{\langle{\cal A}\rangle\mid\text{el NFA }{\cal A}\text{ no acepta ninguna cadena}\}$ \end_inset . @@ -2446,7 +2446,7 @@ Análogo. \end_deeper \begin_layout Enumerate -\begin_inset Formula $\text{Empty}^{\text{PDA}}\coloneqq\{\langle{\cal A}\rangle\mid \text{el PDA }{\cal A}\text{ no acepta ninguna cadena}\}$ +\begin_inset Formula $\text{Empty}^{\text{PDA}}\coloneqq\{\langle{\cal A}\rangle\mid\text{el PDA }{\cal A}\text{ no acepta ninguna cadena}\}$ \end_inset . @@ -2580,7 +2580,7 @@ numeración de Gödel \series bold computables \series default -, es decir existe una +, es decir, existe una \begin_inset Formula $\text{MT}$ \end_inset @@ -2609,19 +2609,15 @@ Demostración: \begin_inset Formula $f:A\to{\cal P}(A)$ \end_inset -, sea +, sean \begin_inset Formula $B\coloneqq\{x\in A\mid x\notin f(x)\}$ \end_inset -, existe -\begin_inset Formula $y\in A$ -\end_inset - - con -\begin_inset Formula $f(y)=B$ + e +\begin_inset Formula $Y\coloneqq f^{-1}(B)$ \end_inset -, pero si +, si \begin_inset Formula $y\in B$ \end_inset @@ -2641,7 +2637,7 @@ Demostración: \end_layout \begin_layout Standard -Existen lenguajes no recursivamente enumerables, pues el conjunto lenguajes +Existen lenguajes no recursivamente enumerables, pues el conjunto de lenguajes sobre un alfabeto \begin_inset Formula $\Sigma$ \end_inset @@ -2767,7 +2763,7 @@ status open \begin_layout Standard \begin_inset Formula \[ -K\coloneqq\{\langle{\cal M},w\rangle\mid \text{la MT }{\cal M}\text{ acepta con entrada }w\}\in{\cal RE}\setminus{\cal DEC}. +K\coloneqq\{\langle{\cal M},w\rangle\mid\text{la MT }{\cal M}\text{ acepta con entrada }w\}\in{\cal RE}\setminus{\cal DEC}. \] \end_inset @@ -2806,7 +2802,7 @@ Demostración: \end_inset que decide -\begin_inset Formula $\{\langle{\cal M}\rangle\mid {\cal H}\text{ rechaza }\langle{\cal M},\langle{\cal M}\rangle\rangle\}$ +\begin_inset Formula $\{\langle{\cal M}\rangle\mid{\cal H}\text{ rechaza }\langle{\cal M},\langle{\cal M}\rangle\rangle\}$ \end_inset , pero entonces @@ -2854,7 +2850,8 @@ Para un lenguaje \begin_inset Formula $\overline{L}$ \end_inset - hasta que una termine y aceptar o rechazar según cuál termine. + hasta que una termine y aceptar o rechazar según cuál termine y con qué + resultado. \end_layout \begin_layout Standard @@ -81,48 +81,6 @@ \begin_body \begin_layout Standard -Un -\series bold -oráculo -\series default - para un lenguaje -\begin_inset Formula $L$ -\end_inset - - es una caja negra que decide -\begin_inset Formula $L$ -\end_inset - -. - Un lenguaje -\begin_inset Formula $A$ -\end_inset - - se -\series bold -reduce -\series default - a un lenguaje -\begin_inset Formula $B$ -\end_inset - - si existe una -\begin_inset Formula $\text{MT}$ -\end_inset - - que decide -\begin_inset Formula $A$ -\end_inset - - usando un oráculo de -\begin_inset Formula $B$ -\end_inset - -. - -\end_layout - -\begin_layout Standard Una \series bold reducción @@ -144,26 +102,38 @@ reducción \end_inset . - Una función -\begin_inset Formula $f:\Sigma_{1}^{*}\to\Sigma_{2}^{*}$ + Una MT +\begin_inset Formula ${\cal M}$ \end_inset - es + \series bold -computable +computa \series default - si existe una -\begin_inset Formula $\text{MT}$ + una función +\begin_inset Formula $f:\Sigma_{1}^{*}\to\Sigma_{2}^{*}$ \end_inset - que siempre termina y que, para una entrada + si siempre termina y, para \begin_inset Formula $w\in\Sigma_{1}^{*}$ \end_inset -, termina conteniendo en su cinta únicamente +, +\begin_inset Formula ${\cal M}$ +\end_inset + + termina conteniendo en su cinta únicamente \begin_inset Formula $f(w)$ \end_inset +, y entonces +\begin_inset Formula $f$ +\end_inset + + es +\series bold +computable +\series default . Una \series bold @@ -211,6 +181,46 @@ reducir \end_layout \begin_layout Standard +Equivalentemente, un +\series bold +oráculo +\series default + para un lenguaje +\begin_inset Formula $L$ +\end_inset + + es una caja negra que decide +\begin_inset Formula $L$ +\end_inset + +, y un lenguaje +\begin_inset Formula $A$ +\end_inset + + +\series bold +se reduce +\series default + a un lenguaje +\begin_inset Formula $B$ +\end_inset + + si existe una +\begin_inset Formula $\text{MT}$ +\end_inset + + con un oráculo de +\begin_inset Formula $B$ +\end_inset + + que decide +\begin_inset Formula $A$ +\end_inset + +. +\end_layout + +\begin_layout Standard \series bold Teoremas de reducibilidad: @@ -327,7 +337,7 @@ Problema de la parada. \begin_inset Formula \[ -\text{HALT}^{\text{MT}}\coloneqq\{\langle{\cal M},w\rangle\mid {\cal M}\text{ es una MT que para con entrada }w\}\notin{\cal DEC}. +\text{HALT}^{\text{MT}}\coloneqq\{\langle{\cal M},w\rangle\mid{\cal M}\text{ es una MT que para con entrada }w\}\notin{\cal DEC}. \] \end_inset @@ -341,7 +351,7 @@ Sea \begin_inset Formula ${\cal M}'$ \end_inset - es una + una \begin_inset Formula $\text{MT}$ \end_inset @@ -380,7 +390,7 @@ mapping \end_deeper \begin_layout Enumerate -\begin_inset Formula $\text{EMPTY}^{\text{MT}}\coloneqq\{\langle{\cal M}\rangle\mid {\cal M}\text{ es una MT que no acepta ninguna cadena}\}\notin{\cal DEC}$ +\begin_inset Formula $\text{EMPTY}^{\text{MT}}\coloneqq\{\langle{\cal M}\rangle\mid{\cal M}\text{ es una MT que no acepta ninguna cadena}\}\notin{\cal DEC}$ \end_inset . @@ -454,7 +464,7 @@ mapping \end_deeper \begin_layout Enumerate -\begin_inset Formula $\text{Pass}\coloneqq\{\langle{\cal M},w,q\rangle\mid {\cal M}\text{ es una MT que, con entrada }w\text{, pasa por el estado \ensuremath{q}}\}\notin{\cal DEC}$ +\begin_inset Formula $\text{Pass}\coloneqq\{\langle{\cal M},w,q\rangle\mid{\cal M}\text{ es una MT que, con entrada }w\text{, pasa por el estado \ensuremath{q}}\}\notin{\cal DEC}$ \end_inset . @@ -512,7 +522,6 @@ mapping \end_deeper \begin_layout Standard -Un lenguaje \begin_inset Formula $L\in{\cal RE}$ \end_inset @@ -674,7 +683,7 @@ Teorema de Rice: no trivial, \begin_inset Formula \[ -{\cal L}_{P}\coloneqq\{\langle{\cal M}\rangle\mid {\cal M}\text{ es una MT con }L(M)\in P\}\notin{\cal DEC}. +{\cal L}_{P}\coloneqq\{\langle{\cal M}\rangle\mid{\cal M}\text{ es una MT con }L(M)\in P\}\notin{\cal DEC}. \] \end_inset @@ -713,7 +722,7 @@ Demostración: \end_inset . - Si, por ejemplo, + Si \begin_inset Formula $L_{2}=\emptyset$ \end_inset @@ -808,7 +817,7 @@ mapping \begin_inset Formula $L_{1}=\emptyset$ \end_inset - esto permite probar que + por este argumento \begin_inset Formula ${\cal RE}\setminus{\cal L}_{P}\notin{\cal DEC}$ \end_inset @@ -170,7 +170,7 @@ límite superior asintótico \begin_layout Standard Para -\begin_inset Formula $t:\mathbb{N}\to\mathbb{R}^{+}$ +\begin_inset Formula $t:\mathbb{N}\to\mathbb{R}^{\geq0}$ \end_inset , llamamos @@ -190,8 +190,7 @@ clase de complejidad \end_inset . - Nótese que esta magnitud se refiere al lenguaje o problema, no a un algoritmo - concreto. + Esta magnitud se refiere al lenguaje o problema, no a un algoritmo concreto. En general, la clase de complejidad de un problema depende del modelo de computación usado, aun para modelos equivalentes. Este orden no difiere mucho entre modelos deterministas, pero sí entre @@ -252,7 +251,7 @@ Demostración: y luego para aplicarla, actualizando el contenido de las celdas y las posicione s de los cursores. Cada cinta tiene tamaño como mucho -\begin_inset Formula $O(t(n))$ +\begin_inset Formula $O(\max\{t(n),n\})=O(t(n))$ \end_inset , pues en cada transición se añade como mucho un caracter en cada cinta, @@ -265,11 +264,7 @@ s de los cursores. \end_inset de estos, el tiempo total es -\begin_inset Formula $O(t(n)^{2}+n)=O(t(n)^{2})$ -\end_inset - -, usando que -\begin_inset Formula $t(n)\geq n$ +\begin_inset Formula $O(t(n)^{2})$ \end_inset . @@ -383,16 +378,7 @@ backtracking \lang spanish y para evitar la interferencia entre una simulación y la siguiente, por lo que el total de transiciones es como mucho -\begin_inset Formula $O(n+mc^{m})=O(n+f(n)c^{f(n)})$ -\end_inset - -, usando que -\begin_inset Formula $n\leq f(n)$ -\end_inset - -. - Entonces el total es -\begin_inset Formula $O(f(n)c^{f(n)})=O(2^{\log_{2}f(n)+f(n)\log_{2}c})=2^{O(\log_{2}f(n)+f(n)\log_{2}c})=2^{O(f(n))}$ +\begin_inset Formula $O(n+mc^{m})=O(n+f(n)c^{f(n)})=O(f(n)c^{f(n)})=O(2^{\log_{2}f(n)+f(n)\log_{2}c})=2^{O(\log_{2}f(n)+f(n)\log_{2}c)}=2^{O(f(n))}$ \end_inset , y por el teorema anterior, al simular esto en un @@ -419,16 +405,7 @@ Nótese que \begin_inset Formula $3^{n}\neq O(2^{n})$ \end_inset - pero -\begin_inset Formula $3^{n}=2^{\log_{2}3^{n}}=2^{n\log_{2}3}=2^{O(n)}$ -\end_inset - -. - En efecto, claramente -\begin_inset Formula $n\log_{2}3\in O(n)$ -\end_inset - -, pero para cualesquiera + porque para cualesquiera \begin_inset Formula $c,n_{0}\in\mathbb{N}$ \end_inset @@ -444,6 +421,10 @@ Nótese que \begin_inset Formula $n>\log_{\frac{3}{2}}c$ \end_inset +, pero +\begin_inset Formula $3^{n}=2^{\log_{2}3^{n}}=2^{n\log_{2}3}=2^{O(n)}$ +\end_inset + . \end_layout @@ -135,31 +135,6 @@ Los problemas en esta clase se consideran tratables, y el resto intratables. \begin_layout Standard Una -\begin_inset Formula $\text{MT}$ -\end_inset - - -\series bold -computa -\series default - una función -\begin_inset Formula $f:D\subseteq\Sigma^{*}\to\Sigma^{*}$ -\end_inset - - si decide -\begin_inset Formula $D$ -\end_inset - - y, para -\begin_inset Formula $w\in D$ -\end_inset - -, termina conteniendo solo -\begin_inset Formula $f(w)$ -\end_inset - - en su cinta. - Una \series bold función polinómica \series default @@ -219,10 +194,15 @@ representación interna Las formas que hemos usado para representar autómatas, grafos, etc. son razonables, pero no lo es la representación unaria de números, pues - es exponencialmente más larga que una representación en base 2 o más. + es exponencialmente más larga que una representación en base 2 o más que + sí es razonable. \end_layout \begin_layout Standard +\begin_inset Note Comment +status open + +\begin_layout Plain Layout \begin_inset Float algorithm wide false sideways false @@ -362,7 +342,7 @@ Suma \end_layout -\begin_layout Standard +\begin_layout Plain Layout \begin_inset Float algorithm wide false sideways false @@ -506,7 +486,7 @@ Resta saturada \end_layout -\begin_layout Standard +\begin_layout Plain Layout \begin_inset Float algorithm wide false sideways false @@ -648,7 +628,7 @@ Producto \end_layout -\begin_layout Standard +\begin_layout Plain Layout \begin_inset Float algorithm wide false sideways false @@ -844,6 +824,11 @@ Cociente entero \end_layout +\end_inset + + +\end_layout + \begin_layout Standard \begin_inset Float algorithm wide false @@ -886,7 +871,7 @@ in L(G)$, rechaza en otro caso.} \backslash SSi{$w= \backslash -lambda$}{ +epsilon$}{ \end_layout \begin_layout Plain Layout @@ -897,7 +882,7 @@ lSSi{$S \backslash to \backslash -lambda +epsilon \backslash in{ \backslash @@ -922,7 +907,17 @@ $T \backslash gets \backslash -emptyset$ +{((i,j), +\backslash +emptyset) +\backslash +}_{1 +\backslash +leq i +\backslash +leq j +\backslash +leq n}$ \end_layout \begin_layout Plain Layout @@ -931,15 +926,7 @@ emptyset$ \backslash tcp*{{ \backslash -rm Para $ -\backslash -{(i,j) -\backslash -}_{1 -\backslash -leq i<j -\backslash -leq n}$, $T(i,j)$ contiene las variables que generan $w_i +rm $T(i,j)$ contiene las variables que generan $w_i \backslash cdots w_j$.}} \end_layout @@ -1105,6 +1092,9 @@ Algoritmo CYK de programación dinámica para establecer si una cadena está \end_layout \begin_layout Standard +\begin_inset Newpage newpage +\end_inset + Están en \begin_inset Formula ${\cal P}$ \end_inset @@ -1113,6 +1103,10 @@ Están en \end_layout \begin_layout Enumerate +La suma, resta saturada, producto, cociente entero y resto de números naturales. +\end_layout + +\begin_layout Enumerate \begin_inset Formula $\text{RELPRIM}\coloneqq\{\langle x,y\rangle\mid x,y\in\mathbb{N}\text{ son primos relativos}\}$ \end_inset @@ -1135,6 +1129,10 @@ Una forma de comprobarlo es usar el algoritmo de Euclides para ver que . La operación más cara en un paso es el módulo, +\begin_inset Note Comment +status open + +\begin_layout Plain Layout \begin_inset Formula $O(n^{3})$ \end_inset @@ -1148,7 +1146,12 @@ noprefix "false" \end_inset -, y basta ver que el número de pasos es polinómico respecto al tamaño de +, +\end_layout + +\end_inset + + y basta ver que el número de pasos es polinómico respecto al tamaño de la entrada, para lo que vemos que, excluyendo el primer paso, cada 2 pasos \begin_inset Formula $x$ @@ -1238,7 +1241,7 @@ Se añade el nodo \end_inset . - Se acepta si y sólo si + Se acepta si y sólo si al final \begin_inset Formula $t$ \end_inset @@ -1348,22 +1351,21 @@ noprefix "false" \end_deeper \begin_layout Standard -Dados -\begin_inset Formula $L_{1},L_{2}\in{\cal P}$ -\end_inset - -, -\begin_inset Formula $L_{1}\cup L_{2},L_{1}\cap L_{2},\overline{L_{1}},L_{1}L_{2},L_{1}^{*}\in{\cal P}$ +\begin_inset Formula ${\cal P}$ \end_inset -. + es cerrada para unión, intersección, complemento, concatenación y clausura. \series bold Demostración: \series default La unión, intersección y clausura son triviales. - Respecto a la concatenación, para cada partición de la entrada en 2 partes, - posiblemente vacías, se decide + Respecto a la concatenación +\begin_inset Formula $L_{1}L_{2}$ +\end_inset + +, para cada partición de la entrada en 2 partes, posiblemente vacías, se + decide \begin_inset Formula $L_{1}$ \end_inset @@ -1372,8 +1374,12 @@ Demostración: \end_inset en la segunda. - Para ver que -\begin_inset Formula $L_{1}^{*}\in{\cal P}$ + Para ver que, si +\begin_inset Formula $L\in{\cal P}$ +\end_inset + +, +\begin_inset Formula $L^{*}\in{\cal P}$ \end_inset , hacemos lo siguiente: Para una entrada @@ -1398,7 +1404,7 @@ Demostración: \end_inset indica si -\begin_inset Formula $w_{i}\cdots w_{j}\in L_{1}^{*}$ +\begin_inset Formula $w_{i}\cdots w_{j}\in L^{*}$ \end_inset . @@ -1423,7 +1429,7 @@ Demostración: \end_inset , si -\begin_inset Formula $w_{i}\cdots w_{j}\in L_{1}$ +\begin_inset Formula $w_{i}\cdots w_{j}\in L$ \end_inset , se marca @@ -1473,7 +1479,7 @@ Demostración: \end_inset ejecuciones de la máquina que decide -\begin_inset Formula $L_{1}$ +\begin_inset Formula $L$ \end_inset . @@ -1562,7 +1568,7 @@ verificador \end_inset tal que -\begin_inset Formula $L=\{w\mid \exists c\mid V\text{ acepta }\langle w,c\rangle\}$ +\begin_inset Formula $L=\{w\mid\exists c:V\text{ acepta }\langle w,c\rangle\}$ \end_inset . @@ -1599,7 +1605,7 @@ status open \end_inset Sea -\begin_inset Formula $M$ +\begin_inset Formula ${\cal M}$ \end_inset una @@ -1615,26 +1621,22 @@ Sea \end_inset , simula -\begin_inset Formula $M$ +\begin_inset Formula ${\cal M}$ \end_inset tratando \begin_inset Formula $c$ \end_inset - como una secuencia con la opción que hace -\begin_inset Formula $M$ + como una secuencia con la opción que toma +\begin_inset Formula ${\cal M}$ \end_inset - en cada paso para aceptar -\begin_inset Formula $w$ -\end_inset - -, y que acepta o rechaza según lo haga -\begin_inset Formula $M$ + en cada paso, y que acepta o rechaza según lo haga +\begin_inset Formula ${\cal M}$ \end_inset - con esta configuración. + con estas elecciones. \end_layout \begin_layout Itemize @@ -1723,20 +1725,11 @@ end{samepage} \end_layout \begin_layout Standard -Sean -\begin_inset Formula $L_{1},L_{2}\in{\cal NP}$ -\end_inset - -, -\begin_inset Formula $L_{1}\cup L_{2},L_{1}\cap L_{2},L_{1}L_{2},L_{1}^{*}\in{\cal NP}$ -\end_inset - -. - Se desconoce si \begin_inset Formula ${\cal NP}$ \end_inset - es cerrada para el complemento o no. + es cerrada para la unión, intersección, concatenación y clausura. + Se desconoce si es cerrada para el complemento o no. \begin_inset Formula ${\cal P}$ \end_inset @@ -223,7 +223,11 @@ status open \end_inset -Obvio. +Por la existencia de lenguajes +\begin_inset Formula ${\cal NP}$ +\end_inset + +-completos, que vamos a ver. \end_layout \begin_layout Itemize @@ -299,7 +303,7 @@ variable \series bold proposición atómica \series default - dada por una secuencia de letras, una + (dada por una secuencia de letras), una \series bold conjunción \series default @@ -404,11 +408,11 @@ Una proposición es \series bold satisfacible \series default - si existe una asignación de valores que le asigna el valor de verdad verdadero. + si existe una asignación de valores que le asigna verdadero. Definimos \begin_inset Formula \[ -\text{SAT}\coloneqq\text{SAT}_{0}\coloneqq\text{SAT}_{\text{LP}}\coloneqq\{\langle\Phi\rangle\mid \Phi\text{ es una fórmula booleana satisfacible}\}. +\text{SAT}\coloneqq\text{SAT}_{0}\coloneqq\text{SAT}_{\text{LP}}\coloneqq\{\langle\Phi\rangle\mid\Phi\text{ es una fórmula booleana satisfacible}\}. \] \end_inset @@ -417,7 +421,7 @@ satisfacible \end_layout \begin_layout Standard -Sea +Sean \begin_inset Formula $N=(Q,\Sigma,\Gamma,\delta,q_{0},q_{\text{f}})$ \end_inset @@ -425,7 +429,7 @@ Sea \begin_inset Formula $\text{MNTD}$ \end_inset - en tiempo polinómico, sean + en tiempo polinómico y \begin_inset Formula $m,c,k\in\mathbb{N}^{*}$ \end_inset @@ -496,7 +500,7 @@ ventana \end_inset , donde -\begin_inset Formula $a_{p0}\coloneqq a_{p,t(n)+1}\coloneqq\#\notin Q\sqcup\Gamma$ +\begin_inset Formula $a_{p0}\coloneqq a_{p,t(n)+2}\coloneqq\#\notin Q\sqcup\Gamma$ \end_inset . @@ -586,7 +590,7 @@ Demostración: \begin_inset Formula $q_{\text{f}}$ \end_inset - se puede seguir hasta completar las + se pueda seguir hasta completar las \begin_inset Formula $t(n)$ \end_inset @@ -676,8 +680,7 @@ s\neq t Finalmente queremos ver que, si una fila es una configuración válida, la siguiente también lo es y se sigue de ella. Si esto es así, todas las ventanas entre las dos filas serán legales. - Ahora bien, las ventanas legales son las que tienen las siguientes formas, - donde + Ahora bien, las ventanas legales son las siguientes, donde \begin_inset Formula $a,b,c,d\in\Gamma$ \end_inset @@ -734,9 +737,9 @@ Con esto es claro que, si todas las ventanas entre dos filas son legales, \begin_inset Quotes crd \end_inset - a los lados se conservan y, si una fila tiene un único estado, la siguiente - tendrá uno único que estará a la izquierda o a la derecha, la transición - estará en + a los lados se conservan y, si una fila tiene una única celda de estado, + la siguiente tendrá una única que estará a la izquierda o a la derecha, + la transición estará en \begin_inset Formula $\delta$ \end_inset @@ -803,15 +806,7 @@ Si \begin_inset Formula $t(n)=O(n^{k})$ \end_inset -, esta fórmula tiene -\begin_inset Formula $O(n^{2k})$ -\end_inset - - variables ( -\begin_inset Formula $C$ -\end_inset - - por celda), +, \begin_inset Formula $\Phi_{\text{start}}$ \end_inset @@ -844,12 +839,11 @@ Si \end_inset tiene -\begin_inset Formula $O(2^{nk})$ +\begin_inset Formula $O(n^{2k})$ \end_inset (hasta 6 por ventana legal y ventana, el número de ventanas legales es - fijo y hay menos ventanas que celdas). - Por tanto + fijo y hay menos ventanas que celdas), por lo que \begin_inset Formula $\Phi$ \end_inset @@ -857,7 +851,7 @@ Si \begin_inset Formula $O(n^{2k})$ \end_inset -, y para + y, para \begin_inset Formula $N$ \end_inset @@ -889,7 +883,7 @@ La cual hay que saberse pese a que es incorrecta porque hacen preguntas \begin_inset Formula $n$ \end_inset - esto es imposible; añade una columa llena de + esto es imposible; añade una columna llena de \begin_inset Formula $\#$ \end_inset @@ -916,11 +910,7 @@ La cual hay que saberse pese a que es incorrecta porque hacen preguntas \begin_layout Standard Este teorema lo descubrieron Stephen Cook y Leonid Levin en los 70, siendo - -\begin_inset Formula $\text{SAT}$ -\end_inset - - el primer lenguaje que se descubrió + la primera vez que se descubre que un lenguaje es \begin_inset Formula ${\cal NP}$ \end_inset @@ -975,7 +965,7 @@ Llamando \end_inset -completos. - Sin embargo + Sin embargo, \begin_inset Formula $\text{SAT}_{\text{2-CNF}}$ \end_inset @@ -1022,6 +1012,13 @@ Entscheidungsproblem en 1936. \end_layout +\begin_layout Standard +\begin_inset Newpage newpage +\end_inset + + +\end_layout + \begin_layout Section Otros lenguajes \begin_inset Formula ${\cal NP}$ @@ -1271,10 +1268,10 @@ Veamos que \begin_inset Formula \begin{align*} V\coloneqq & \{a_{i}\}_{i=0}^{m}\cup\{b_{ij}\}_{i\in\{1,\dots,m\}}^{j\in\{1,\dots,3n+3\}}\cup\{c_{j}\}_{j=1}^{n},\\ -E\coloneqq & \{(a_{i-1},b_{i1}),(a_{i-1},b_{i,3n+3}),(b_{i1},a_{i}),(b_{i1},a_{i,3n+3})\}_{i=1}^{m}\cup\\ +E\coloneqq & \{(a_{i-1},b_{i1}),(a_{i-1},b_{i,3n+3}),(b_{i1},a_{i}),(b_{i,3n+3},a_{i})\}_{i=1}^{m}\cup\\ & \cup\{(b_{ij},b_{i,j+1}),(b_{i,j+1},b_{ij})\}_{i\in\{1,\dots,m\}}^{j\in\{1,\dots,3n+2\}}\cup\\ & \cup\{(b_{i,3j},c_{j}),(c_{j},b_{i,3j+1})\}_{i\in\{1,\dots m\},j\in\{1,\dots,n\}}^{p_{i}\text{ aparece en }k_{j}}\cup\\ - & \cup\{(b_{i,3j+1},c_{j}),(c_{j},b_{i,3j})\}_{i\in\{1,\dots,m\},j\in\{1,\dots,n\}}^{\neg p_{1}\text{ aparece en }k_{j}}. + & \cup\{(b_{i,3j+1},c_{j}),(c_{j},b_{i,3j})\}_{i\in\{1,\dots,m\},j\in\{1,\dots,n\}}^{\neg p_{i}\text{ aparece en }k_{j}}. \end{align*} \end_inset @@ -1323,7 +1320,7 @@ Tomamos una asignación de valores que haga verdadera a \begin_inset Formula $k_{j}$ \end_inset - que tenga valor verdadero. + que valga verdadero. Para construir el camino, primero, para \begin_inset Formula $i$ \end_inset @@ -1415,11 +1412,6 @@ Para \end_inset , y en el segundo le asignamos falso. - Veamos que esta asignación hace verdadera a -\begin_inset Formula $\Phi$ -\end_inset - -. Para \begin_inset Formula $j\in\{1,\dots,n\}$ \end_inset @@ -1432,7 +1424,7 @@ Para \begin_inset Formula $b_{i,3j}$ \end_inset -, la queremos ver que el siguiente es +, queremos ver que el siguiente es \begin_inset Formula $b_{i,3j+1}$ \end_inset @@ -1744,6 +1736,10 @@ El ciclo hamiltoniano debe contener el subcamino \begin_inset Formula $b$ \end_inset + en +\begin_inset Formula $G$ +\end_inset + que pasa por todos los nodos en \begin_inset Formula $V$ \end_inset @@ -1990,7 +1986,7 @@ Si \begin_inset Formula $(u_{k},1)$ \end_inset - y + y luego \begin_inset Formula $(u_{k},2)$ \end_inset @@ -2154,7 +2150,7 @@ Traveling Salesman Problem . Dado un grafo no dirigido -\begin_inset Formula $G=VE$ +\begin_inset Formula $G=(V,E)$ \end_inset , definimos un grafo no dirigido con pesos @@ -2503,7 +2499,7 @@ Para cada \end_inset verdadera. - Ahora bien, para cada cláusula + Para cada cláusula \begin_inset Formula $k_{j}$ \end_inset @@ -2658,7 +2654,7 @@ Para ver que es \end_inset distintas y cláusulas -\begin_inset Formula $(l_{11}\land l_{12}\land l_{13})\land\dots\land(l_{n1}\land l_{n2}\land l_{n3})$ +\begin_inset Formula $(l_{11}\lor l_{12}\lor l_{13})\land\dots\land(l_{n1}\lor l_{n2}\lor l_{n3})$ \end_inset , definimos un grafo no dirigido |