\documentclass[11pt]{article}
\usepackage{fullpage,amsmath,hyperref,xcolor}
\newcommand{\eps}{\varepsilon}
\begin{document}
\begin{center}\Large\bf
CS/ECE 374 A (Spring 2024)\\
{\Large Homework 3} (due Feb 8 Thursday at 10am)
\end{center}
\medskip\noindent
{\bf Instructions:} As in previous homeworks.
\begin{description}
\bigskip
\item[Problem 3.1:]
For each of the following languages in parts (a), (b), and (c),
describe an NFA that accepts the language, using as few states as you can.
Provide a short explanation of your solution.
%Below, $\#_0(x)$ and $\#_1(x)$ denote the number of 0's and the number of 1's in $x$ respectively.
\begin{enumerate}
\item[(a)] (30 pts)
the language defined by the regular expression
$((01)^*+(10)^*) \cdot (11+00) \cdot \big( \epsilon+(11)^*0+(00)^*1 \big)^*$ over the alphabet $\{0,1\}$.
\item[(b)] (30 pts)
all strings $x\in\{0,1\}^*$ such that ($x$ has $1000$ as a substring) and (there exist two distinct indices $i$'s such that $i$th character of $x$ and the $(i+3)$rd character of~$x$ are different).
[{\em Note}: if $x$ has $1000$ as a substring, we already know that there is at least one such $i$ with the property, but we are asking for at least one more $i$ with the property.
For example, $1{\color{blue}1}01{\color{blue}0}0\underline{{\color{red}1}00\color{red}0}$ is in the language, and so is $0\underline{{\color{red} 1}0{\color{blue}0}{\color{red}0}}0{\color{blue}1}00$.]
\item[(c)] (10 pts)
all strings in $\{0,1\}^*$ that have at least two $1$'s and for some pair of two consecutive ones, have a block of $0$'s where the number of $0$'s is divisible by $3$.
In other words, the language defined by the regular expression $(0+1)^*\cdot 1\cdot (000)^* \cdot 1 \cdot (0+1)^*$.
\item[(d)] (30 pts)
Convert your NFA from part (c) to a DFA by using the subset construction (i.e., power set construction).
[{\em Note}: Don't include unreachable states; for full points your DFA should not have more than $10$ states.
It may be possible to collapse some states to reduce the number of states further, but you are not required to do so.]
\end{enumerate}
\bigskip
\item[Problem 3.2:] For $\Sigma=\{0,1,2\}$, given a string $y\in \Sigma^*$, let $y^{\textit{IL}_0}$ define a string where $0$ is inserted after every character of $y$. For example if $y=0121$ then $y^{\textit{IL}_0}=00102010$.
Given a language $L$ over the alphabet $\Sigma=\{0,1,2\}$,
define
\newcommand{\IL}{\textsc{Interleave}_0}
\[ \IL(L) = \{xy^{\textit{IL}_0}z:\ xyz\in L,\ x,y,z\in\Sigma^*\}.
\]
Prove that if $L$ is regular, then $\IL(L)$ is regular.
(For example, if $0100{\bf 101}0011\in L$, then
$0100{\bf 100010}0011\in \IL(L)$.)
(For a different example: $\IL(1^*) = 1^* \cdot (10)^* \cdot 1^*$.)
[{\em Hint}: given an NFA (or DFA) for $L$, construct an NFA for $\IL(L)$.
Give a formal description of your construction. Provide an explanation of
how your NFA works, including the meaning of each state. A formal proof
of correctness of your NFA is not required.]
\end{description}
\end{document}