5 files changed, 136 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..00fd323
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,3 @@
+result
+.envrc
+.direnv
diff --git a/flake.lock b/flake.lock
new file mode 100644
index 0000000..2a45856
--- /dev/null
+++ b/flake.lock
@@ -0,0 +1,25 @@
+{
+  "nodes": {
+    "nixpkgs": {
+      "locked": {
+        "lastModified": 1607855778,
+        "narHash": "sha256-D4/b7xDssBKxgYqw818fz2r4ZKcgEgfenaq72O7id7I=",
+        "owner": "NixOS",
+        "repo": "nixpkgs",
+        "rev": "37dfd61f02dbbb75c088786b24c37eb08ddf446e",
+        "type": "github"
+      },
+      "original": {
+        "id": "nixpkgs",
+        "type": "indirect"
+      }
+    },
+    "root": {
+      "inputs": {
+        "nixpkgs": "nixpkgs"
+      }
+    }
+  },
+  "root": "root",
+  "version": 7
+}
diff --git a/flake.nix b/flake.nix
new file mode 100644
index 0000000..19f063e
--- /dev/null
+++ b/flake.nix
@@ -0,0 +1,19 @@
+{
+  description = "Project presentation for Finite Automata and Formal Languages";
+
+  outputs = { self, nixpkgs }: 
+    let 
+      pkgs = import nixpkgs { system = "x86_64-linux"; };
+    in
+    with pkgs;
+    {
+      defaultPackage.x86_64-linux = stdenv.mkDerivation {
+        name = "fafl";
+        src = ./.;
+        buildInputs = [ 
+          texlive.combined.scheme-full 
+          gnumake
+        ];
+      };
+    };
+}
diff --git a/makefile b/makefile
new file mode 100644
index 0000000..9539d3b
--- /dev/null
+++ b/makefile
@@ -0,0 +1,19 @@
+DOCNAME=presentation
+PDFLATEX="pdflatex -interaction=nonstopmode"
+
+.PHONY: $(DOCNAME).pdf all clean
+
+all: $(DOCNAME).pdf
+
+$(DOCNAME).pdf: $(DOCNAME).tex
+        latexmk -pdf -pdflatex=$(PDFLATEX) -use-make $(DOCNAME).tex
+
+watch: $(DOCNAME).tex
+        latexmk -pvc -pdf -pdflatex=$(PDFLATEX) -use-make $(DOCNAME).tex
+
+clean:
+        latexmk -CA
+
+install:
+        cp $(DOCNAME).pdf ${out}/
+
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}