-
Notifications
You must be signed in to change notification settings - Fork 0
/
hw02.tex
125 lines (115 loc) · 7.08 KB
/
hw02.tex
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
\documentclass[11pt,letterpaper]{article}
\usepackage{preamble}
\title{Homework Assignment 02 \\
\small Due: September 13, 2019}
\begin{document}
\maketitle
\section{Cardinality}
\subsection{Finite Cardinality Sets}
The collection of all finite cardinality sets of finite length strings of $0's$ and $1's$ is countably infinite as we can have a one-to-one mapping with the set of Natural Numbers. By the diagonalization method, we can map the set of $1,2,3,\cdots$ to the sets containing strings of length $1,2,3,\cdots$. Hence, the collection of all finite cardinality sets of finite length strings is \textit{countably infinite}.
\subsection{Infinite Cardinality Sets}
The collection of all sets of finite
length strings of $0's$ and $1's$ is uncountably infinite as any set in the collection can be of infinite cardinality, thereby making the collection itself \textit{uncountably infinite}.
\section{Finite Automata}
\label{sec:s2}
$L(M)$ is the set of strings that start and end with the same character. Therefore, strings accepted: $\epsilon$, $0$, $1$, $0x0$, $1x1$
\subsection{Nondeterministic}
\begin{figure}[!ht]
\label{fig:nfa}
\centering
\begin{tikzpicture}
% States %
\node[state, initial, accepting] at (-2,0) (S) {S};
\node[state] at (0,2) (0x) {0x};
\node[state] at (0,-2) (1x) {1x};
\node[state, accepting] at (2,0) (F) {F};
% Edges %
\draw [->]
(S) edge[below] node{0} (0x)
(S) edge[above] node{1} (1x)
(S) edge[above] node{0,1} (F)
(0x) edge[below] node{0} (F)
(1x) edge[above] node{1} (F)
(0x) edge[loop above] node{0,1} (0x)
(1x) edge[loop below] node{0,1} (1x);
\end{tikzpicture}
\caption{NFA for \hyperref[sec:s2]{Section 2}}
\end{figure}
The following \hyperref[tab:nfa]{state table} can be constructed from the above \hyperref[fig:nfa]{drawing representation}. The accepting states ($S,[0xF],[1xF]$) are marked with $*$.
\begin{table}[!ht]
\label{tab:nfa}
\centering
\begin{tabular}{c| c c}
& $0$ & $1$ \\
\hline
$S*$ & $[0xF]$ & $[1xF]$ \\
$[0xF]*$ & $[0xF]$ & $0x$ \\
$[1xF]*$ & $1x$ & $[1xF]$ \\
$0x$ & $[0xF]$ & $0x$ \\
$1x$ & $1x$ & $[1xF]$
\end{tabular}
\caption{State Table for \hyperref[fig:nfa]{NFA}}
\end{table}
\paragraph{}
\small [AB] is a new state needed in the DFA that corresponds to the next state being either A or B in the equivalent NFA. Hence, in the \hyperref[tab:nfa]{table above}, from $S$, on seeing a $0$ or a $1$, we can either go to the $0x$ or the $F$ state or the $1x$ or the $F$ state respectively.
\subsection{Deterministic}
We need 5 states for the equivalent DFA of the \hyperref[fig:nfa]{NFA} above ($S$, $0xF$, $1xF$, $0x$, $1x$). Of them, the first three are accepting states. The \hyperref[fig:dfa]{drawing} representation of the equivalent DFA is as below
\begin{figure}[!ht]
\label{fig:dfa}
\centering
\begin{tikzpicture}
% States %
\node[state, initial, accepting] at (-2,0) (S) {S};
\node[state, accepting] at (0,2) (0xF) {0xF};
\node[state, accepting] at (0,-2) (1xF) {1xF};
\node[state] at (2,2) (0x) {0x};
\node[state] at (2,-2) (1x) {1x};
% Edges %
\draw [->]
(S) edge[left] node{0} (0xF)
(S) edge[left] node{1} (1xF)
(0xF) edge[above] node{1} (0x)
(0xF) edge[loop above] node{0} (0xF)
(1xF) edge[below] node{0} (1x)
(1xF) edge[loop below] node{1} (1xF)
(0x) edge[bend left, below] node{0} (0xF)
(0x) edge[loop right] node{1} (0x)
(1x) edge[bend right, above] node{1} (1xF)
(1x) edge[loop right] node{0} (1x);
\end{tikzpicture}
\caption{DFA given by \hyperref[tab:nfa]{NFA State Table}}
\end{figure}
\section{Set of strings}
\begin{center} $\{10^n10^n | n \geq 1\}^*$ \end{center}
The given expression yields strings that start with $1$ and end with $0$. The initial $1$ is followed by $n$ $0's$ where $n \in N$. Those $0's$ are then followed by a $1$ which is then followed by another $n$ $0's$. The $^*$ at the end of the set implies that the string maybe empty or have multiple variations of $n$ concatenated together.
The set of strings less than or equal to length of 10 is $\{\epsilon, 10^{1}10^{1}, 10^{2}10^{2}, 10^{3}10^{3}, 10^{4}10^{4}, 1010100100\}$. Hence, six strings are in the set with length $\leq 10$. Note that the empty string is in the set and so is a combination of the second and third string in the set ($n=1,2$). Both are possible due to the presence of the $^*$ in the expression.
\section{Interweaving}
\begin{center}
$S = \{10^{n}10^{n+1}|n \geq 1\}$
\\
$10S^{*} \cap S^{*}10^{*} =$ ??
\end{center}
Therefore, $S^{*} = \{\epsilon, 10^{1}10^{2}, 10^{2}10^{3}, 10^{3}10^{4}, 10^{4}10^{5}, 10^{5}10^{6}, ..\}$ and any number of concatenations of the elements.
\\
The string must start with a $10$ due to the left part. The right part forces us to complete $S^*$ adding $10^{2}$ to the end. The left part then forces us to add $10^{3}$ to complete its $S^*$. This is an acceptable string of the given conjunction. However, it can be extended by adding $10^{4}$ and $10^{5}$, in which case ($10^{1}10^{2}10^{3}10^{4}10^{5}$), the $S^*$ on the left consists of $10^{2}10^{3}10^{4}10^{5}$ while the $S^*$ on the right consists of $10^{1}10^{2}10^{3}10^{4}$. Lastly, as $S^*$ can also be empty, the following strings are also included in the conjunction: $\{101\}$. Hence, the conjunction ($10S^{*} \cap S^{*}10^{*}$) contains the following strings,
\begin{center}
$\{101, 1010^{2}10^{3}, 1010^{2}10^{3}10^{4}10^{5}, 1010^{2}10^{3}10^{4}10^{5}10^{6}10^{7}, \cdots\}$
\end{center}
\paragraph{}
\small Note that there must be an odd number of $0$ blocks as either side of the conjunction requires at least one block of $0's$ along with $S^*$ which is made of an even number of blocks of $0$.
\section{Expression Formation}
Given $S_1 = \{ 10^{n}10^{n+1} | n \geq 1 \}$ and $S_2 = \{ 10^{n}10^{2n} | n \geq 1 \}$ and the following union:
\begin{center}
$S = \{1010^{2}10^{3}10^{6}10^{7}10^{14}\cdots10^{2^{n+1}-1} | n \geq 1 \}$ \\
$\cup$ \\
$\{1010^{2}10^{3}10^{6}10^{7}10^{14}\cdots10^{2^{n+2}-2} | n \geq 1 \}$
\end{center}
Hence, \\
When $n=1$, $S = \{1010^{2}10^{3}, 1010^{2}10^{3}10^{6}\}$.\\ When $n=2$, $S = \{1010^{2}10^{3}10^{6}10^{7}, 1010^{2}10^{3}10^{6}10^{7}10^{14}\}$ \\
As the length of the strings is increasing, $S$ can simply be written as $S_2S_1(S_2S_1)^*$
\paragraph{}
The $S_2$ takes care of the doubling (which occurs first, whenever there is an odd block of $0's$) and the $S_1$ takes care of the increment (which occurs second, whenever there is an even block of $0's$). The $S_2$ and $S_1$ not in the brackets force the exclusion of the empty string $\epsilon$. The $()^*$ assures that the sequence can be repeated multiple times, but in that order (of $S_2S_1$).
\paragraph{}
\small Note that since a part of the previous $S_1$ will be a part of the consecutive $S_2$, $n$ must strictly be increasing and the following pattern for the blocks of $0's$ will appear - double, increment, double, increment, $\cdots$.
Hence, a sequence such as $1010^{2}10^{3}1010^{2}10^{3}$ is not possible as the first $10^{3}$ fixes $n$ to $3$ making the next term $10^{6}$ (and the subsequent term to $10^{7}$ resulting in $1010^{2}10^{3}10^{6}10^{7}$). Remember that $S_2$ is followed before $S_1$.
\end{document}