\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 minimalizació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(q,a)\}$ 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,above right=of s] (q_1)   {$q_1$};
      \node[state,below right=of s] (q_2)   {$q_2$};
      \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,above right=of s] (q_1)   {$q_1$};
      \node[state,below right=of s] (q_2)   {$q_2$};
      \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}

Ya nos deshicimos del estado inaccesible, ahora está todo para aplicar el algoritmo. Vamos paso a paso, armemos la tabla:

\begin{center}
  \begin{tabular}{|c|c|c|c|c|c|}
    \hline
    Estados & $S$ & $q_1$ & $q_2$ & $q_3$ & $q_4$ \\
    \hline
    $S$ &  &  &  &  &\\
    $q_1$ &  &  &  &  &\\
    $q_2$ &  &  &  &  &\\
    $q_3$ &  &  &  &  &\\
    $q_4$ &  &  &  &  &\\
    \hline
  \end{tabular}
\end{center}

Quizá este método no es el mejor visualmente, pero es más directo de lo que se escribe en el algoritmo. Noten que las parejas $\{ q_i,q_i\}$ siempre se pueden colapsar, es el mismo estado colapsado a si mismo, la versión del Kozen se ahorra estos cuadros.

Marcamos todos las parejas que incluyen un estado final, los que incluyan a $q_3$ y $q_4$.

\begin{center}
  \begin{tabular}{|c|c|c|c|c|c|}
    \hline
    Estados & $S$ & $q_1$ & $q_2$ & $q_3$ & $q_4$ \\
    \hline
    $S$ &  &  & &\checkmark  & \checkmark  \\
    $q_1$ &  &  & &\checkmark  & \checkmark  \\
    $q_2$ &  &  & &\checkmark  & \checkmark  \\
    $q_3$ & \checkmark  & \checkmark  & \checkmark  &  &\\
    $q_4$ & \checkmark  & \checkmark  & \checkmark  &  &\\
    \hline
  \end{tabular}
\end{center}

Noten que sólo se marca si uno de los dos es final, no ambos (esos podría ser que sí colapsen, aún no lo sabemos). Vamos al siguiente paso: vemos por pares sin marcar para los valores $a$ o $b$ hacia donde van.

Empezamos con $\{S,q_1\}$, con $a$ $S\overset{a}{\rightarrow} q_1$ y $q_1 \overset{a}{\rightarrow} q_2 $, entonces $\{s,q_1\}\overset{a}{\rightarrow}\{q_1,q_2\}$, que no está marcado, seguimos sin marcarlo.

¿Qué pasa con $b$? $\{s,q_1\}\overset{b}{\rightarrow}\{q_2,q_3\}$, que sí está marcado, lo marcamos entonces (y también el par simétrico $\{ q_1,s\}$).

Ahora vemos que pasa con el par $\{S,q_2\}$:

\begin{align*}
  \{S,q_2\}\overset{a}{\rightarrow}& \{ q_1,q_2\}\text{ sin marcar}\\
  \{S,q_2\}\overset{b}{\rightarrow}& \{ q_2,q_4\}\text{ se marca \checkmark, así como el simétrico}
\end{align*}

\begin{center}
  \begin{tabular}{|c|c|c|c|c|c|}
    \hline
    Estados & $S$ & $q_1$ & $q_2$ & $q_3$ & $q_4$ \\
    \hline
    $S$ &  &\checkmark  &\checkmark &\checkmark  & \checkmark  \\
    $q_1$ &\checkmark  &  & &\checkmark  & \checkmark  \\
    $q_2$ &\checkmark  &  & &\checkmark  & \checkmark  \\
    $q_3$ & \checkmark  & \checkmark  & \checkmark  &  &\\
    $q_4$ & \checkmark  & \checkmark  & \checkmark  &  &\\
    \hline
  \end{tabular}
\end{center}

El siguiente sería $\{S,q_3\}$, pero ya está marcado, al igual que $\{ S,q_4\}$. Saltemos hasta el $\{q_1,q_2\}$
\begin{align*}
  \{q_1,q_2\}\overset{a}{\rightarrow}& \{ q_2,q_2\}\text{ no se marca}\\
  \{q_1,q_2\}\overset{b}{\rightarrow}& \{ q_3,q_4\}\text{ no se marca}
\end{align*}

Y ya no podemos hacer más, si volvemos a barrer la tabla llegamos a los mismos estados sin marcar.

Lo que quiere decir que $q_1$ y $q_2$ son colapsables, así como $q_3$ y $q_4$. Entonces el autómata reducido es como se ve en la imagen \ref{fig:fin}. Es casi autómatico pasar a este autómata, las trancisiones que iban al estado $q_1$ o $q_2$ ahora van al estado $q_{1-2}$, las que iban al estado $q_3$ o $q_4$ ahora van al estado $q_{3-4}$.

\begin{figure}[h!]
  \begin{center}
    \begin{tikzpicture}
      \node[state,initial,initial text= ] (s)   {$S$};
      \node[state,right=of s] (q12)   {$q_{1-2}$};
      \node[state,accepting,right=of q12] (q34)   {$q_{3-4}$};
      
      \path [-stealth,thick]
      (s) edge node[yshift=0.3cm]{$a,b$} (q12)
      (q12) edge [loop above] node {$a$} ()
      edge node[yshift=0.3cm] {$b$} (q34)
      (q34) edge [loop above] node {$a,b$} ();
      					
    \end{tikzpicture}
  \end{center}
  \caption{Autómata determinista ya reducido al mínimo.}
  \label{fig:fin}
\end{figure}

Veamos otro ejemplo ahora a partir de una tabla.

\textbf{Ejemplo:} Minimaliza el siguiente autómata
\begin{center}
  \begin{tabular}{||c||c c||} 
    \hline
    Estado & a & b  \\ [0.5ex] 
    \hline\hline
    $\rightarrow S$ & $Q_1$ & $Q_5$  \\ 
    \hline
    $Q_1$ & $S$ & $Q_5$  \\
    \hline
    $Q_2$ & $Q_6$ & $S$ \\
    \hline
    $Q_3$ & $Q_7$ & $Q_1$ \\
    \hline
    $Q_4$ & $S$ & $Q_6$ \\
    \hline
    $Q_5^*$ & $Q_7$ & $Q_2$ \\
    \hline
    $Q_6^*$ & $S$ & $Q_3$ \\
    \hline
    $Q_7^*$ & $S$ & $Q_2$ \\ [1ex] 
    \hline
  \end{tabular}
\end{center}

Espero sea claro que $S$ es el estado inicial y $Q_5$, $Q_6$ y $Q_7$, los estados marcados con asterisco, son estados finales. De analizar la tabla podemos encontrar los estados inaccesibles, aquellos estados que no aparezcan del lado derecho de la tabla. Revisando podemos ver que el estado $Q_4$ no aparece en ninguna transición desde otro estado. Podemos eliminarlo.

\begin{center}
  \begin{tabular}{||c||c c||} 
    \hline
    Estado & a & b  \\ [0.5ex] 
    \hline\hline
    $S$ & $Q_1$ & $Q_5$  \\ 
    \hline
    $Q_1$ & $S$ & $Q_5$  \\
    \hline
    $Q_2$ & $Q_6$ & $S$ \\
    \hline
    $Q_3$ & $Q_7$ & $Q_1$ \\
    \hline
    $Q_5^*$ & $Q_7$ & $Q_2$ \\
    \hline
    $Q_6^*$ & $S$ & $Q_3$ \\
    \hline
    $Q_7^*$ & $S$ & $Q_2$ \\ [1ex] 
    \hline
  \end{tabular}
\end{center}

Ya sin estados inaccesibles armamos la tabla \ref{tab:1}, empezando vacía y marcamos, como lo dice el algoritmo, las parejas \{\emph{estado final, no estado final}\} o viceversa. 

\begin{table}[h!]
  \begin{center}
    \begin{tabular}{c c c c c c c} 
      \hline
      $S$ & & & & & & \\ 
      \hline
      & $Q_1$ & & & & & \\ 
      \hline
      & & $Q_2$ & & & & \\
      \hline
      & & & $Q_3$ & & & \\
      \hline
      & & & & $Q_5$ & & \\
      \hline 
      & & & & & $Q_6$ & \\  
      \hline
      & & & & & & $Q_7$ \\[1ex]
      \hline
    \end{tabular}
    \caption{Tabla para la minimalización de estados del autómata.}
    \label{tab:1}
  \end{center}
\end{table}

Una vez marcadas las parejas \{\emph{estado final, no estado final}\}, revisamos las posibles transiciones de cada estado de la pareja para cada símbolo del alfabeto.

\begin{table}[h!]
  \begin{center}
    \begin{tabular}{c c c c c c c} 
      \hline
      $S$ & & & & & & \\ 
      \hline
      & $Q_1$ & & & & & \\ 
      \hline
      & & $Q_2$ & & & & \\
      \hline
      & & & $Q_3$ & & & \\
      \hline
      \checkmark& \checkmark & \checkmark & \checkmark & $Q_5$ & & \\
      \hline 
      \checkmark & \checkmark & \checkmark & \checkmark & & $Q_6$ & \\  
      \hline
      \checkmark & \checkmark & \checkmark & \checkmark & & & $Q_7$ \\[1ex]
      \hline
    \end{tabular}
    \caption{Tabla para la minimalización de estados del autómata.}
    \label{tab:2}
  \end{center}
\end{table}

Se pueden ver las siguientes posibilidades:

\begin{align*}
  \{S,Q_1\} &\overset{a}{\rightarrow} \{Q_1,S\} \text{, que no está marcado} \\
  \{S,Q_1\} &\overset{b}{\rightarrow} \{Q_5,Q_5\} \text{, que no puede estar marcado}\\
  \{S,Q_2\} &\overset{a}{\rightarrow} \{Q_1,Q_6\} \text{, que sí está marcado \checkmark}\\
  \{S,Q_3\} &\overset{a}{\rightarrow} \{Q_1,Q_7\} \text{, que sí está marcado \checkmark}\\
  \{Q_1,Q_2\} &\overset{a}{\rightarrow} \{S,Q_6\} \text{, que sí está marcado \checkmark}\\
  \{Q_1,Q_3\} &\overset{a}{\rightarrow} \{S,Q_7\} \text{, que sí está marcado \checkmark}\\
  \{Q_2,Q_3\} &\overset{a}{\rightarrow} \{Q_6,Q_7\} \text{, que no está marcado}\\
  \{Q_2,Q_3\} &\overset{b}{\rightarrow} \{S,Q_1\} \text{, que no está marcado}\\
  \{Q_5,Q_6\} &\overset{a}{\rightarrow} \{Q_7,S\} \text{, que sí está marcado \checkmark}\\
  \{Q_5,Q_7\} &\overset{a}{\rightarrow} \{Q_7,S\} \text{, que sí está marcado \checkmark}\\
  \{Q_6,Q_7\} &\overset{a}{\rightarrow} \{S,S\} \text{, que no puede estar marcado}\\
  \{Q_6,Q_7\} &\overset{b}{\rightarrow} \{Q_3,Q_2\} \text{, que no está marcado}
\end{align*}

Una vez con viendo las transiciones podemos seguir repitiendo el paso, pero vemos que las parejas sin marcar siguen si poderse marcar. Para ese caso la tabla queda como se ve en \ref{tab:3}

\begin{table}[h!]
  \begin{center}
    \begin{tabular}{c c c c c c c} 
      \hline
      $S$ & & & & & & \\ 
      \hline
      & $Q_1$ & & & & & \\ 
      \hline
      \checkmark & \checkmark & $Q_2$ & & & & \\
      \hline
      \checkmark & \checkmark & & $Q_3$ & & & \\
      \hline
      \checkmark& \checkmark & \checkmark & \checkmark & $Q_5$ & & \\
      \hline 
      \checkmark & \checkmark & \checkmark & \checkmark & \checkmark & $Q_6$ & \\  
      \hline
      \checkmark & \checkmark & \checkmark & \checkmark & \checkmark & & $Q_7$ \\[1ex]
      \hline
    \end{tabular}
    \caption{Tabla para la minimalización de estados del autómata.}
    \label{tab:3}
  \end{center}
\end{table}

Lo que quiere decir, que aunque demos más vueltas ya no podemos marcar más y por lo tanto las equivalencias son $S\equiv Q_1$, $Q_2\equiv Q_3$ y $Q_6\equiv Q_7$, estos estados pueden colapsarse. Les muestro la tabla y ya les toca a ustedes hacer el autómata:

\begin{center}
  \begin{tabular}{||c||c c||} 
    \hline
    Estado & a & b  \\ [0.5ex] 
    \hline\hline
    $\{S,Q_1\}$ & $\{S,Q_1\}$ & $Q_5$  \\ 
    \hline
    $\{Q_2,Q_3\}$ & $\{Q_6,Q_7\}$ & $\{S,Q_1\}$  \\
    \hline
    $Q_5^*$ & $\{Q_6,Q_7\}$ & $\{Q_2,Q_3\}$ \\
    \hline
    $\{Q_6,Q_7\}^*$ & $S$ & $\{Q_2,Q_3\}$ \\
    \hline
  \end{tabular}
\end{center}

\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}
