diff options
Diffstat (limited to 'presentation.tex')
-rw-r--r-- | presentation.tex | 70 |
1 files changed, 70 insertions, 0 deletions
diff --git a/presentation.tex b/presentation.tex new file mode 100644 index 0000000..0ca6878 --- /dev/null +++ b/presentation.tex | |||
@@ -0,0 +1,70 @@ | |||
1 | \documentclass{beamer} | ||
2 | |||
3 | \usepackage[utf8]{inputenc} | ||
4 | |||
5 | |||
6 | \title{Finite Automata and Formal Languages (18CS52)} | ||
7 | \author{Akshay O} | ||
8 | \institute[R V College of Engineering] | ||
9 | { | ||
10 | Submitted To: Dr. Krishnappa H K\\ | ||
11 | Assistant Professor | ||
12 | \and | ||
13 | Self Study Assignment | ||
14 | } | ||
15 | |||
16 | \begin{document} | ||
17 | |||
18 | \frame{\titlepage} | ||
19 | |||
20 | \begin{frame} | ||
21 | \frametitle{Problem Statement} | ||
22 | 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. | ||
23 | \end{frame} | ||
24 | |||
25 | \begin{frame} | ||
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. | ||
28 | \end{frame} | ||
29 | |||
30 | \begin{frame} | ||
31 | \frametitle{Proof} | ||
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 | ||
35 | \begin{equation} | ||
36 | L(M_1) = L(M_2) = L | ||
37 | \end{equation} | ||
38 | |||
39 | 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$. | ||
40 | \end{frame} | ||
41 | |||
42 | \begin{frame} | ||
43 | \frametitle{Proof} | ||
44 | |||
45 | 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$. | ||
46 | |||
47 | 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. | ||
48 | \end{frame} | ||
49 | |||
50 | \begin{frame} | ||
51 | \frametitle{Conclusion} | ||
52 | |||
53 | 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: | ||
54 | \[ \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 \] | ||
55 | \[ \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 \] | ||
56 | \end{frame} | ||
57 | |||
58 | \begin{frame} | ||
59 | \frametitle{Conclusion (contd.)} | ||
60 | There is a one-one mapping between $M_1$ and $M_2$: | ||
61 | |||
62 | \[ p_0 \leftrightarrow q_0 \] | ||
63 | \[ \delta_{M_1} \leftrightarrow \delta_{M_2} \] | ||
64 | \[ p_f \leftrightarrow q_f \] | ||
65 | |||
66 | Hence, $M_1$ and $M_2$ are isomorphic. | ||
67 | |||
68 | \end{frame} | ||
69 | |||
70 | \end{document} | ||