summaryrefslogtreecommitdiff log msg author committer range
diff options
 context: 12345678910152025303540 space: includeignore mode: unifiedssdiffstat only
-rw-r--r--presentation.tex7
1 files changed, 3 insertions, 4 deletions
 diff --git a/presentation.tex b/presentation.texindex 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 34 36 L(M_1) = L(M_2) = L 35 L(M_1) = L(M_2) = L