\documentclass{beamer}

\usepackage[utf8]{inputenc}

\usefonttheme{serif}
\title{Finite Automata and Formal Languages (18CS52)}
\author{Akshay O (1RV18CS016)}
\institute[R V College of Engineering]
{
    Submitted To: Dr. Krishnappa H K\\
    Assistant Professor
    \and
    Self Study Assignment
}

\begin{document}

\frame{\titlepage}

\begin{frame}
    \frametitle{Problem Statement}
    Suppose that $M_1(Q, \Sigma, \delta, p_0, F)$ and $M_2(Q, \Sigma, \delta, q_0, F)$ are both DFAs accepting the language $L$, and both have as few states as possible. Show that $M_1$ and $M_2$ are isomorphic.
\end{frame}

\begin{frame}
    \frametitle{Proof}
    Consider the union of $M_1$ and $M_2$ (assume there are no common names of states among the two). The transition function of the combined automaton is the union of the transition rules of $M_1$ and $M_2$. Run the state distinguishability process on this new DFA.
\end{frame}

\begin{frame}
    \frametitle{Proof}

    The start states of $M_1$ and $M_2$, $p_0$ and $q_0$ respectively; are indistinguishable because 
    \begin{equation}
        L(M_1) = L(M_2) = L
    \end{equation}

    Any successor state that is reachable by input of one symbol is also indistinguishable. The reason being, if they were distinguishable, then we could distinguish $p_0$ and $q_0$.
\end{frame}

\begin{frame}
    \frametitle{Proof}

    Assume an input of length $k$, that is, $w = a_1 a_2 a_3 ... a_k$, is applied to DFAs $M_1$ and $M_2$. This string takes the state of $M_1$ to a state, say $p$, and $M_2$ to a state, say $q$. 

    From $(1)$, we know that their start states are indistinguishable. Hence, on an input of $a_1$, the successor states, $p_1$ and $q_1$ are also indistinguishable. The successors of those states on an input of $a_2$; $p_2$ and $q_2$ are also indistinguishable, and so on.
\end{frame}

\begin{frame}
    \frametitle{Conclusion}

    Every state in $M_1$ has a corresponding state in $M_2$ such that the two states are indistinguishable. Also, the transition rules for $M_1$ and $M_2$ are similarly identical:
    \[ \hat{\delta_{M_1}}(p_0, a_1 a_2 a_3 ... a_k) = \hat{\delta_{M_1}}(p_1, a_2 a_3 ... a_k) = \ldots = \delta_{M_1}(p_{k-1}, a_k) = p_k \]
    \[ \hat{\delta_{M_2}}(q_0, a_1 a_2 a_3 ... a_k) = \hat{\delta_{M_2}}(q_1, a_2 a_3 ... a_k) = \ldots = \delta_{M_2}(q_{k-1}, a_k) = q_k \]
\end{frame}

\begin{frame}
    \frametitle{Conclusion (contd.)}
    There is a one-one mapping between $M_1$ and $M_2$:

    \[ p_0 \leftrightarrow q_0 \]
    \[ \delta_{M_1} \leftrightarrow \delta_{M_2} \]
    \[ p_f \leftrightarrow q_f \]

    Hence, $M_1$ and $M_2$ are isomorphic.

\end{frame}

\end{document}