From 09ea9d78d9fd959a1a314b3c03b3e583949a529b Mon Sep 17 00:00:00 2001
From: Juan Marin Noguera <juan@mnpi.eu>
Date: Tue, 6 Sep 2022 17:39:50 +0200
Subject: MC tema 1

---
 mc/n.lyx    |  177 +++++
 mc/n1.1.dot |    6 +
 mc/n1.2.dot |    6 +
 mc/n1.3.dot |    8 +
 mc/n1.lyx   | 2365 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 5 files changed, 2562 insertions(+)
 create mode 100644 mc/n.lyx
 create mode 100644 mc/n1.1.dot
 create mode 100644 mc/n1.2.dot
 create mode 100644 mc/n1.3.dot
 create mode 100644 mc/n1.lyx

(limited to 'mc')

diff --git a/mc/n.lyx b/mc/n.lyx
new file mode 100644
index 0000000..037d5b4
--- /dev/null
+++ b/mc/n.lyx
@@ -0,0 +1,177 @@
+#LyX 2.3 created this file. For more info see http://www.lyx.org/
+\lyxformat 544
+\begin_document
+\begin_header
+\save_transient_properties true
+\origin unavailable
+\textclass book
+\begin_preamble
+\input{../defs}
+\end_preamble
+\use_default_options true
+\begin_modules
+algorithm2e
+\end_modules
+\maintain_unincluded_children false
+\language spanish
+\language_package default
+\inputencoding auto
+\fontencoding global
+\font_roman "default" "default"
+\font_sans "default" "default"
+\font_typewriter "default" "default"
+\font_math "auto" "auto"
+\font_default_family default
+\use_non_tex_fonts false
+\font_sc false
+\font_osf false
+\font_sf_scale 100 100
+\font_tt_scale 100 100
+\use_microtype false
+\use_dash_ligatures true
+\graphics default
+\default_output_format default
+\output_sync 0
+\bibtex_command default
+\index_command default
+\paperfontsize 10
+\spacing single
+\use_hyperref false
+\papersize a5paper
+\use_geometry true
+\use_package amsmath 1
+\use_package amssymb 1
+\use_package cancel 1
+\use_package esint 1
+\use_package mathdots 1
+\use_package mathtools 1
+\use_package mhchem 1
+\use_package stackrel 1
+\use_package stmaryrd 1
+\use_package undertilde 1
+\cite_engine basic
+\cite_engine_type default
+\biblio_style plain
+\use_bibtopic false
+\use_indices false
+\paperorientation portrait
+\suppress_date false
+\justification true
+\use_refstyle 1
+\use_minted 0
+\index Index
+\shortcut idx
+\color #008000
+\end_index
+\leftmargin 0.2cm
+\topmargin 0.7cm
+\rightmargin 0.2cm
+\bottommargin 0.7cm
+\secnumdepth 3
+\tocdepth 3
+\paragraph_separation indent
+\paragraph_indentation default
+\is_math_indent 0
+\math_numbering_side default
+\quotes_style swiss
+\dynamic_quotes 0
+\papercolumns 1
+\papersides 1
+\paperpagestyle empty
+\listings_params "basicstyle={\ttfamily}"
+\tracking_changes false
+\output_changes false
+\html_math_output 0
+\html_css_as_file 0
+\html_be_strict false
+\end_header
+
+\begin_body
+
+\begin_layout Title
+Modelos de computación
+\end_layout
+
+\begin_layout Date
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+def
+\backslash
+cryear{2022}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset CommandInset include
+LatexCommand input
+filename "../license.lyx"
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Bibliografía:
+\end_layout
+
+\begin_layout Itemize
+Apuntes de clase.
+\end_layout
+
+\begin_layout Itemize
+
+\lang english
+Michael Sipser
+\lang spanish
+.
+ 
+\emph on
+\lang english
+Introduction to the Theory of Computation, 3rd.
+ ed.
+
+\emph default
+ Cengage Learning
+\lang spanish
+ (2013).
+\end_layout
+
+\begin_layout Chapter
+Lenguajes regulares
+\end_layout
+
+\begin_layout Standard
+\begin_inset CommandInset include
+LatexCommand input
+filename "n1.lyx"
+
+\end_inset
+
+
+\end_layout
+
+\end_body
+\end_document
diff --git a/mc/n1.1.dot b/mc/n1.1.dot
new file mode 100644
index 0000000..a3305e6
--- /dev/null
+++ b/mc/n1.1.dot
@@ -0,0 +1,6 @@
+digraph G {
+	rankdir=LR
+	q[shape=circle,label=""]
+	begin[shape=point]
+	begin -> q
+}
diff --git a/mc/n1.2.dot b/mc/n1.2.dot
new file mode 100644
index 0000000..fedced9
--- /dev/null
+++ b/mc/n1.2.dot
@@ -0,0 +1,6 @@
+digraph G {
+	rankdir=LR
+	q[shape=doublecircle,label=""]
+	begin[shape=point]
+	begin -> q
+}
diff --git a/mc/n1.3.dot b/mc/n1.3.dot
new file mode 100644
index 0000000..2c868d5
--- /dev/null
+++ b/mc/n1.3.dot
@@ -0,0 +1,8 @@
+digraph G {
+	rankdir=LR
+	q[shape=circle,label=""]
+	r[shape=doublecircle, label=""]
+	begin[shape=point]
+	begin -> q
+	q -> r[label=a]
+}
diff --git a/mc/n1.lyx b/mc/n1.lyx
new file mode 100644
index 0000000..62d5293
--- /dev/null
+++ b/mc/n1.lyx
@@ -0,0 +1,2365 @@
+#LyX 2.3 created this file. For more info see http://www.lyx.org/
+\lyxformat 544
+\begin_document
+\begin_header
+\save_transient_properties true
+\origin unavailable
+\textclass book
+\begin_preamble
+\input{../defs}
+\end_preamble
+\use_default_options true
+\maintain_unincluded_children false
+\language spanish
+\language_package default
+\inputencoding auto
+\fontencoding global
+\font_roman "default" "default"
+\font_sans "default" "default"
+\font_typewriter "default" "default"
+\font_math "auto" "auto"
+\font_default_family default
+\use_non_tex_fonts false
+\font_sc false
+\font_osf false
+\font_sf_scale 100 100
+\font_tt_scale 100 100
+\use_microtype false
+\use_dash_ligatures true
+\graphics default
+\default_output_format default
+\output_sync 0
+\bibtex_command default
+\index_command default
+\paperfontsize default
+\spacing single
+\use_hyperref false
+\papersize default
+\use_geometry false
+\use_package amsmath 1
+\use_package amssymb 1
+\use_package cancel 1
+\use_package esint 1
+\use_package mathdots 1
+\use_package mathtools 1
+\use_package mhchem 1
+\use_package stackrel 1
+\use_package stmaryrd 1
+\use_package undertilde 1
+\cite_engine basic
+\cite_engine_type default
+\biblio_style plain
+\use_bibtopic false
+\use_indices false
+\paperorientation portrait
+\suppress_date false
+\justification true
+\use_refstyle 1
+\use_minted 0
+\index Index
+\shortcut idx
+\color #008000
+\end_index
+\secnumdepth 3
+\tocdepth 3
+\paragraph_separation indent
+\paragraph_indentation default
+\is_math_indent 0
+\math_numbering_side default
+\quotes_style french
+\dynamic_quotes 0
+\papercolumns 1
+\papersides 1
+\paperpagestyle default
+\tracking_changes false
+\output_changes false
+\html_math_output 0
+\html_css_as_file 0
+\html_be_strict false
+\end_header
+
+\begin_body
+
+\begin_layout Standard
+Un 
+\series bold
+alfabeto
+\series default
+ 
+\begin_inset Formula $\Sigma$
+\end_inset
+
+ es un conjunto finito de 
+\series bold
+símbolos
+\series default
+.
+ Una 
+\series bold
+cadena
+\series default
+ en 
+\begin_inset Formula $\Sigma$
+\end_inset
+
+ es un elemento de 
+\begin_inset Formula ${\cal U}_{\Sigma}\coloneqq\Sigma^{*}:=\bigcup_{n\in\mathbb{N}}\Sigma^{n}$
+\end_inset
+
+, que solemos escribir como 
+\begin_inset Formula $u_{1}\cdots u_{n}\coloneqq(u_{1},\dots,u_{n})$
+\end_inset
+
+.
+ Dadas dos cadenas 
+\begin_inset Formula $u,v\in\Sigma^{*}$
+\end_inset
+
+, llamamos 
+\series bold
+concatenación
+\series default
+ de 
+\begin_inset Formula $u$
+\end_inset
+
+ y 
+\begin_inset Formula $v$
+\end_inset
+
+ a 
+\begin_inset Formula $u\cdot v\coloneqq u_{1}\cdots u_{|u|}v_{1}\cdots v_{|v|}$
+\end_inset
+
+.
+ 
+\begin_inset Formula $\Sigma^{*}$
+\end_inset
+
+ es un monoide con la concatenación de cadenas.
+\end_layout
+
+\begin_layout Standard
+Un 
+\series bold
+lenguaje
+\series default
+ sobre 
+\begin_inset Formula $\Sigma$
+\end_inset
+
+ es un 
+\begin_inset Formula $L\subseteq\Sigma^{*}$
+\end_inset
+
+.
+ La 
+\series bold
+concatenación
+\series default
+ de dos lenguajes 
+\begin_inset Formula $L_{1},L_{2}\subseteq\Sigma^{*}$
+\end_inset
+
+ es 
+\begin_inset Formula $L_{1}\cdot L_{2}\coloneqq\{uv\}_{u\in L_{1},v\in L_{2}}$
+\end_inset
+
+.
+ 
+\begin_inset Formula ${\cal P}(\Sigma^{*})$
+\end_inset
+
+ es un monoide con la concatenación de lenguajes.
+ La 
+\series bold
+clausura
+\series default
+ o 
+\series bold
+\emph on
+\lang english
+Kleene star
+\series default
+\emph default
+\lang spanish
+ de un lenguaje 
+\begin_inset Formula $L$
+\end_inset
+
+ es 
+\begin_inset Formula $L^{*}\coloneqq\bigcup_{n\in\mathbb{N}}L^{n}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Un 
+\series bold
+autómata finito determinista
+\series default
+ (
+\series bold
+DFA
+\series default
+, 
+\emph on
+\lang english
+Deterministic Finite Automaton
+\emph default
+\lang spanish
+) es una tupla 
+\begin_inset Formula $(Q,\Sigma,\delta,q_{0},F)$
+\end_inset
+
+ formada por un conjunto finito de 
+\series bold
+estados
+\series default
+ 
+\begin_inset Formula $Q$
+\end_inset
+
+, un alfabeto 
+\begin_inset Formula $\Sigma$
+\end_inset
+
+, una 
+\series bold
+función de transición
+\series default
+ 
+\begin_inset Formula $\delta:Q\times\Sigma\to Q$
+\end_inset
+
+, un 
+\series bold
+estado inicial
+\series default
+ 
+\begin_inset Formula $q_{0}\in Q$
+\end_inset
+
+ y un conjunto de 
+\series bold
+estados finales
+\series default
+ o 
+\series bold
+de aceptación
+\series default
+ 
+\begin_inset Formula $F\subseteq Q$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Un 
+\series bold
+autómata finito no determinista
+\series default
+ (
+\series bold
+NFA
+\series default
+, 
+\emph on
+\lang english
+Nondeterministic Finite Automaton
+\emph default
+\lang spanish
+) es una tupla 
+\begin_inset Formula $(Q,\Sigma,\delta,q_{0},F)$
+\end_inset
+
+ formada por un conjunto finito de 
+\series bold
+estados
+\series default
+ 
+\begin_inset Formula $Q$
+\end_inset
+
+, un alfabeto 
+\begin_inset Formula $\Sigma$
+\end_inset
+
+, una 
+\series bold
+función de transición
+\series default
+ 
+\begin_inset Formula $\delta:Q\times(\Sigma_{\epsilon}\coloneqq\Sigma^{1}\cup\{\epsilon\})\to{\cal P}(Q)$
+\end_inset
+
+, un 
+\series bold
+estado inicial
+\series default
+ 
+\begin_inset Formula $q_{0}\in Q$
+\end_inset
+
+ y un conjunto de 
+\series bold
+estados finales
+\series default
+ o 
+\series bold
+de aceptación
+\series default
+ 
+\begin_inset Formula $F\subseteq Q$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Un NFA 
+\begin_inset Formula $(Q,\Sigma,\delta,q_{0},F)$
+\end_inset
+
+ 
+\series bold
+acepta
+\series default
+ una cadena 
+\begin_inset Formula $w\in\Sigma^{*}$
+\end_inset
+
+ si existen 
+\begin_inset Formula $m\in\mathbb{N}$
+\end_inset
+
+, 
+\begin_inset Formula $(y_{1},\dots,y_{m})\in(\Sigma_{\epsilon})^{m}$
+\end_inset
+
+ y 
+\begin_inset Formula $(r_{0},\dots,r_{m})\in Q^{m+1}$
+\end_inset
+
+ tales que 
+\begin_inset Formula $r_{0}=q_{0}$
+\end_inset
+
+, 
+\begin_inset Formula $r_{m}\in F$
+\end_inset
+
+ y, para 
+\begin_inset Formula $i\in\{0,\dots,m-1\}$
+\end_inset
+
+, 
+\begin_inset Formula $r_{i+1}\in\delta(r_{i},y_{i+1})$
+\end_inset
+
+.
+ Un DFA 
+\begin_inset Formula $(Q,\Sigma,\delta,q_{0},F)$
+\end_inset
+
+ 
+\series bold
+acepta
+\series default
+ una cadena 
+\begin_inset Formula $w\in\Sigma^{*}$
+\end_inset
+
+ si el NFA 
+\begin_inset Formula $(Q,\Sigma,\delta',q_{0},F)$
+\end_inset
+
+ lo acepta, donde 
+\begin_inset Formula $\delta'$
+\end_inset
+
+ viene dado por 
+\begin_inset Formula $\delta'(q,a)\coloneqq\{\delta(q,a)\}$
+\end_inset
+
+ y 
+\begin_inset Formula $\delta'(q,\emptyset)\coloneqq\emptyset$
+\end_inset
+
+ para 
+\begin_inset Formula $q\in Q$
+\end_inset
+
+ y 
+\begin_inset Formula $a\in\Sigma$
+\end_inset
+
+.
+ El 
+\series bold
+lenguaje aceptado
+\series default
+ por un DFA o NFA 
+\begin_inset Formula ${\cal A}$
+\end_inset
+
+, 
+\begin_inset Formula $L({\cal A})$
+\end_inset
+
+, es el conjunto de cadenas aceptadas por 
+\begin_inset Formula ${\cal A}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Llamamos 
+\begin_inset Formula ${\cal L}_{\text{DFA}}$
+\end_inset
+
+ a la clase de lenguajes aceptados por algún DFA, y 
+\begin_inset Formula ${\cal L}_{\text{NFA}}$
+\end_inset
+
+ a la de lenguajes aceptados por algún NFA.
+ Como 
+\series bold
+teorema
+\series default
+, 
+\begin_inset Formula ${\cal L}_{\text{DFA}}={\cal L}_{\text{NFA}}$
+\end_inset
+
+.
+\begin_inset Note Comment
+status open
+
+\begin_layout Itemize
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\subseteq]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Trivial.
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\supseteq]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Sean 
+\begin_inset Formula ${\cal A}\coloneqq(Q,\Sigma,\delta,q_{0},F)$
+\end_inset
+
+ un NFA, 
+\begin_inset Formula $Q'\coloneqq{\cal P}(Q)$
+\end_inset
+
+ y 
+\begin_inset Formula $F'\coloneqq\{r\in Q':r\cap F\neq\emptyset\}$
+\end_inset
+
+.
+ Para 
+\begin_inset Formula $r\in Q'$
+\end_inset
+
+, decimos que 
+\begin_inset Formula $q\in Q$
+\end_inset
+
+ es alcanzable desde 
+\begin_inset Formula $r$
+\end_inset
+
+ si existen 
+\begin_inset Formula $m\in\mathbb{N}$
+\end_inset
+
+ y una secuencia 
+\begin_inset Formula $(q_{0},\dots,q_{m})$
+\end_inset
+
+ de elementos de 
+\begin_inset Formula $Q$
+\end_inset
+
+ tal que 
+\begin_inset Formula $q_{0}\in r$
+\end_inset
+
+, 
+\begin_inset Formula $q_{m}=q$
+\end_inset
+
+ y, para 
+\begin_inset Formula $i\in\{0,\dots,m-1\}$
+\end_inset
+
+, 
+\begin_inset Formula $q_{i+1}\in\delta(q_{i},\varepsilon)$
+\end_inset
+
+.
+ Llamamos entonces 
+\begin_inset Formula $E(r)$
+\end_inset
+
+ al conjunto de elementos de 
+\begin_inset Formula $Q$
+\end_inset
+
+ alcanzables desde 
+\begin_inset Formula $r$
+\end_inset
+
+, con lo que 
+\begin_inset Formula $r\subseteq E(r)$
+\end_inset
+
+, y definimos 
+\begin_inset Formula $\delta':Q'\times\Sigma\to Q'$
+\end_inset
+
+ como
+\begin_inset Formula 
+\[
+\delta'(r,a)\coloneqq\bigcup_{q\in r}E(\delta(q,a)).
+\]
+
+\end_inset
+
+Dado el DFA 
+\begin_inset Formula ${\cal A}'\coloneqq(Q',\Sigma,\delta',E(q_{0}),)$
+\end_inset
+
+, queremos ver 
+\begin_inset Formula $L({\cal A}')=L({\cal A})$
+\end_inset
+
+.
+ Llamamos 
+\begin_inset Formula ${\cal A}_{q}$
+\end_inset
+
+ a un NFA como 
+\begin_inset Formula ${\cal A}$
+\end_inset
+
+ pero con estado inicial 
+\begin_inset Formula $q$
+\end_inset
+
+, y 
+\begin_inset Formula ${\cal A}'_{r}$
+\end_inset
+
+ a un DFA como 
+\begin_inset Formula ${\cal A}'$
+\end_inset
+
+ pero con estado inicial 
+\begin_inset Formula $r$
+\end_inset
+
+.
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\subseteq]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Sea 
+\begin_inset Formula $w=w_{1}\cdots w_{n}\in L({\cal A}')$
+\end_inset
+
+, existen 
+\begin_inset Formula $r_{0},\dots,r_{n}\in Q'$
+\end_inset
+
+ con 
+\begin_inset Formula $\delta'(r_{i},w_{i})=r_{i+1}$
+\end_inset
+
+ para cada 
+\begin_inset Formula $i$
+\end_inset
+
+, 
+\begin_inset Formula $r_{0}=E(q_{0})$
+\end_inset
+
+ y 
+\begin_inset Formula $r_{n}\in F'$
+\end_inset
+
+, y queremos probar que para cada 
+\begin_inset Formula $i$
+\end_inset
+
+ existe un 
+\begin_inset Formula $q_{i}\in r_{i}$
+\end_inset
+
+ tal que 
+\begin_inset Formula $w_{i+1}\cdots w_{n}\in L({\cal A}_{q_{i}})$
+\end_inset
+
+.
+\end_layout
+
+\begin_deeper
+\begin_layout Plain Layout
+Para 
+\begin_inset Formula $i=n$
+\end_inset
+
+, tomamos 
+\begin_inset Formula $q_{n}\in r_{n}\cap F$
+\end_inset
+
+ y 
+\begin_inset Formula $\lambda\in L({\cal A}_{q_{n}})$
+\end_inset
+
+.
+ Probado esto para un 
+\begin_inset Formula $i\geq1$
+\end_inset
+
+, para 
+\begin_inset Formula $i-1$
+\end_inset
+
+, 
+\begin_inset Formula $q_{i}\in\delta'(r_{i-1},w_{i})$
+\end_inset
+
+ y por tanto existe un 
+\begin_inset Formula $q_{i-1}\in r_{i-1}$
+\end_inset
+
+ tal que 
+\begin_inset Formula $q_{i}\in E(\delta(q_{i-1},w_{i}))$
+\end_inset
+
+.
+ Así, existen 
+\begin_inset Formula $s_{0},\dots,s_{l}\in Q$
+\end_inset
+
+ con 
+\begin_inset Formula $s_{0}\in\delta(q_{i-1},w_{i})$
+\end_inset
+
+, 
+\begin_inset Formula $s_{l}=q_{i}$
+\end_inset
+
+ y cada 
+\begin_inset Formula $s_{j+1}\in\delta(s_{j},\epsilon)$
+\end_inset
+
+, pero por hipótesis de inducción, existen 
+\begin_inset Formula $a_{1},\dots,a_{k}\in\Sigma_{\epsilon}$
+\end_inset
+
+ y 
+\begin_inset Formula $p_{0},\dots,p_{k}\in Q$
+\end_inset
+
+ con 
+\begin_inset Formula $a_{1}\cdots a_{k}=w_{i+1}\cdots w_{n}$
+\end_inset
+
+, 
+\begin_inset Formula $p_{0}=q_{i}$
+\end_inset
+
+, 
+\begin_inset Formula $p_{k}\in F$
+\end_inset
+
+ y cada 
+\begin_inset Formula $p_{k+1}\in\delta(p_{k},a_{k+1})$
+\end_inset
+
+, de modo que las secuencias 
+\begin_inset Formula $q_{i-1},s_{0},\dots,s_{l}=p_{0},\dots,p_{k}$
+\end_inset
+
+ y 
+\begin_inset Formula $w_{i},\overbrace{\epsilon,\dots,\epsilon}^{l},a_{1},\dots,a_{k}$
+\end_inset
+
+ prueban que 
+\begin_inset Formula $w_{i}\cdots w_{n}\in L({\cal A}_{q_{i-1}})$
+\end_inset
+
+.
+ Entonces 
+\begin_inset Formula $w\in L({\cal A}_{q_{0}})$
+\end_inset
+
+ y, añadiendo transiciones 
+\begin_inset Formula $\epsilon$
+\end_inset
+
+ como antes del estado inicial al 
+\begin_inset Formula $q_{0}$
+\end_inset
+
+ obtenido, vemos que 
+\begin_inset Formula $w\in L({\cal A})$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Itemize
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\supseteq]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Sea 
+\begin_inset Formula $w=w_{1}\cdots w_{n}\in L({\cal A})$
+\end_inset
+
+, existen 
+\begin_inset Formula $y_{1},\dots,y_{m}\in\Sigma_{\epsilon}$
+\end_inset
+
+ y 
+\begin_inset Formula $q_{0},\dots,q_{m}\in Q$
+\end_inset
+
+ con 
+\begin_inset Formula $y_{1}\cdots y_{m}=w$
+\end_inset
+
+, 
+\begin_inset Formula $q_{m}\in F$
+\end_inset
+
+ y cada 
+\begin_inset Formula $q_{j+1}=\delta(q_{j},y_{j+1})$
+\end_inset
+
+.
+ Tomamos la subsecuencia 
+\begin_inset Formula $y_{p_{1}},\dots,y_{p_{n}}=w_{1},\dots,w_{n}$
+\end_inset
+
+ y queremos ver que, si 
+\begin_inset Formula $p_{n+1}\coloneqq m+1$
+\end_inset
+
+ y 
+\begin_inset Formula $(r_{0},\dots,r_{n})$
+\end_inset
+
+ es la secuencia de elementos de 
+\begin_inset Formula $Q'$
+\end_inset
+
+ con 
+\begin_inset Formula $r_{0}=q'_{0}$
+\end_inset
+
+ y cada 
+\begin_inset Formula $r_{i+1}=\delta(r_{i},w_{i+1})$
+\end_inset
+
+, entonces 
+\begin_inset Formula $q_{p_{i+1}-1}\in r_{i}$
+\end_inset
+
+ y en particular 
+\begin_inset Formula $q_{m}\in r_{n}$
+\end_inset
+
+ y 
+\begin_inset Formula $r_{n}\in F$
+\end_inset
+
+.
+ Para 
+\begin_inset Formula $i=0$
+\end_inset
+
+, 
+\begin_inset Formula $q_{0},\dots,q_{p_{1}-1}$
+\end_inset
+
+ cumple que cada 
+\begin_inset Formula $q_{j+1}\in\delta(q_{j},\epsilon)$
+\end_inset
+
+, luego 
+\begin_inset Formula $q_{p_{1}-1}\in E(q_{0})=q'_{0}=r_{0}$
+\end_inset
+
+.
+ Para 
+\begin_inset Formula $0<i\leq m$
+\end_inset
+
+, probado esto para 
+\begin_inset Formula $i-1$
+\end_inset
+
+ (
+\begin_inset Formula $q_{p_{i}-1}\in r_{i-1}$
+\end_inset
+
+), entonces 
+\begin_inset Formula $E(\delta(q_{p_{i}-1},w_{i}))\subseteq\delta'(r_{i-1},w_{i})=r_{i}$
+\end_inset
+
+, pero 
+\begin_inset Formula $q_{p_{i}}\in\delta(q_{p_{i-1}},y_{p_{i}}=w_{i})$
+\end_inset
+
+, luego 
+\begin_inset Formula $E(q_{p_{i}})\subseteq E(\delta(q_{p_{i-1}},w_{i})\subseteq r_{i}$
+\end_inset
+
+ y, como claramente 
+\begin_inset Formula $q_{p_{i+1}-1}\in E(q_{p_{i}})$
+\end_inset
+
+, 
+\begin_inset Formula $q_{p_{i+1}-1}\in r_{i}$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Para dibujar un NFA 
+\begin_inset Formula $(Q,\Sigma,\delta,q_{0},F)$
+\end_inset
+
+, dibujamos un círculo para cada 
+\begin_inset Formula $q\in Q$
+\end_inset
+
+ con su etiqueta dentro, o un círculo doble si 
+\begin_inset Formula $q\in F$
+\end_inset
+
+, una flecha que señala a 
+\begin_inset Formula $q_{0}$
+\end_inset
+
+ y, para cada 
+\begin_inset Formula $q\in Q$
+\end_inset
+
+, 
+\begin_inset Formula $a\in\Sigma_{\epsilon}$
+\end_inset
+
+ y 
+\begin_inset Formula $q'\in\delta(q,a)$
+\end_inset
+
+, una flecha del círculo 
+\begin_inset Formula $q$
+\end_inset
+
+ al 
+\begin_inset Formula $q'$
+\end_inset
+
+ etiquetada con 
+\begin_inset Formula $a$
+\end_inset
+
+.
+ Para dibujar un DFA, dibujamos su NFA equivalente.
+ Además, si en el DFA existe un 
+\begin_inset Formula $e\in Q\setminus F$
+\end_inset
+
+ (estado de error) tal que para todo 
+\begin_inset Formula $a\in\Sigma$
+\end_inset
+
+ es 
+\begin_inset Formula $\delta(e,a)=e$
+\end_inset
+
+, podemos no dibujar 
+\begin_inset Formula $e$
+\end_inset
+
+ ni las flechas que van a parar a 
+\begin_inset Formula $e$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Las 
+\series bold
+operaciones regulares
+\series default
+ son la unión, la concatenación y la clausura de lenguajes.
+ Una 
+\series bold
+expresión regular
+\series default
+ sobre el alfabeto 
+\begin_inset Formula $\Sigma$
+\end_inset
+
+ es una de la forma 
+\begin_inset Formula $\emptyset$
+\end_inset
+
+, 
+\begin_inset Formula $\epsilon$
+\end_inset
+
+, 
+\begin_inset Formula $a$
+\end_inset
+
+ para un 
+\begin_inset Formula $a\in\Sigma$
+\end_inset
+
+, 
+\begin_inset Formula $r_{1}\mid r_{2}$
+\end_inset
+
+, 
+\begin_inset Formula $r_{1}r_{2}$
+\end_inset
+
+ o 
+\begin_inset Formula $r_{1}^{*}$
+\end_inset
+
+, donde 
+\begin_inset Formula $r_{1}$
+\end_inset
+
+ y 
+\begin_inset Formula $r_{2}$
+\end_inset
+
+ son expresiones regulares y las operaciones, de mayor a menor prioridad,
+ son 
+\begin_inset Formula $r_{1}^{*}$
+\end_inset
+
+, 
+\begin_inset Formula $r_{1}r_{2}$
+\end_inset
+
+ y 
+\begin_inset Formula $r_{1}\mid r_{2}$
+\end_inset
+
+, y se usan paréntesis para desambiguar la prioridad.
+ Un 
+\series bold
+lenguaje regular
+\series default
+ es uno representado por una expresión regular, donde 
+\begin_inset Formula $\emptyset$
+\end_inset
+
+ y 
+\begin_inset Formula $\epsilon$
+\end_inset
+
+ se representan a sí mismos, 
+\begin_inset Formula $a$
+\end_inset
+
+ representa 
+\begin_inset Formula $\{a\}$
+\end_inset
+
+, 
+\begin_inset Formula $r_{1}\mid r_{2}$
+\end_inset
+
+ representa la unión de los lenguajes correspondientes, 
+\begin_inset Formula $r_{1}r_{2}$
+\end_inset
+
+ la concatenación y 
+\begin_inset Formula $r_{1}^{*}$
+\end_inset
+
+ la clausura.
+\end_layout
+
+\begin_layout Standard
+Llamamos 
+\begin_inset Formula ${\cal L}_{\text{ER}}$
+\end_inset
+
+ o 
+\begin_inset Formula ${\cal REG}$
+\end_inset
+
+ a la clase de lenguajes regulares, y se tiene 
+\begin_inset Formula ${\cal L}_{\text{ER}}={\cal L}_{\text{NFA}}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\subseteq]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\begin_inset Formula $\emptyset$
+\end_inset
+
+ es el lenguaje de
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+\align center
+\begin_inset External
+	template VectorGraphics
+	filename n1.1.dot
+	scale 40
+
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\epsilon$
+\end_inset
+
+ es el lenguaje de
+\end_layout
+
+\begin_layout Standard
+\align center
+\begin_inset External
+	template VectorGraphics
+	filename n1.2.dot
+	scale 40
+
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $a$
+\end_inset
+
+ es el lenguaje de
+\end_layout
+
+\begin_layout Standard
+\align center
+\begin_inset External
+	template VectorGraphics
+	filename n1.3.dot
+	scale 40
+
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Dados dos lenguajes regulares 
+\begin_inset Formula $L_{1}$
+\end_inset
+
+ y 
+\begin_inset Formula $L_{2}$
+\end_inset
+
+ con NFAs respectivos 
+\begin_inset Formula $(Q_{1},\Sigma,\delta_{1},q_{1},F_{1})$
+\end_inset
+
+ y 
+\begin_inset Formula $(Q_{2},\Sigma,\delta_{2},q_{2},F_{2})$
+\end_inset
+
+, sea 
+\begin_inset Formula $q_{0}\notin Q_{1}\cup Q_{2}$
+\end_inset
+
+, 
+\begin_inset Formula $L_{1}\cup L_{2}$
+\end_inset
+
+ es aceptado por 
+\begin_inset Formula $(Q_{1}\sqcup Q_{2}\sqcup\{q_{0}\},\Sigma,\delta,q_{0},F_{1}\cup F_{2})$
+\end_inset
+
+, donde
+\end_layout
+
+\begin_layout Standard
+\align center
+\begin_inset Tabular
+<lyxtabular version="3" rows="4" columns="3">
+<features tabularvalignment="middle">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<row>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $\delta$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" bottomline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $\Sigma$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" bottomline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $\epsilon$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $q_{0}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $\emptyset$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $\{q_{1},q_{2}\}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $Q_{1}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell multicolumn="1" alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $\delta_{1}(q,a)$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell multicolumn="2" alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $Q_{2}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell multicolumn="1" alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $\delta_{2}(q,a)$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell multicolumn="2" alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+</cell>
+</row>
+</lyxtabular>
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $L_{1}L_{2}$
+\end_inset
+
+ es aceptado por 
+\begin_inset Formula $(Q_{1}\sqcup Q_{2},\Sigma,\delta,q_{1},F_{2})$
+\end_inset
+
+, con 
+\begin_inset Formula $\delta$
+\end_inset
+
+ dada por
+\end_layout
+
+\begin_layout Standard
+\align center
+\begin_inset Tabular
+<lyxtabular version="3" rows="4" columns="3">
+<features tabularvalignment="middle">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<row>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $\delta$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" bottomline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $\Sigma$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" bottomline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $\epsilon$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $Q_{1}\setminus F_{1}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell multicolumn="1" alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $\delta_{1}(q,a)$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell multicolumn="2" alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $F_{1}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $\delta_{1}(q,a)\cup\{q_{2}\}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $Q_{2}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell multicolumn="1" alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $\delta_{2}(q,a)$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell multicolumn="2" alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+</cell>
+</row>
+</lyxtabular>
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $L_{1}^{*}$
+\end_inset
+
+ es aceptado por 
+\begin_inset Formula $(Q_{1}\sqcup\{q_{0}\},\Sigma,\delta,q_{0},\{q_{0}\})$
+\end_inset
+
+, con 
+\begin_inset Formula $\delta$
+\end_inset
+
+ dada por
+\end_layout
+
+\begin_layout Standard
+\align center
+\begin_inset Tabular
+<lyxtabular version="3" rows="4" columns="3">
+<features tabularvalignment="middle">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<column alignment="center" valignment="top">
+<row>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $\delta$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" bottomline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $\Sigma$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" bottomline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $\epsilon$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $q_{0}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $\emptyset$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $\{q_{1}\}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $Q_{1}\setminus F_{1}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell multicolumn="1" alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $\delta_{1}(q,a)$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell multicolumn="2" alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="center" valignment="top" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $F_{1}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+\begin_inset Formula $\delta_{1}(q,a)\cup\{q_{0}\}$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+</cell>
+</row>
+</lyxtabular>
+
+\end_inset
+
+
+\begin_inset Note Comment
+status open
+
+\begin_layout Itemize
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\supseteq]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Dado un NFA 
+\begin_inset Formula ${\cal A}\coloneqq(Q\coloneqq\{q_{1},\dots,q_{n-1}\},\Sigma,\delta,q_{1},F)$
+\end_inset
+
+, queremos construir una expresión regular que acepte el mismo lenguaje
+ que 
+\begin_inset Formula ${\cal A}$
+\end_inset
+
+.
+ Para ello consideramos tuplas de la forma 
+\begin_inset Formula $(Q,\Sigma,\delta,q_{0},q_{\text{F}})$
+\end_inset
+
+, donde 
+\begin_inset Formula $Q$
+\end_inset
+
+ es un conjunto finito, 
+\begin_inset Formula $\Sigma$
+\end_inset
+
+ es un alfabeto, 
+\begin_inset Formula $q_{0},q_{\text{F}}\in Q$
+\end_inset
+
+, 
+\begin_inset Formula $q_{0}\neq q_{\text{F}}$
+\end_inset
+
+ y 
+\begin_inset Formula $\delta:(Q\setminus\{q_{\text{F}}\})\times(Q\setminus\{q_{0}\})\to{\cal R}$
+\end_inset
+
+, siendo 
+\begin_inset Formula ${\cal R}$
+\end_inset
+
+ el conjunto de expresiones regulares sobre 
+\begin_inset Formula $\Sigma$
+\end_inset
+
+, y decimos que esta tupla acepta una cadena 
+\begin_inset Formula $w\in\Sigma^{*}$
+\end_inset
+
+ si existe una secuencia de cadenas 
+\begin_inset Formula $y_{1},\dots,y_{m}\in\Sigma^{*}$
+\end_inset
+
+ y una de estados 
+\begin_inset Formula $r_{0},\dots,r_{m}\in Q$
+\end_inset
+
+ con 
+\begin_inset Formula $w=y_{1}\cdots y_{m}$
+\end_inset
+
+, 
+\begin_inset Formula $r_{0}=q_{0}$
+\end_inset
+
+, 
+\begin_inset Formula $r_{m}=q_{\text{F}}$
+\end_inset
+
+ y, para cada 
+\begin_inset Formula $i$
+\end_inset
+
+, 
+\begin_inset Formula $\delta(r_{i},r_{i+1})$
+\end_inset
+
+ acepta 
+\begin_inset Formula $y_{i+1}$
+\end_inset
+
+.
+\end_layout
+
+\begin_deeper
+\begin_layout Plain Layout
+Sean 
+\begin_inset Formula $q_{0},q_{\text{F}}$
+\end_inset
+
+ distintos, empezamos con 
+\begin_inset Formula $(Q\sqcup\{q_{0},q_{\text{F}}\},\Sigma,\delta',q_{0},q_{\text{F}})$
+\end_inset
+
+, donde
+\begin_inset Formula 
+\[
+\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;\\
+\emptyset, & \text{en otro caso}.
+\end{cases}
+\]
+
+\end_inset
+
+Es fácil ver que esta tupla acepta las mismas cadenas que 
+\begin_inset Formula ${\cal A}$
+\end_inset
+
+, y vamos a ir transformándola, llegando en cada paso a una tupla que acepta
+ el mismo lenguaje pero con un estado menos, hasta llegar a una de 2 estados,
+ que será de la forma 
+\begin_inset Formula $(\{q_{0},q_{\text{F}}\},\Sigma,\delta_{\text{F}},q_{0},q_{\text{F}})$
+\end_inset
+
+ y aceptará las mismas cadenas que 
+\begin_inset Formula $\delta_{\text{F}}(q_{0},q_{\text{F}})\in{\cal R}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Plain Layout
+Sea la tupla 
+\begin_inset Formula ${\cal A}_{k}\coloneqq(Q_{k},\Sigma,\delta_{k},q_{0},q_{\text{F}})$
+\end_inset
+
+ con 
+\begin_inset Formula $|Q_{k}|>2$
+\end_inset
+
+ y sea 
+\begin_inset Formula $q_{\text{R}}\in Q_{k}\setminus\{q_{0},q_{\text{F}}\}$
+\end_inset
+
+, 
+\begin_inset Formula ${\cal A}_{k+1}\coloneqq(Q_{k+1},\Sigma,\delta_{k+1},q_{0},q_{\text{F}})$
+\end_inset
+
+ dada por 
+\begin_inset Formula $Q_{k+1}\coloneqq Q_{k}$
+\end_inset
+
+ y
+\begin_inset Formula 
+\[
+\delta_{k+1}(q,r)\coloneqq(\delta_{k}(q,q_{\text{R}}))(\delta_{k}(q_{\text{R}},q_{\text{R}}))^{*}(\delta_{k}(q_{\text{R}},r))\mid\delta_{k}(q,r)
+\]
+
+\end_inset
+
+acepta el mismo lenguaje que 
+\begin_inset Formula ${\cal A}_{k}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Plain Layout
+En efecto, si 
+\begin_inset Formula ${\cal A}_{k}$
+\end_inset
+
+ acepta 
+\begin_inset Formula $w$
+\end_inset
+
+, existen 
+\begin_inset Formula $y_{1},\dots,y_{m}\in\Sigma^{*}$
+\end_inset
+
+ y 
+\begin_inset Formula $r_{0},\dots,r_{m}\in Q_{k}$
+\end_inset
+
+ tal que 
+\begin_inset Formula $r_{0}=q_{0}$
+\end_inset
+
+, 
+\begin_inset Formula $r_{m}=q_{\text{F}}$
+\end_inset
+
+, 
+\begin_inset Formula $w=y_{1}\cdots y_{m}$
+\end_inset
+
+ y cada 
+\begin_inset Formula $\delta_{k}(r_{i},r_{i+1})$
+\end_inset
+
+ acepta 
+\begin_inset Formula $y_{i+1}$
+\end_inset
+
+.
+ Si 
+\begin_inset Formula $r_{0},\dots,r_{m}\neq q_{\text{F}}$
+\end_inset
+
+, esta secuencia sirve para 
+\begin_inset Formula ${\cal A}_{k+1}$
+\end_inset
+
+, pues cada 
+\begin_inset Formula $\delta_{k+1}(r_{i},r_{i+1})=\cdots\mid\delta_{k}(r_{i},r_{i+1})$
+\end_inset
+
+.
+ En otro caso, sean 
+\begin_inset Formula $0<p\leq q<m$
+\end_inset
+
+ tales que 
+\begin_inset Formula $r_{p},\dots,r_{q}=q_{\text{R}}$
+\end_inset
+
+ y 
+\begin_inset Formula $r_{p-1},r_{q+1}\neq q_{\text{R}}$
+\end_inset
+
+, sean 
+\begin_inset Formula $e_{1}\coloneqq\delta_{k}(r_{p-1},q_{\text{R}})$
+\end_inset
+
+, 
+\begin_inset Formula $e_{2}\coloneqq\delta_{k}(q_{\text{R}},q_{\text{R}})$
+\end_inset
+
+ y 
+\begin_inset Formula $e_{3}\coloneqq\delta_{k}(q_{\text{R}},r_{q+1})$
+\end_inset
+
+, 
+\begin_inset Formula $y_{p}\cdots y_{q+1}$
+\end_inset
+
+ es aceptada por 
+\begin_inset Formula $e_{1}e_{2}\cdots e_{2}e_{3}$
+\end_inset
+
+ y por tanto por 
+\begin_inset Formula $e_{1}e_{2}^{*}e_{3}$
+\end_inset
+
+ y por 
+\begin_inset Formula $\delta_{k+1}(r_{p-1},r_{q+1})=e_{1}e_{2}^{*}e_{3}\mid\cdots$
+\end_inset
+
+, luego basta eliminar 
+\begin_inset Formula $r_{p},\dots,r_{q}$
+\end_inset
+
+ y sustituir 
+\begin_inset Formula $y_{p},\dots,y_{q+1}$
+\end_inset
+
+ por su concatenación.
+\end_layout
+
+\begin_layout Plain Layout
+Recíprocamente, si 
+\begin_inset Formula ${\cal A}_{k+1}$
+\end_inset
+
+ acepta 
+\begin_inset Formula $w$
+\end_inset
+
+, existen 
+\begin_inset Formula $y_{1},\dots,y_{m}\in\Sigma^{*}$
+\end_inset
+
+ y 
+\begin_inset Formula $r_{0},\dots,r_{m}\in Q_{k+1}$
+\end_inset
+
+ con 
+\begin_inset Formula $r_{0}=q_{0}$
+\end_inset
+
+, 
+\begin_inset Formula $r_{m}=q_{\text{F}}$
+\end_inset
+
+, 
+\begin_inset Formula $w=y_{1}\cdots y_{m}$
+\end_inset
+
+ y cada 
+\begin_inset Formula $\delta_{k+1}(r_{i},r_{i+1})$
+\end_inset
+
+ acepta 
+\begin_inset Formula $y_{i+1}$
+\end_inset
+
+.
+ Entonces, por definición de 
+\begin_inset Formula $\delta_{k+1}$
+\end_inset
+
+, bien 
+\begin_inset Formula $\delta_{k}(r_{i},r_{i+1})$
+\end_inset
+
+ acepta 
+\begin_inset Formula $y_{i+1}$
+\end_inset
+
+, bien la acepta 
+\begin_inset Formula $(\delta_{k}(r_{i},q_{\text{R}}))(\delta_{k}(q_{\text{R}},q_{\text{R}}))^{*}(\delta_{k}(q_{\text{R}},r_{i+1}))$
+\end_inset
+
+, con lo que existen 
+\begin_inset Formula $z_{0},\dots,z_{p}$
+\end_inset
+
+ (
+\begin_inset Formula $p>0$
+\end_inset
+
+) con 
+\begin_inset Formula $z_{0}\cdots z_{p}=y_{i+1}$
+\end_inset
+
+, 
+\begin_inset Formula $z_{0}$
+\end_inset
+
+ aceptada por 
+\begin_inset Formula $\delta_{k}(r_{i},q_{\text{R}})$
+\end_inset
+
+, 
+\begin_inset Formula $z_{1},\dots,z_{p-1}$
+\end_inset
+
+ aceptadas por 
+\begin_inset Formula $\delta_{k}(q_{\text{R}},q_{\text{R}})$
+\end_inset
+
+ y 
+\begin_inset Formula $z_{p}$
+\end_inset
+
+ aceptada por 
+\begin_inset Formula $\delta_{k}(q_{\text{R}},r_{i+1})$
+\end_inset
+
+ y basta cambiar 
+\begin_inset Formula $y_{i+1}$
+\end_inset
+
+ por 
+\begin_inset Formula $z_{0},\dots,z_{p}$
+\end_inset
+
+ en la secuencia e insertar 
+\begin_inset Formula $q_{\text{R}}$
+\end_inset
+
+ 
+\begin_inset Formula $p$
+\end_inset
+
+ veces entre 
+\begin_inset Formula $r_{i}$
+\end_inset
+
+ y 
+\begin_inset Formula $r_{i+1}$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\end_inset
+
+
+\end_layout
+
+\end_deeper
+\begin_layout Standard
+\begin_inset Formula ${\cal REG}$
+\end_inset
+
+ está cerrado bajo unión, concatenación, clausura, complemento, intersección
+ y diferencia.
+ 
+\series bold
+Demostración:
+\series default
+ Los 3 primeros son por definición.
+ Si el DFA 
+\begin_inset Formula $(Q,\Sigma,\delta,q_{0},F)$
+\end_inset
+
+ acepta el lenguaje 
+\begin_inset Formula $L$
+\end_inset
+
+, el DFA 
+\begin_inset Formula $(Q,\Sigma,\delta,q_{0},Q\setminus F)$
+\end_inset
+
+ acepta 
+\begin_inset Formula $\overline{L}=\Sigma^{*}\setminus L$
+\end_inset
+
+, pues para cada cadena 
+\begin_inset Formula $w$
+\end_inset
+
+ solo hay una secuencia de estados 
+\begin_inset Formula $\{r_{0},\dots,r_{m}\}\subseteq Q$
+\end_inset
+
+ con 
+\begin_inset Formula $r_{0}=q_{0}$
+\end_inset
+
+ y cada 
+\begin_inset Formula $r_{i+1}=\delta(r_{i},w_{i+1})$
+\end_inset
+
+ y 
+\begin_inset Formula $w$
+\end_inset
+
+ se acepta si y sólo si 
+\begin_inset Formula $r_{m}$
+\end_inset
+
+ es final.
+ Finalmente, 
+\begin_inset Formula $L\cap M=\overline{\overline{L}\cap\overline{M}}$
+\end_inset
+
+ y 
+\begin_inset Formula $L\setminus M=L\cap\overline{M}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+
+\series bold
+Lema del bombeo
+\series default
+, 
+\series bold
+LBLR
+\series default
+ o 
+\series bold
+\emph on
+\lang english
+pumping lemma
+\emph default
+\lang spanish
+:
+\series default
+ para 
+\begin_inset Formula $L\in{\cal REG}$
+\end_inset
+
+, existe 
+\begin_inset Formula $p\in\mathbb{N}$
+\end_inset
+
+, la 
+\series bold
+\emph on
+\lang english
+pumping length
+\series default
+\emph default
+\lang spanish
+, tal que toda 
+\begin_inset Formula $w\in L$
+\end_inset
+
+ con 
+\begin_inset Formula $|w|\geq p$
+\end_inset
+
+ puede ser dividida como 
+\begin_inset Formula $w=xyz$
+\end_inset
+
+ con 
+\begin_inset Formula $|y|>0$
+\end_inset
+
+ y 
+\begin_inset Formula $|xy|\leq p$
+\end_inset
+
+ de modo que 
+\begin_inset Formula $xy^{k}z\in L$
+\end_inset
+
+ para todo 
+\begin_inset Formula $k\in\mathbb{N}$
+\end_inset
+
+.
+ 
+\series bold
+Demostración:
+\series default
+ Sean 
+\begin_inset Formula $(Q,\Sigma,\delta,q_{0},F)$
+\end_inset
+
+ un DFA que acepta 
+\begin_inset Formula $L$
+\end_inset
+
+, 
+\begin_inset Formula $p\coloneqq|Q|$
+\end_inset
+
+, 
+\begin_inset Formula $w\in L$
+\end_inset
+
+ con 
+\begin_inset Formula $|w|\geq p$
+\end_inset
+
+ y 
+\begin_inset Formula $\{q_{0},\dots,q_{n}\}\subseteq Q$
+\end_inset
+
+ con cada 
+\begin_inset Formula $q_{i+1}=\delta(q_{i},w_{i+1})$
+\end_inset
+
+, como 
+\begin_inset Formula $\{q_{0},\dots,q_{p}\}\subseteq Q$
+\end_inset
+
+, existen 
+\begin_inset Formula $i,j\in\{0,\dots,p\}$
+\end_inset
+
+ con 
+\begin_inset Formula $i<j$
+\end_inset
+
+ y 
+\begin_inset Formula $q_{i}=q_{j}$
+\end_inset
+
+.
+ Sean entonces 
+\begin_inset Formula $x\coloneqq w_{1}\cdots w_{i}$
+\end_inset
+
+, 
+\begin_inset Formula $y\coloneqq w_{i+1}\cdots w_{j}$
+\end_inset
+
+ y 
+\begin_inset Formula $z\coloneqq w_{j+1}\cdots w_{n}$
+\end_inset
+
+, entonces 
+\begin_inset Formula $w=xyz$
+\end_inset
+
+, 
+\begin_inset Formula $|y|\geq0$
+\end_inset
+
+, 
+\begin_inset Formula $|xy|=j\leq p$
+\end_inset
+
+ y, para 
+\begin_inset Formula $k\in\mathbb{N}$
+\end_inset
+
+, el DFA acepta 
+\begin_inset Formula $xy^{k}z$
+\end_inset
+
+ con la secuencia de estados 
+\begin_inset Formula $q_{0}\cdots q_{i}(q_{i+1}\cdots q_{j})^{k}q_{i+1}\cdots q_{n}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+El lenguaje 
+\begin_inset Formula $\{0^{n}1^{n}\}_{n\in\mathbb{N}}$
+\end_inset
+
+ no es regular.
+ 
+\series bold
+Demostración:
+\series default
+ Supongamos que lo sea y sean 
+\begin_inset Formula $L$
+\end_inset
+
+ el lenguaje, 
+\begin_inset Formula $p\in\mathbb{N}$
+\end_inset
+
+ una 
+\emph on
+\lang english
+pumping length
+\emph default
+\lang spanish
+ de 
+\begin_inset Formula $L$
+\end_inset
+
+, 
+\begin_inset Formula $w\coloneqq0^{p}1^{p}$
+\end_inset
+
+ y 
+\begin_inset Formula $w\eqqcolon xyz$
+\end_inset
+
+ una división dada por el lema del bombeo.
+ Si 
+\begin_inset Formula $y=0^{k}$
+\end_inset
+
+, 
+\begin_inset Formula $xy^{2k}z\notin L$
+\end_inset
+
+ porque tiene más 0s que 1s; análogamente, si 
+\begin_inset Formula $y=1^{k}$
+\end_inset
+
+, 
+\begin_inset Formula $xy^{2k}z\notin L$
+\end_inset
+
+, y si 
+\begin_inset Formula $y=0^{k}1^{l}$
+\end_inset
+
+ con 
+\begin_inset Formula $k,l>0$
+\end_inset
+
+, 
+\begin_inset Formula $xyyz\notin L$
+\end_inset
+
+ porque tiene un 1 seguido de un 
+\begin_inset Formula $0\#$
+\end_inset
+
+.
+\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.
+\end_layout
+
+\end_body
+\end_document
-- 
cgit v1.2.3