\documentclass[12pt]{article}

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

\newcommand{\es}{\emptyset}

\begin{document}

\newif{\ifshowsoln}
\showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks.

\centerline{\bf Homework 4 Morally Due Feb 26}

%\centerline{\bf THIS HOMEWORK IS TWO PAGES LONG!!!!!!!!!!!!!!!}

\begin{enumerate}
\item
(40 points)
Recall that a B-NFA is an NFA where we
say that an INFINITE string is accepted if there is SOME way
to process it where it hits a final state infinitely often.
Give an algorithm for the following: given a B-NFA $M$, determine
if there exists an infinite string that it accepts.


\item
(30 points)
The alphabet is $\{a,b\}$.
Give a B-NFA for the following languages

\begin{enumerate}
\item
(15 points)
\[\{ w \in \{a,b\}^\omega \mid w \hbox{ has an infinite number of $a$'s } \}\]
\item
(15 points)
\[\{ w \in \{a,b\}^\omega \mid w \hbox{ has a finite number of $a$'s } \}\]
\item
(0 points)
Think about: For the above languages ponder if they could be done by a B-DFA which
is a DFA where we say an infinite string accepts if it hits some final state infinitely often.
\end{enumerate}


\item
(30 points)
The alphabet is $\{a,b\}$.
Recall that $n_a(w)$ is the number of $a$'s in $w$.
\begin{enumerate}
\item
(10 points)
Give a regular expression for

$$\{ w \mid n_a(w) \equiv 0 \pmod 3 \}$$

\item
(10 points)
Give a regular expression for

$$\{ w \mid n_a(w) \equiv 1 \pmod 3 \}$$

\item
(10 points)
For all $x,y$  with $0<x<y$, 
give a regular expression for

$$\{ w \mid n_a(w) \equiv x \pmod y \}$$
\end{enumerate}

\end{enumerate}
\end{document}