\documentclass[11pt]{article}
\usepackage[letterpaper,margin=1in]{geometry}
\usepackage{amsmath,amsthm,amssymb,latexsym}
\usepackage{array,multirow,alltt,enumerate,bbm,eucal,graphicx}
\usepackage[colorlinks]{hyperref}
\usepackage{xcolor,stmaryrd,bussproofs,mathpartir}
\usepackage{tikz,pgfmath}
\usepgflibrary{shapes}
\usetikzlibrary{arrows,automata,backgrounds}

\setlength\parindent{0in}
\addtolength\parskip{1ex}
\setlength\fboxrule{.5mm}\setlength{\fboxsep}{1.2mm}
\newlength\courseheader
\courseheader=\textwidth
\addtolength\courseheader{-4mm}
\parindent=0pt
\parskip=1ex

%macro definitions

\newcommand\eps\varepsilon
\newcommand\Imp\Rightarrow
\renewcommand\hat\widehat
\newcommand\set[2]{\{#1\mid#2\}}
\newcommand\Iff\Leftrightarrow
\newcommand\Iffdef{\stackrel{\mathrm{def}}\Leftrightarrow}
\newcommand\rev{\mathop{\mathsf{rev}}}
\newcommand\floor[1]{\lfloor#1\rfloor}
\newcommand\len[1]{|#1|}
\newcommand\subs\subseteq
\newcommand\MM{\mathcal M}

%environment definitions

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}

\begin{document}

\begin{center}
\framebox{\parbox\courseheader{\large Introduction to Theory of Computing\hfill Homework 5\\ 
CS 4810/5810 Spring 2025\hfill Due Wednesday, 5 March 2025}}
\end{center}
\medskip

\pagestyle{empty}

\begin{enumerate}

\item
Give a CFG for the set of strings in $\{a,b\}^*$ that are \emph{not} palindromes.
Argue that your grammar is correct. You may use without proof the fact that a string of length $n$ is a palindrome (that is, $\rev x=x$) iff for all $k\le\floor{n/2}$, the $k$th symbols reading from the left and right ends agree.

\item
Consider the set
\begin{gather*}
E = \set{x\in\{a,b\}^*}{\#a(x) = \#b(x)},
\end{gather*}
the set of all strings in $\{a,b\}^*$ with equally many $a$'s and
$b$'s. Give a CFG for $E$ and prove that it generates exactly $E$.
(\emph{Hint}. To show that your grammar generates only strings in $E$,
use induction on the length of the derivation. To show that every
$x\in E$ is generated by your grammar, use induction on $\len x$.
Characterize elements $x\in E$ in terms of the graph of
the function $\#b(y) - \#a(y)$ as $y$ ranges over prefixes of $x$, as
we did in class with balanced parentheses.)

\item
A (\emph{strongly}) \emph{right-linear grammar} is a CFG in which all productions
are of the form $A\to aB$ or $A\to\eps$, where $A,B$ are nonterminals and $a$ is a terminal.
Prove that right-linear grammars generate exactly the regular sets, thus every regular set is a CFL.

\item
(For 5810 students.)
Prove that a set $R\subs\Sigma^*$ is regular if and only if there exists a finite monoid $\MM = (M,\cdot,1)$ and a monoid homomorphism $h:\Sigma^*\to\MM$ such that $R = h^{-1}(A) = \set{x\in\Sigma^*}{h(x)\in A}$ for some $A\subs M$.

\end{enumerate}

\end{document}
