**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 |