1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
\documentclass{beamer}
\usepackage[utf8]{inputenc}
\title{Finite Automata and Formal Languages (18CS52)}
\author{Akshay O}
\institute[R V College of Engineering]
{
Submitted To: Dr. Krishnappa H K\\
Assistant Professor
\and
Self Study Assignment
}
\begin{document}
\frame{\titlepage}
\begin{frame}
\frametitle{Problem Statement}
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.
\end{frame}
\begin{frame}
\frametitle{Proof}
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.
\end{frame}
\begin{frame}
\frametitle{Proof}
For an empty input, $|w| = 0$, both DFAs remain in the start state.
The start states of $M_1$ and $M_2$, $p_0$ and $q_0$ respectively; are indistinguishable because
\begin{equation}
L(M_1) = L(M_2) = L
\end{equation}
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$.
\end{frame}
\begin{frame}
\frametitle{Proof}
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$.
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.
\end{frame}
\begin{frame}
\frametitle{Conclusion}
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:
\[ \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 \]
\[ \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 \]
\end{frame}
\begin{frame}
\frametitle{Conclusion (contd.)}
There is a one-one mapping between $M_1$ and $M_2$:
\[ p_0 \leftrightarrow q_0 \]
\[ \delta_{M_1} \leftrightarrow \delta_{M_2} \]
\[ p_f \leftrightarrow q_f \]
Hence, $M_1$ and $M_2$ are isomorphic.
\end{frame}
\end{document}
|
