\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{comment} 

\newcommand{\IS}{{\rm ISAAC}}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\Ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}

\newcommand{\goes}{\rightarrow}
\newcommand{\nth}{n^{th}}
\newcommand{\N}{\sf{N}}
\newcommand{\Q}{\sf{Q}}
\newcommand{\R}{\sf{R}}
\newcommand{\C}{\sf{C}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\es}{\emptyset}
\newcommand{\st}{\mathrel{:}}
\newcommand{\e}{\varepsilon}
\usepackage{tikz}
\usetikzlibrary{automata,positioning,arrows}

\begin{document}

\centerline{\bf Homework 5 Morally Due March 5 at 3:30PM}

\begin{enumerate}
\item
(0 points, but if you actually miss the midterm without telling Dr. Gasarch ahead of time, you will lose 100 points on this homework)
When will the midterm be (give date and time)?

\newpage


\item 
(30 points) 
Assume $n$ is a power of 2 and $n\ge 32$. 
Give a Context Free Grammar in Chomsky Normal Form for 

$$L_1=\{ a^{n/4} b^{n/4} a^{n/4} b^{n/4} \}.$$

You may use DOT DOT DOT

How many rules does it take? Do you think this is optimal? 
Try to get the number of rules somewhat exact (okay if off by $O(1)$). 

{\bf Advice:} First get a grammar that is not in Chomsky Normal Form for $L$.
Then discuss how each rule can be put into Chomsky Normal Form and
see how many rules it is. 

{\bf What you can use:} You can use that, for any symbol $\sigma$,
There is a Chomsky Normal Form grammar for $\{ \sigma^n\}$ that
uses $\lg(n)$ rules. 

\newpage

\item 
(30 points) 
Give a Context Free Grammar for $L=\overline{ \{ a^n b^n c^n \st n\in \N \}}$.
(Hint: Write $L$ as a union of several languages. 
For each one such language either show it is regular or give a context free
grammar for it. Then you are DONE since (a) if $L$ is regular it is a CFL, and
(b) the set of CFL's are closed under union.)


\newpage 

\item 
(40 points)
The alphabet is $\{a,b\}$. 
Let $n\in\N$. Assume $n$ is a power of 2. 
Consider the language 

$$L = \biggl \{  w \st |w|=n \wedge \#_a(w)=\frac{n}{2} \biggr \}.$$

(Strings of length $n$ such that exactly $\frac{n}{2}$ of the symbols are $a$.) 

\begin{enumerate}
\item
(15 points) 
Describe a DFA for $L$ by using a transition table.
You CANNOT use DOT DOT DOT. 
How many states does it have (you can use big-O notation). 
Do you think there is a smaller DFA for $L$? 


\item 
(15 points) 
Give a regular expression for $L$. You CAN use DOT DOT DOT.
How long is it (you can use big-O notation). 
(We use the usual convention of not counting UNION signs or PARENTHESIS
for length.) 
Do you think there is a shorter regular expression for $L$? 


\item 
(10 points) 
Give a Context Free Grammar in Chomsky Normal Form for  $L$. You CAN use DOT DOT DOT.
How many rules are in it? (you can use big-O notation). 
Do you think there is a smaller CFG in CNG for $L$? \\
(Note: You may use the theorem that Bill either proved or meant-to-prove that for a string $w$ of length $n$ there is a CFG in CNF of size $O(n)$ for $\{w\}$.)



\end{enumerate} 


\end{enumerate} 

\end{document}