Problem Set 1 latex source
This file has been stripped of comments and some formatting for clarity.
It is provided to help students create their solutions in latex if they wish.
It is missing some macros, but you can figure out what they are by looking
at the pdf image. It isn't intended to be a working latex file.
\usepackage{amsmath}
\newcommand{\set}[1]{\{#1|\ }
\newcommand{\setb}[1]{\{\brk{#1}| \ }
\newcommand{\setend}{\ensuremath{\}}}
\newcommand{\st}[1]{\mbox{\texttt{#1}}}
\newcommand{\mst}[1]{{\mathtt{#1}}}
\newcommand{\lang}[1]{\ensuremath{\text{\textit{#1}}}}
\newcommand{\defin}[1]{\textit{\textbf{{\boldmath #1}}}}
\item
\newcommand{\domino}[2]{\genfrac{[}{]}{0pt}{1}{\,\mst{#1}\,}{\,\mst{#2}\,}}
Let $\Sigma_2= \left \{\domino00, \domino01, \domino10, \domino11 \right\}.$ \
Here, $\SS_2$ contains all columns of \st{0}s and \st{1}s of height two.
A~string of symbols in $\SS_2$ gives two rows of \st{0}s and \st{1}s.
Consider each row to be a binary number and let
$$T= \set{w\in \Sigma_2\kstar}\text{the top row of $w$
is three times the bottom row}\setend.$$
For example,
$ \domino00 \domino01 \domino11 \domino00 \in T$,
but $\domino01 \domino01 \domino10 \not\in T.$
Show that $T$ is regular.
\item
Let $A$ be any language over an alphabet $\SS$.
Define $\lang{ADD-ONE}(A)$ to be the language
containing all strings that can be obtained by adding
a symbol in $\SS$ anywhere to a string in $A$. \\
Thus, $\lang{ADD-ONE}(A)=\set{xay} xy\in A$ where
$x,y \in \SSS, a\in \SS$\setend. \\
Show that the class of regular languages is closed under
the $\lang{ADD-ONE}$ operation. \\
Give both a proof by picture and a more formal proof by construction
as in Theorem~1.47.
\item
For any regular expression $R$ and $k\ge0$, let $R^k$ be
$R$ self-concatenated $k$ times, $\smash{\underbrace{RR\cdots R}_k}$. \\
Let $\SS=\{\st0,\st1\}$.
\begin{enumerate}
\item Let $A=\set{\st0^ku\st1^k} k\ge1$ and $ u\in\SSS\setend$.
Show $A$ is regular.
\item Let $B=\set{\st0^ku\st1^k} k\ge1$ and $ u\in\st1\SSS\setend$.
Show $B$ is not regular.
\end{enumerate}
\item
String $w$ is a \defin{palindrome} if $w=w^\mathcal{R}$.
Let $\lang{NEP}$ be the language of all strings over $\SS=\{\st0,\st1\}$
that are \underline{not} even-length palindromes.
Prove that $\lang{NEP}$ is not a regular language.
\item
Let $\SS = \{\st0,\!\st1\}$. For $k\ge1$, let $E_k=\set{w}
|w| \ge k$ and the $k$th symbol from the end of $w$ is~a~\st1\setend.
Here, $|w|$ means the length of $w$.
\begin{enumerate}
\item Given $k$, describe a regular expression for $E_k$.
You may use the exponentation notation given in problem 4.
\item Given $k$, describe an \nfa\ with $k+1$ states for $E_k$,
with a picture and a formal description.
\item Prove that for each $k$, no \dfa\ can recognize $E_k$
with fewer than $2^k$ states.
\end{enumerate}
\item
\begin{enumerate}
\item Use \cfgs\ to show that the class of \cfls\ is closed under union.
\item Let $E=\{\st{a}^i\st{b}^j|\ i \neq j$ and $2i \neq j\}$.
Use part (a) to show that $E$ is a context-free language. \\
(Hint: Express $E$ in a different way.)
\end{enumerate}
\item[$7.^{\!\star}$] ($\star$ = optional)
Let $M=(Q,\Sigma,\delta,q_0,F)$ be a \dfa\ and let $b$
be a state of $M$ called its ``base''. A \defin{reset string}
for $M$ and $b$ is a string $s \in \Sigma\kstar$ where $\delta(q, s) = b$
for every $q \in Q$. (Here we have extended $\delta$ to strings, so that
$\delta(q,s)$ equals the state where $M$ ends up when $M$ starts at state
$q$ and reads input $s$.) Say that $M$ is \defin{resettable} if it
has a reset string for some state~$b$. Prove that if $M$ is
a $k$-state resettable \dfa, then it has a reset string
of length at most $k^3$. (Note: I believe it is unknown whether
the bound can be improved to $o(k^3)$.)