diff options
Diffstat (limited to 'Homework/cs5000/hw04/hw04.tex')
| -rw-r--r-- | Homework/cs5000/hw04/hw04.tex | 146 |
1 files changed, 146 insertions, 0 deletions
diff --git a/Homework/cs5000/hw04/hw04.tex b/Homework/cs5000/hw04/hw04.tex new file mode 100644 index 0000000..9aa70a1 --- /dev/null +++ b/Homework/cs5000/hw04/hw04.tex @@ -0,0 +1,146 @@ +% Created 2023-09-27 Wed 14:13 +% Intended LaTeX compiler: pdflatex +\documentclass[11pt]{article} +\usepackage[utf8]{inputenc} +\usepackage[T1]{fontenc} +\usepackage{graphicx} +\usepackage{longtable} +\usepackage{wrapfig} +\usepackage{rotating} +\usepackage[normalem]{ulem} +\usepackage{amsmath} +\usepackage{amssymb} +\usepackage{capt-of} +\usepackage{hyperref} +\notindent \notag \usepackage{amsmath} \usepackage[a4paper,margin=1in,portrait]{geometry} +\author{Elizabeth Hunt} +\date{\today} +\title{HW 04} +\hypersetup{ + pdfauthor={Elizabeth Hunt}, + pdftitle={HW 04}, + pdfkeywords={}, + pdfsubject={}, + pdfcreator={Emacs 28.2 (Org mode 9.7-pre)}, + pdflang={English}} +\begin{document} + +\maketitle +\setlength\parindent{20pt} + +\section{Question One} +\label{sec:org1166362} +Consider the regular language \(L\) over \(\Sigma = \{0,1,2\}\) such that \(L = \{x^{\star} | x \in \Sigma\}\) +, then \(L\) is a language; its members being all possible combinations of any length of all +\(x \in \Sigma\). + +\(L\) is a \uline{regular} language since there is a FA to describe it: + +\begin{itemize} +\item \(F = \{q_0\}\) +\item \(\Sigma = \{0,1,2\}\) +\item \(S = q_0\) +\item \(\delta(q_0, 0) = q_0\), \(\delta(q_0, 1) = q_0\), \(\delta(q_0, 2) = q_0\) +\item \(Q = {q_0}\) +\end{itemize} + +Let a set of languages \(G\) exist such that \(G_1 = \{0^i 1^i | i \geq 0\}\), \(G_2 = \{(0^i 1^i)(0^i 1^i) | i \geq 0\}\) +\(\cdots\) \(G_n = \{(0^i 1^i)^n | i \geq 0\}\). \(G_1\) is irregular by the proof found in Lecture 5. Then we assume that +\(G_k\) is irregular. If so, we can show \(G_{k+1}\) is irregular because we can only construct a FA to recognize +\(G_{k+1}\) if and only if we can concatenate a FA recognizing \(G_k\) in an epsilon transition with another FA recognizing \(G_1\); which is +not existant. By induction, any such \(G_i | i \in \mathds{N}\) is irregular. + +Each \(G\) is also a proper sublanguage since for each \(i \in \mathds{N}\) we can construct \((01)^{i+1}\) +which is not in \(G_i\) but in \(L\), so \(\nexist x \in G | x = L\). For extra clarity we know every string in \(G_i\) is +also in \(L\) since \(L\) is really the Kleene Closure. + +Thus there are at least \(\aleph_0\) infinitely many such non-regular proper sublanguages of the regular language \(L\). + +\section{Question Two} +\label{sec:orgf857515} +\subsection{One (adapted from slide notes in Lecture 5)} +\label{sec:org606e4e3} +Consider a minimal DFA \(M\) that recognizes \(L\); \(L = L(M)\) with \(k\) states. + +Then consider the string \(a^k b^k c^k\); to first recognize \(a^k\) we go through \(k+1\) states, so we can +find a loop in the path taken via \(\delta\) such that there exists \(q = \delta^{\star}(q, a^i) | i > 0\). + +If we pump this loop zero times, then for the string \(a^j b^k c^k\), \(j < k\); for one or more times, +\(j > k\); thus \(j < k\) or \(j > k\) but \(j \neq k\), a contradiction from the original definition. + +\subsection{Two} +\label{sec:org6221b61} + +Any string in this language is an even number of \(a\)'s, recognized by this FA (thus, is a regular language). + +\begin{itemize} +\item \(F = \{q_0\}\) +\item \(\Sigma = \{a\}\) +\item \(S = q_0\) +\item \(\delta(q_0, a) = q_1, \delta(q_1, a) = q_0\) +\item \(Q = \{q_0, q_1\}\) +\end{itemize} + +\subsection{Three} +\label{sec:org4423d9f} +Consider a minimal DFA \(M\) that recognizes \(L\); \(L = L(M)\) with \(k\) states. By the pumping lemma +each string \(x \in L\) such that \(|x| \geq k\) is of the form \(uvw\) with \(|uv| \leq k\), \(|v| \geq 1\) and +\(uv^i w \in L \forall i \geq 0\). + +For any such \(k\) we create the string \(a^k c a^k \in L\), and because \(|uv| \leq k\) then \(uv\) matches at most +\(a^k\). So, \(u = a^m, v = a^n\) with \(m + n \leq k\), and thus \(w = a^{k - (m+n)} c a^k\). Additionally, since \(|v| \geq 1\), +\(n \ge 1\). + +By pumping \(v\) zero times we then have \(a^m a^{k-(m+n)}c a^k = a^{k-n} c a^k \notin L\) as \(n \geq 1\) so \(L\) must be irregular. + +\subsection{Four} +\label{sec:org719bada} +Consider a minimal DFA \(M\) that recognizes \(L\); \(L = L(M)\) with \(k\) states. By the pumping lemma +each string \(x \in L\) such that \(|x| \geq k\) is of the form \(uvw\) with \(|uv| \leq k\), \(|v| \geq 1\) and +\(uv^i w \in L \forall i \geq 0\). + +For any such \(k\) we create the string \(a^k c^k b^{2k} \in L\) and because \(|uv| \leq k\) then \(uv\) matches at most +\(a^k\). So, \(u = a^m, v = a^n\) with \(m + n \leq k\), and since \(|v| \geq 1\), \(n \ge 1\) thus \(w = a^{k - (m+n)} c^k b^{2k}\). +Additionally, since \(|v| \geq 1\), \(n \ge 1\). + +By pumping \(v\) zero times we then obtain \(a^m a^{k-(m+n)} c^k b^2k = a^{k-n} c^k b^{2k}\) but then \(k-n + k \neq 2k\) as +\(n \geq 1\), a contradiction; \(L\) is irregular. + +\subsection{Five} +\label{sec:org9f5d6ff} +Consider a minimal DFA \(M\) that recognizes \(L\); \(L = L(M)\) with \(k\) states. By the pumping lemma +each string \(x \in L\) such that \(|x| \geq k\) is of the form \(uvw\) with \(|uv| \leq k\), \(|v| \geq 1\) and +\(uv^i w \in L \forall i \geq 0\). + +For any such \(k\) we create the string \(0^k 1^{k-1} \in L\), and because \(|uv| \leq k\) then \(uv\) matches at most +\(0^k\). So, \(u = 0^m, v = 0^n\) with \(m + n \leq k\), thus \(w = 0^{k - (m+n)} 1^{k-1}\). Additionally, since \(|v| \geq 1\), \(n \ge 1\). + +By pumping \(v\) zero times we obtain the string \(0^m 0^{k-(m+n)} 1^{k-1} = 0^{k-n} 1^{k-1}\) and \(k-n\) cannot be greater than +\(k-1\), a contradiction; \(L\) is irregular. + +\section{Question Three} +\label{sec:org9247330} + +(pictorial draft) DFA + +\begin{center} +\includegraphics[width=200px]{./img/problem_3_dfa.png} +\end{center} + +And: + +\begin{itemize} +\item \(\Sigma = \{a, b\}\) +\item \(Q = \{q_0, q_1, q_2, q_3\}\) +\item \(F = \{q_2\}\) +\item \(S = q_0\) +\item \(\delta(q_0, a) = q_1\), \(\delta(q_0, b) = \emptyset\), \(\delta(q_1, a) = \emptyset\), \(\delta(q_1, b) = q_2\), \(\delta(q_2, a) = q_3\), \(\delta(q_2, a = q_1)\), +\(\delta(q_3, a) = q_2\), \(\delta(q_3, b) = \emptyset\) +\end{itemize} + +We can build a FA that recognizes strings in \(L(G)\), so it is regular. + +\section{Question Four} +\label{sec:org7d011c1} +\(G = (\{S\}, \{0,1,\cdots,9\}, S, \{S \rightarrow 0S | 1S | 2S | 3S | 4S | 5S | 6S | 7S | 8S | 9S | \epsilon\})\) +\end{document}
\ No newline at end of file |