\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}}


\usepackage{tikz}
\usetikzlibrary{automata}
\usetikzlibrary{positioning}

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

\title{\sc Math 4931 / 5931 -- Special Topics: Theory of Computation and Formal Languages\\[10pt]Homework 5}
\author{
	Spring 2023\\[10pt]
	due Friday, May 5, \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 4 out of the 7 problems.}\\
\textbf{Students enrolled in MSSC 5931: Complete any 5 out of the 7 problems.}\\

\begin{enumerate}

	\item Let $N_\ell(w)$ denote the number of occurrences of the letter $\ell$ in the word $w$. Consider the language
	\[
		\LL_1 = \{w\#0^{N_0(w)} : w \in \{0,1\}^*\}
	\]
	over the alphabet $\Sigma = \{0, 1, \#\}$. These are words that have a word $w$ over $\{0,1\}$, then a $\#$, then some $0$'s, and the number of $0$'s after $\#$ must match the number of $0$'s in $w$.
	
	Prove that $\LL_1$ is a context-free language by finding a CFG for it.
	
	\item Let $N_\ell(w)$ denote the number of occurrences of the letter $\ell$ in the word $w$. Consider the language
	\[
		\LL_2 = \{x \# y : x,y \in \{0,1\}^*\text{ and }N_0(x)=N_1(y)\}.
	\]
	
	Prove that $\LL_2$ is a context-free language by finding a CFG for it.
	
	
	\item Convert the CFG below into a CFG in Chomsky Normal Form that generates the same language:
	\begin{align*}
		A &\to BAB \;|\; B \;|\; \varepsilon\\
		B &\to 00 \;|\; \varepsilon
	\end{align*}
	
	\item Find a pushdown automata for the language $\LL_1$ in Exercise 1. Draw its diagram and also give its formal definition.

	\item Find a pushdown automata for the language $\LL_2$ in Exercise 2. Draw its diagram and also give its formal definition.
	
	\item Use the Myhill-Nerode Lemma (not the Pumping Lemma) to prove that the language
	\[
		\{ww : w \in \{a,b\}^*\}
	\]
	is not regular.

	\item Use Moore's Algorithm to find the minimal DFA that accepts the same language as the DFA below.
	
	\begin{center}
		\begin{tikzpicture}[%
			baseline=(current bounding box.center),%
	        thick, shorten >=1pt, shorten <=1pt, node distance=2cm,on grid,auto,%
			every state/.style={%
				draw={rgb:red,0;green,0;blue,0.6},%
				thick,%
				fill={rgb:red,0;green,0;blue,0.6},%
				fill opacity=0.1,
				text opacity=1
			}%
		]
			\node[state, initial, initial text={}] (0)   {$0$};
			\node[state] (1) [below left=1in and 0.5in of 0] {$1$}; 
			\node[state] (2) [right=1.2in of 0] {$2$};
			\node[state] (3) [below right=1in and 0.5in of 1] {$3$};
			\node[state] (5) [below right=1in and 0.6in of 0] {$5$};
			\node[state, accepting] (9) [below right=1in and 0.5in of 2] {$9$}; 
			\node[state, accepting] (7) [below right=1in and 0.5in of 9] {$7$};
			\node[state, accepting] (6) [right=1in of 7] {$6$};
			\node[state] (4) [below left=1in and 0.5in of 9] {$4$};
			\node[state, accepting] (8) [right=1in of 9] {$8$};
			\path[->] 
				(0) edge node[swap] {0} (1)
					edge node {1} (2)
				(1) edge node[swap] {0} (3)
					edge node[pos=0.2] {1} (4)
				(2) edge node[swap] {0} (5)
					edge node {1} (9)	
				(3) edge[loop left] node {0} (3)
					edge node[swap] {1} (4)
				(4) edge[bend left=10] node[pos=0.9] {0} (5)
					edge node[swap] {1} (9)
				(5) edge[bend left=10] node {1} (4)
					edge node[swap, pos=0.2] {0} (3)
				(6) edge[loop right] node {0} (6)
					edge node {1} (7)
				(7) edge[bend left=10] node {0} (8)
					edge node {1} (9)
				(8) edge node {0} (6)
					edge[bend left=10] node {1} (7)
				(9) edge node {0} (8)
					edge[loop above] node {1} (9)
				;
		\end{tikzpicture}
	\end{center}

	
		
\end{enumerate}
\end{document}


