diff options
Diffstat (limited to 'mc')
| -rw-r--r-- | mc/n1.lyx | 4 | ||||
| -rw-r--r-- | mc/n2.lyx | 4 | ||||
| -rw-r--r-- | mc/n4.lyx | 20 | ||||
| -rw-r--r-- | mc/n5.lyx | 8 | ||||
| -rw-r--r-- | mc/n7.lyx | 12 | ||||
| -rw-r--r-- | mc/n8.lyx | 16 |
6 files changed, 32 insertions, 32 deletions
@@ -489,7 +489,7 @@ Sean \end_inset y -\begin_inset Formula $F'\coloneqq\{r\in Q':r\cap F\neq\emptyset\}$ +\begin_inset Formula $F'\coloneqq\{r\in Q'\mid r\cap F\neq\emptyset\}$ \end_inset . @@ -1807,7 +1807,7 @@ Sean \[ \delta'(q,r)\coloneqq\begin{cases} \epsilon, & (q,r)=(q_{0},q_{1})\lor(q\in F\land r=q_{\text{F}});\\ -a_{1}\mid\dots\mid a_{k}, & \{a\in\Sigma:r\in\delta(q,a)\}=\{a_{1},\dots,a_{k}\}\neq\emptyset;\\ +a_{1}\mid\dots\mid a_{k}, & \{a\in\Sigma\mid r\in\delta(q,a)\}=\{a_{1},\dots,a_{k}\}\neq\emptyset;\\ \emptyset, & \text{en otro caso}. \end{cases} \] @@ -602,7 +602,7 @@ variable inicial \end_inset , donde -\begin_inset Formula $\{w_{1},\dots,w_{n}\}=\{w:(T,w)\in V\}$ +\begin_inset Formula $\{w_{1},\dots,w_{n}\}=\{w\mid (T,w)\in V\}$ \end_inset . @@ -668,7 +668,7 @@ lenguaje generado \end_inset es -\begin_inset Formula $L(G)\coloneqq\{w\in\Sigma^{*}:S\Rightarrow^{*}w\}$ +\begin_inset Formula $L(G)\coloneqq\{w\in\Sigma^{*}\mid S\Rightarrow^{*}w\}$ \end_inset . @@ -439,7 +439,7 @@ input \end_inset que reconoce -\begin_inset Formula $K\coloneqq\{\langle{\cal A},w\rangle:\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:\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:\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:\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:\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:\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:\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 . @@ -2610,7 +2610,7 @@ Demostración: \end_inset , sea -\begin_inset Formula $B\coloneqq\{x\in A:x\notin f(x)\}$ +\begin_inset Formula $B\coloneqq\{x\in A\mid x\notin f(x)\}$ \end_inset , existe @@ -2767,7 +2767,7 @@ status open \begin_layout Standard \begin_inset Formula \[ -K\coloneqq\{\langle{\cal M},w\rangle:\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 +2806,7 @@ Demostración: \end_inset que decide -\begin_inset Formula $\{\langle{\cal M}\rangle:{\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 @@ -327,7 +327,7 @@ Problema de la parada. \begin_inset Formula \[ -\text{HALT}^{\text{MT}}\coloneqq\{\langle{\cal M},w\rangle:{\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 @@ -380,7 +380,7 @@ mapping \end_deeper \begin_layout Enumerate -\begin_inset Formula $\text{EMPTY}^{\text{MT}}\coloneqq\{\langle{\cal M}\rangle:{\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 +454,7 @@ mapping \end_deeper \begin_layout Enumerate -\begin_inset Formula $\text{Pass}\coloneqq\{\langle{\cal M},w,q\rangle:{\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 . @@ -674,7 +674,7 @@ Teorema de Rice: no trivial, \begin_inset Formula \[ -{\cal L}_{P}\coloneqq\{\langle{\cal M}\rangle:{\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 @@ -1113,7 +1113,7 @@ Están en \end_layout \begin_layout Enumerate -\begin_inset Formula $\text{RELPRIM}\coloneqq\{\langle x,y\rangle:x,y\in\mathbb{N}\text{ son primos relativos}\}$ +\begin_inset Formula $\text{RELPRIM}\coloneqq\{\langle x,y\rangle\mid x,y\in\mathbb{N}\text{ son primos relativos}\}$ \end_inset . @@ -1192,7 +1192,7 @@ noprefix "false" \end_deeper \begin_layout Enumerate -\begin_inset Formula $\text{PATH}\coloneqq\{\langle G,s,t\rangle:G\text{ es un grafo dirigido con un camino de }s\text{ a }t\}$ +\begin_inset Formula $\text{PATH}\coloneqq\{\langle G,s,t\rangle\mid G\text{ es un grafo dirigido con un camino de }s\text{ a }t\}$ \end_inset . @@ -1251,7 +1251,7 @@ Se añade el nodo \end_deeper \begin_layout Enumerate -\begin_inset Formula $\text{4-CLIQUE}\coloneqq\{\langle G\rangle:G\text{ es un grafo no dirigido con una 4-clique}\}$ +\begin_inset Formula $\text{4-CLIQUE}\coloneqq\{\langle G\rangle\mid G\text{ es un grafo no dirigido con una 4-clique}\}$ \end_inset . @@ -1287,7 +1287,7 @@ Si \end_deeper \begin_layout Enumerate -\begin_inset Formula $\text{EULCYCLE}\coloneqq\{\langle G\rangle:G\text{ es un grafo dirigido con un ciclo euleriano}\}$ +\begin_inset Formula $\text{EULCYCLE}\coloneqq\{\langle G\rangle\mid G\text{ es un grafo dirigido con un ciclo euleriano}\}$ \end_inset . @@ -1317,7 +1317,7 @@ Un teorema de Euler dice que un grafo dirigido \end_deeper \begin_layout Enumerate -\begin_inset Formula $\text{2-COLOR}\coloneqq\{\langle G\rangle:G\text{ es un grafo no dirigido bipartito}\}$ +\begin_inset Formula $\text{2-COLOR}\coloneqq\{\langle G\rangle\mid G\text{ es un grafo no dirigido bipartito}\}$ \end_inset . @@ -1562,7 +1562,7 @@ verificador \end_inset tal que -\begin_inset Formula $L=\{w:\exists c:V\text{ acepta }\langle w,c\rangle\}$ +\begin_inset Formula $L=\{w\mid \exists c\mid V\text{ acepta }\langle w,c\rangle\}$ \end_inset . @@ -408,7 +408,7 @@ satisfacible Definimos \begin_inset Formula \[ -\text{SAT}\coloneqq\text{SAT}_{0}\coloneqq\text{SAT}_{\text{LP}}\coloneqq\{\langle\Phi\rangle:\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 @@ -1039,7 +1039,7 @@ Son \end_layout \begin_layout Enumerate -\begin_inset Formula $\text{CLIQUE}\coloneqq\{\langle G,k\rangle:G\text{ es grafo no dirigido con }k\text{-clique}\}$ +\begin_inset Formula $\text{CLIQUE}\coloneqq\{\langle G,k\rangle\mid G\text{ es grafo no dirigido con }k\text{-clique}\}$ \end_inset . @@ -1209,7 +1209,7 @@ La función de conversión de \end_deeper \begin_layout Enumerate -\begin_inset Formula $\text{HAMPATH}\coloneqq\{\langle G,s,t\rangle:G\text{ es un grafo dirigido con camino hamiltoniano de }s\text{ a }t\}$ +\begin_inset Formula $\text{HAMPATH}\coloneqq\{\langle G,s,t\rangle\mid G\text{ es un grafo dirigido con camino hamiltoniano de }s\text{ a }t\}$ \end_inset . @@ -1607,7 +1607,7 @@ La función de conversión de \end_deeper \begin_layout Enumerate -\begin_inset Formula $\text{HAMCYCLE}\coloneqq\{\langle G\rangle:G\text{ es un grafo dirigido con un ciclo hamiltoniano}\}$ +\begin_inset Formula $\text{HAMCYCLE}\coloneqq\{\langle G\rangle\mid G\text{ es un grafo dirigido con un ciclo hamiltoniano}\}$ \end_inset . @@ -1765,7 +1765,7 @@ La función de conversión de \end_deeper \begin_layout Enumerate -\begin_inset Formula $\text{UHAMCYCLE}\coloneqq\{\langle G\rangle:G\text{ es un grafo no dirigido con un ciclo hamiltoniano}\}$ +\begin_inset Formula $\text{UHAMCYCLE}\coloneqq\{\langle G\rangle\mid G\text{ es un grafo no dirigido con un ciclo hamiltoniano}\}$ \end_inset . @@ -2011,7 +2011,7 @@ Claramente la función de conversión de \end_deeper \begin_layout Enumerate -\begin_inset Formula $\text{COLOR}\coloneqq\{\langle G,k\rangle:G\text{ es un grafo no dirigido }k\text{-coloreable}\}$ +\begin_inset Formula $\text{COLOR}\coloneqq\{\langle G,k\rangle\mid G\text{ es un grafo no dirigido }k\text{-coloreable}\}$ \end_inset . @@ -2277,7 +2277,7 @@ Un ciclo hamiltoniano en \end_deeper \begin_layout Enumerate -\begin_inset Formula $\text{SUBSET-SUM}\coloneqq\{\langle S,t\rangle:S\text{ es una lista de naturales con una subsecuencia que suma }t\}.$ +\begin_inset Formula $\text{SUBSET-SUM}\coloneqq\{\langle S,t\rangle\mid S\text{ es una lista de naturales con una subsecuencia que suma }t\}.$ \end_inset @@ -2605,7 +2605,7 @@ ión, pero calcular las potencias de 10 corresponde a multiplicar por 10 \end_deeper \begin_layout Enumerate -\begin_inset Formula $\text{VERTEX-COVER}\coloneqq\{\langle G,k\rangle:G\text{ es un grafo no dirigido con una }k\text{-cobertura}\}$ +\begin_inset Formula $\text{VERTEX-COVER}\coloneqq\{\langle G,k\rangle\mid G\text{ es un grafo no dirigido con una }k\text{-cobertura}\}$ \end_inset . |