128 lines
5.7 KiB
TeX
128 lines
5.7 KiB
TeX
\documentclass[10pt,a4paper]{article}
|
|
\usepackage[utf8]{inputenc}
|
|
\usepackage[spanish]{babel}
|
|
\usepackage{amsmath}
|
|
\usepackage{amsfonts}
|
|
\usepackage{amssymb}
|
|
\usepackage{hyperref}
|
|
\usepackage{graphicx}
|
|
\usepackage{pgf}
|
|
\usepackage{tikz}
|
|
\usetikzlibrary{automata,positioning,arrows}
|
|
\renewcommand{\rmdefault}{ptm}
|
|
%\usepackage[all,cmtip]{xy}
|
|
%\usepackage{graphicx}
|
|
\author{Autómatas y Lenguajes Formales}
|
|
\title{Algoritmo de minimización}
|
|
\begin{document}
|
|
\maketitle
|
|
\section*{Automata cociente}
|
|
|
|
La idea del algoritmo de minimización es colapsar estados, dos o más estados se reducen a uno. Eso no se puede hacer de forma deliberada, debe haber un método formal y que nos asegure que no estamos perdiendo transiciones.
|
|
|
|
Para ello debemos definir algunas cosas. Para empezar podemos notar que no es deseable colapsar un estado de aceptación con uno de rechazo, son radicalmente distintos. Cualesquiera dos o más estados que se colapsen deben mantener el determinismo (recuerden estamos minimizando un autómata finito determinista).
|
|
|
|
Definimos una relación de equivalencia entre dos estados, que como bien sospechan, serán los dos a colapsar.
|
|
|
|
Definimos una relación de equivalencia entre $q$ y $r$ como:
|
|
\begin{equation*}
|
|
q\approx r \ \iff \ \{\forall \alpha.\delta^*(q,\alpha)\in F \iff \delta^*(r,\alpha)\in F \},
|
|
\end{equation*}
|
|
|
|
\noindent siendo $q,r\in Q$ y $\alpha\in \Sigma*$. Esta relación de equivalencia cumple con ser reflexiva, simétrica y transitiva, y parte el conjunto en subconjuntos disconexos llamados clases de equivalencia
|
|
|
|
\begin{equation*}
|
|
[p] \overset{def}{=} \{ q|q \approx p\}
|
|
\end{equation*}
|
|
|
|
Definimos un autómata cociente. Partimos del autómata $A=( Q,\Sigma, \delta, s, F)$ y definimos al autómata cociente como $A/\approx = (Q_{\approx},\Sigma,\delta_{\approx},s_{\approx},F_{\approx})$:
|
|
|
|
\begin{align*}
|
|
Q_{\approx} =& \{[q] | q\in Q\} \\
|
|
\delta_{\approx}([q],a) =& [\delta(q,a)] \\
|
|
s_{\approx} =& [s] \\
|
|
F_{\approx} =& \{ [f] | f\in F\}
|
|
\end{align*}.
|
|
|
|
Hay un estado de $A/{\approx}$ por cada clase de equivalencia, es decir, todos los estados colapsados están en un estado para el autómata cociente. Sólo restaría ver si la función de transición está bien definida, pero eso pueden consultarlo en el libro\cite{Kozen}.
|
|
|
|
\section*{Algoritmo de minimización}
|
|
|
|
Entonces vamos ahora sí a dar un método sistemático para colapsar estados, tan sistemático que hasta numerado está (recuerden que trabajamos con autómatas finitos deterministas sin estados inalcanzables, si quieren reducir uno no determinista primero deben pasarlo a determinista):
|
|
|
|
\begin{enumerate}
|
|
\item Escribe una tabla vacía de todos los pares $\{p,q\}$.
|
|
\item Marca $\{p,q\}$ si $p\in F$ y $q\neg \in F$ o al revés.
|
|
\item Paso recursivo, \textbf{repítelo hasta que ya no haya nada más por marcar}: si existe un par sin marcar $\{ p,q\}$ tal que su par de transiciones $\{ \delta(p,a),\delta(p,q)\}$ sí está marcado para algún símbolo del alfabeto, $a\in \Sigma$, entonces se marca el par $\{ p,q\}$.
|
|
\item Si ya no hay más que marcar por el \textit{loop} pasado, $p\approx q$ si $\{ p,q\}$ no está marcado.
|
|
\end{enumerate}
|
|
|
|
Vemos un ejemplo:
|
|
|
|
\begin{figure}[h!]
|
|
\begin{center}
|
|
\begin{tikzpicture}
|
|
\node[state,initial,initial text= ] (s) {$S$};
|
|
\node[state,accepting,above right=of s] (q_1) {$q_1$};
|
|
\node[state,below right=of s] (q_2) {$q_{0_a}$};
|
|
\node[state,accepting,right=of q_1] (q_3) {$q_3$};
|
|
\node[state,accepting,right=of q_2] (q_4) {$q_4$};
|
|
\node[state,right=of q_4] (q_5) {$q_5$};
|
|
|
|
\path [-stealth,thick]
|
|
(s) edge node[yshift=0.3cm]{$a$} (q_1)
|
|
edge node[yshift=0.3cm]{$b$} (q_2)
|
|
(q_1) edge node[xshift=0.3cm]{$a$} (q_2)
|
|
edge node[yshift=0.3cm]{$b$} (q_3)
|
|
(q_2) edge node[yshift=0.3cm]{$b$} (q_4)
|
|
edge [loop below] node {$a$} ()
|
|
(q_3) edge [loop above] node {$a,b$} ()
|
|
(q_4) edge [loop below] node {$a,b$} ()
|
|
(q_5) edge node[yshift=0.3cm]{$b$} (q_4)
|
|
edge [loop below] node {$a$} ();
|
|
|
|
\end{tikzpicture}
|
|
\end{center}
|
|
\caption{Autómata determinista con estados inaccesibles, por reducir.}
|
|
%\label{fig:10}
|
|
\end{figure}
|
|
|
|
Este autómata aún tiene un estado inaccesible, es decir, ninguna flecha entra en él, no hay transiciones hacia él, por lo tanto es inaccesible, no podemos llegar a ese estado de ninguna manera. Si lo borramos no perdemos nada pues no hay manera de llegar a él.
|
|
|
|
\begin{figure}[h!]
|
|
\begin{center}
|
|
\begin{tikzpicture}
|
|
\node[state,initial,initial text= ] (s) {$S$};
|
|
\node[state,accepting,above right=of s] (q_1) {$q_1$};
|
|
\node[state,below right=of s] (q_2) {$q_{0_a}$};
|
|
\node[state,accepting,right=of q_1] (q_3) {$q_3$};
|
|
\node[state,accepting,right=of q_2] (q_4) {$q_4$};
|
|
|
|
\path [-stealth,thick]
|
|
(s) edge node[yshift=0.3cm]{$a$} (q_1)
|
|
edge node[yshift=0.3cm]{$b$} (q_2)
|
|
(q_1) edge node[xshift=0.3cm]{$a$} (q_2)
|
|
edge node[yshift=0.3cm]{$b$} (q_3)
|
|
(q_2) edge node[yshift=0.3cm]{$b$} (q_4)
|
|
edge [loop below] node {$a$} ()
|
|
(q_3) edge [loop above] node {$a,b$} ()
|
|
(q_4) edge [loop below] node {$a,b$} ();
|
|
|
|
\end{tikzpicture}
|
|
\end{center}
|
|
\caption{Autómata determinista sin estados inaccesibles, aún hay más por reducir.}
|
|
%\label{fig:10}
|
|
\end{figure}
|
|
|
|
|
|
\begin{thebibliography}{10}
|
|
\bibitem{Kozen} Kozen, Dexter C. ``Automata and Computability'' Springer (1997)
|
|
\bibitem{Sipser} Sipser, Michael ``Introduction to the Theory of Computation'' 2a ed., Thomson Course Tecnology (2006)
|
|
\bibitem{Lewis} Lewis, Harry R. y Papadimitriou, Christos H. ``Elements of the Theory of Computation''2a ed., Prentice-Hall Inc. (1998).
|
|
|
|
|
|
\end{thebibliography}
|
|
|
|
|
|
\end{document}
|