\documentclass[10pt]{article}

\usepackage[margin=1in]{geometry}
\usepackage[small]{titlesec}
\usepackage{palatino, mathpazo}
\usepackage{inconsolata}
\usepackage{amsmath, amssymb}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage[normalem]{ulem}
\usepackage[mathscr]{euscript}
\usepackage{inconsolata}
\usepackage{tikz}

\newcommand{\ds}{\displaystyle}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\FF}{\mathscr{F}}
\newcommand{\GG}{\mathscr{G}}
\newcommand{\LL}{\mathscr{L}}
\newcommand{\SSS}{\mathscr{S}}
\newcommand{\CC}{\mathscr{C}}
\newcommand{\ttt}{\texttt}
\newcommand{\Length}{\ttt{Length}}
\newcommand{\MS}{\ttt{MixedShuffle}}



\setlength{\parindent}{0pt}
\setlength{\parskip}{1.5ex}

\title{\sc Math 4931 / 5931 -- Special Topics: Theory of Computation and Formal Languages\\[10pt]Homework 4}
\author{
	Spring 2023\\[10pt]
	due \sout{Friday, March 31} Monday, April 3, \underline{by the beginning of class}
}
\date{}
\begin{document}
\maketitle

\begin{center} 
	\emph{This homework assignment was written in \LaTeX{}. You can find the source code on the course website.}
\end{center}

\textbf{\underline{You must explain your reasoning for all of your answers. Correct answers with no justification or}\\[5pt]\underline{explanation will not be accepted.}}

\textbf{Students enrolled in Math 4931: Complete any 6 out of the 9 problems.}\\
\textbf{Students enrolled in MSSC 5931: Complete any 7 out of the 9 problems.}\\

\begin{enumerate}

	\item Prove that the language $\{a^nb^mc^k : n,m,k \geq 0\text{ and }n+m=k\}$ over the alphabet $\{a,b,c\}$ is not regular.

	\item Let $N_\ell(w)$ denote the number of occurrences of the letter $\ell$ in the word $w$. In Homework 3 we proved that the language
	\[
		\{xy : x,y \in \{0,1\}^*\text{ and }N_0(x) = N_1(y)\}
	\]
	is regular. In this exercise, let $\Sigma = \{0, 1, \#\}$ and prove that
	\[
		\{x\#y : x,y \in \{0,1\}^*\text{ and }N_0(x) = N_1(y)\}
	\]
	is not regular.

	\item Using the notation from Exercise 2, prove that the related language
	\[
		\{xy : x,y \in \{0,1\}^*\text{ and }N_0(x) = N_1(y) \text{ and }N_0(y) = N_1(x)\}
	\]
	is also not regular!

	\item Let $\Sigma = \{A, B, C, \ldots, Z\}$ and define $\mathcal{P}$ to be the set of palindromes in $\Sigma^*$. Formally,
	\[
		\mathcal{P} = \{w \in \Sigma^* : w = w^R\}.
	\]
	Prove that $\mathcal{P}$ is not regular.
	
	\item Prove that the single-letter language $\{\ell^i : i\text{ is prime}\}$ is not regular.
\end{enumerate}
	
\hrulefill

\textbf{Note:} For the four questions below, you can use Maple, the WolframAlpha website, or any other computer tool to compute the inverse of matrices. For other steps, be sure to show your work.

\begin{enumerate}
	\setcounter{enumi}{5}
		
	\item Let $R$ be the regular expression $(ab^+)^*$ and let $\LL = \{w : w \not \in L(R)\}$ (another way to put this is $\LL = \overline{L(R)}$, the complement of $L(R)$). Let $(a_n)_{n \in \N}$ be the counting sequence for the number of words in $\LL$ of each length. Find the generating function for $(a_n)_{n \in \N}$.


	\item Let $p_n$ be the number of permutations $\pi$ of length $n$ such that $\pi(i) - i \in \{-2, -1, 0, 1, 2\}$ for all $i = 1,2,\ldots,n$. Find the generating function for the counting sequence $(p_n)_{n \in \N}$.
	
	\item Let $t_n$ be the number of ways to tile a $1 \times n$ board with the tiles below:
	\begin{center}
	\begin{tikzpicture}
		\draw[dashed] (0.01,0.01) rectangle (1,1);
		\draw[fill] (0,0) -- (1,0) -- (0,1) -- cycle;
	\end{tikzpicture}
	\qquad
	\begin{tikzpicture}
		\draw[dashed] (0.01,0.01) rectangle (1,1);
		\draw[fill] (0,0) -- (1,1) -- (1,0) -- cycle;
	\end{tikzpicture}
	\qquad
	\begin{tikzpicture}
		\draw[dashed] (0.01,0.01) rectangle (1,1);
		\draw[fill] (0,0) -- (1,1) -- (0,1) -- cycle;
	\end{tikzpicture}
	\qquad
	\begin{tikzpicture}
		\draw[dashed] (0.01,0.01) rectangle (1,1);
		\draw[fill] (1,1) -- (1,0) -- (0,1) -- cycle;
	\end{tikzpicture}
	\qquad
	\begin{tikzpicture}
		\draw[dashed] (0.01,0.01) rectangle (2,1);
		\draw[fill] (0,0) -- (1,1) -- (2,1) -- (1,0) -- cycle;
		\draw[white, thick, dashed] (1,0) -- (1,1);
	\end{tikzpicture}
	\qquad
	\begin{tikzpicture}
		\draw[dashed] (0.01,0.01) rectangle (2,1);
		\draw[fill] (0,1) -- (1,1) -- (2,0) -- (1,0) -- cycle;
		\draw[white, thick, dashed] (1,0) -- (1,1);
	\end{tikzpicture}
	\qquad
	\begin{tikzpicture}
		\draw[fill] (0,0) rectangle (1,1);
	\end{tikzpicture}
	\end{center}
	The first four are triangles filling up half of a $1 \times 1$ squares. The second two are parallelograms taking up half of one square and half of the next. The last tile is a $1 \times 1$ square. First compute $t_0$, $t_1$ and $t_2$ by hand. Then find the generating function for the counting sequence $(t_n)_{n \in \N}$.
	
	

	\item Let $d_n$ be the number of ways to tile a $3 \times n$ board with domino ($1 \times 2$) tiles that can be vertical or horizontal. First compute $d_0$, $d_1$, and $d_2$ by hand. Find the generating function for the counting sequence $(d_n)_{n \in \N}$.
	
\end{enumerate}
\end{document}


