diff options
Diffstat (limited to 'mc/n4.lyx')
| -rw-r--r-- | mc/n4.lyx | 37 |
1 files changed, 17 insertions, 20 deletions
@@ -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 |