diff options
-rw-r--r-- | presentation.tex | 7 |
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 |