From 6e18a4da63a46a54b531422dcc80b46cba80490b Mon Sep 17 00:00:00 2001
From: Akshay <nerdy@peppe.rs>
Date: Mon, 14 Dec 2020 22:47:05 +0530
Subject: init

---
 presentation.tex | 70 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 70 insertions(+)
 create mode 100644 presentation.tex

(limited to 'presentation.tex')

diff --git a/presentation.tex b/presentation.tex
new file mode 100644
index 0000000..0ca6878
--- /dev/null
+++ b/presentation.tex
@@ -0,0 +1,70 @@
+\documentclass{beamer}
+
+\usepackage[utf8]{inputenc}
+
+
+\title{Finite Automata and Formal Languages (18CS52)}
+\author{Akshay O}
+\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}
+    Let $M_1$ and $M_2$ be two minimal DFAs (have as few states as possible) accepting the language $L$. Both $M_1$ and $M_2$ must have exactly the same number of states because, if one had more states than the other, it would not be a minimal DFA.
+\end{frame}
+
+\begin{frame}
+    \frametitle{Proof}
+
+    For an empty input, $|w| = 0$, both DFAs remain in the start state.
+    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}
-- 
cgit v1.2.3