
\documentclass{article}
\usepackage{amsmath,amssymb}
\usepackage[top=1in, bottom=1in, left=1in, right=1in]{geometry}
\usepackage{latexsym}

\begin{document}
\title{ CSCE 428/828 Homework 1}
\author{Name:    UID:  }
\date{month/data/year}
\maketitle


\vspace{10pt}

\textbf{1.35}. Let $\Sigma_{2} $ be the same as in Problem 1.33 ($\Sigma
_{2} =\{\left[ {{\begin{array}{*{20}c}
 0 \hfill \\
 0 \hfill \\
\end{array} }} \right],\left[ {{\begin{array}{*{20}c}
 0 \hfill \\
 1 \hfill \\
\end{array} }} \right],\left[ {{\begin{array}{*{20}c}
 1 \hfill \\
 0 \hfill \\
\end{array} }} \right],\left[ {{\begin{array}{*{20}c}
 1 \hfill \\
 1 \hfill \\
\end{array} }} \right]\})$. Consider the top and bottom rows to be strings
of 0s and 1s, and let

E$=$\textbraceleft $\omega \in \Sigma_{2}^{\ast } $ \textbar the bottom row
of $\omega $ is the reverse of the top row of $\omega $\textbraceright.
Show that E is not regular.

\vspace{30pt}

\textbf{1.46c.} Prove that the following language is not regular. You may
use the pumping lemma and the closure of the regular languages under union,
intersection, and complement.

\textbraceleft $\omega \vert \omega \in \{0,1\}^{\ast }$ \textbar is not a
palindrome\textbraceright 
\vspace{30pt}

\textbf{1.53.} Let $\Sigma =\{0,1,+,=\}$ and
\par
 $ADD =$ \textbraceleft x$=$y$+$z \textbar x,y,z are binary integers, and x
is the sum of y and z \textbraceright.\par
Show that \textit{ADD} is not regular.
\vspace{30pt}

\textbf{1.55.} The pumping lemma says that every regular language has a
pumping length p, such that every string in the language can be pumped if it
has length p or more. If p is a pumping length for language A. so is any
length $p^{,} \geq p$. The \textbf{\textit{minimum pumping length}} for
A is the smallest p that is a pumping length for A. For example, if
A$=$01$^{\ast }$, the minimum pumping length is 2. The reason is that the
string s$=$0 is in A and has length 1 yet s cannot be pumped; but any string
in A of length 2 or more contains a 1 and hence can be pumped by dividing it so
that x$=$0, y$=$1, and z is the rest. For each of the following languages,
give the minimum pumping length and justify your answer.

\textbf{c.} $001\cup 0^{\ast }1^{\ast }$

\textbf{e. }$(01)^{\ast }$

\textbf{h.} $10(11^{\ast }0)^{\ast }0$
\vspace{30pt}

1\textbf{.62.} let$\Sigma =\{a,b\}$. For each $k\geq 1$, let
$D_{k}$ be the language consisting of all strings that have at
least one a among the last k symbols. Thus $D_{k}=\Sigma^{\ast }a(\Sigma\cup\varepsilon)^{k-1 }$. Describe a
\textbf{DFA} with at most k$+$1 states that recognizes $D_{k}$
in terms of both a state diagram and a formal description.
\vspace{30pt}

\textbf{1.63a.} Let A be an infinite regular language. Prove that A can be
split into two infinite disjoint regular subsets.
\vspace{30pt}

\textbf{1.71a.} Let$\Sigma =\{0,1\}$.

Let $A = \{0^{k}u0^{k}|k\geq 1 \mbox{ and } u \in \Sigma^{\ast} \}$ Show that A is regular.
\vspace{30pt}

\textbf{1.72b.} Let M$_{1}$ and M$_{2\, }$be \textbf{DFA}s that have $k_{1}$
and $k_{2}$ states, respectively, and then let $U=L(M_{1})\cup L(M_{1})$.

Show that if $U \neq \Sigma^{\ast}$, the $U$ excludes some
string$s$, where $|s| < k_{1}k_{2} $.

\end{document}
