\documentclass[11pt]{article}
\usepackage{fullpage,amsmath,hyperref}
\newcommand{\eps}{\varepsilon}
\begin{document}
\begin{center}\Large\bf
CS/ECE 374 A (Spring 2024)\\
{\Large Homework 4} (due Feb 15 Thursday at 10am)
\end{center}
\medskip\noindent
{\bf Instructions:} As in previous homeworks.
\begin{description}
\bigskip
\item[Problem 4.1:]
For each of the following languages, determine whether it is regular or not, and give a proof. To prove that a language is not regular, you should use the fooling set method. (To prove that a language is regular, you are allowed to use known facts about regular languages, e.g., closure properties, all finite languages are regular, \ldots)
\begin{enumerate}
\item[(a)] $\{0^i 1^j 0^k: \mbox{$j$ is divisible by $i+k$, and $i+j+k$ is divisible by $4$, and $i,j,k\ge 5$}\}$.
\item[(b)] $\{xx^R0x: x\in \{0,1\}^*\}$ (where $x^R$ denotes the reverse of $x$).
\item[(c)] All strings $x\in\{0,1\}^*$ such that $x$ ends in a palindrome of length between 4 and 374.
\item[(d)] All strings $x\in\{0,1\}^*$ such that $x$ ends in a palindrome of length at least 374.
\end{enumerate}
\bigskip
\item[Problem 4.2:]
Give a context-free grammar (CFG)
for each of the following languages.
You must provide explanation for how
your grammar works, by describing in English what is generated by
each non-terminal. (Formal proofs of correctness are not required.)
\begin{enumerate}
\item[(a)] All strings $x\in\{0,1\}^*$ such that $x$ ends in a palindrome of length at least 4.
\item[(b)] All strings $w=x0^iy$ where $x,y\in\{0,1\}^*$ and $i\ge \frac{2|w|}{3}$.
\item[(c)] $\{0^i 1^j 0^k: \mbox{$k\ge2i$ and $i+j+k$ is divisible by 4}\}$.
\end{enumerate}
\end{description}
\end{document}