summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAkshay <[email protected]>2020-12-16 04:58:32 +0000
committerAkshay <[email protected]>2020-12-16 04:58:32 +0000
commit10c15b2e9a42f164fac2d5ea67d37a99a9f53532 (patch)
tree5f978f910685311641ecff31c0a9c7239eca96af
parent6e18a4da63a46a54b531422dcc80b46cba80490b (diff)
wordingHEADmaster
-rw-r--r--presentation.tex7
1 files changed, 3 insertions, 4 deletions
diff --git a/presentation.tex b/presentation.tex
index 0ca6878..a6d3238 100644
--- a/presentation.tex
+++ b/presentation.tex
@@ -2,9 +2,9 @@
2 2
3\usepackage[utf8]{inputenc} 3\usepackage[utf8]{inputenc}
4 4
5 5\usefonttheme{serif}
6\title{Finite Automata and Formal Languages (18CS52)} 6\title{Finite Automata and Formal Languages (18CS52)}
7\author{Akshay O} 7\author{Akshay O (1RV18CS016)}
8\institute[R V College of Engineering] 8\institute[R V College of Engineering]
9{ 9{
10 Submitted To: Dr. Krishnappa H K\\ 10 Submitted To: Dr. Krishnappa H K\\
@@ -24,13 +24,12 @@
24 24
25\begin{frame} 25\begin{frame}
26 \frametitle{Proof} 26 \frametitle{Proof}
27 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. 27 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.
28\end{frame} 28\end{frame}
29 29
30\begin{frame} 30\begin{frame}
31 \frametitle{Proof} 31 \frametitle{Proof}
32 32
33 For an empty input, $|w| = 0$, both DFAs remain in the start state.
34 The start states of $M_1$ and $M_2$, $p_0$ and $q_0$ respectively; are indistinguishable because 33 The start states of $M_1$ and $M_2$, $p_0$ and $q_0$ respectively; are indistinguishable because
35 \begin{equation} 34 \begin{equation}
36 L(M_1) = L(M_2) = L 35 L(M_1) = L(M_2) = L