\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{times}
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\usepackage{enumerate}
\usepackage[usenames]{color} 
\usepackage[pst-pdf=md5]{gastex}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{claim}{Claim}
\newtheorem{definition}{Definition}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\mfr}[1]{\mathfrak{#1}}
\newcommand{\mcal}[1]{\mathcal{#1}}
\newcommand{\pow}[1]{\mathcal{P}(#1)}

\newcommand{\ignore}[1]{}
\newcommand{\mybox}{\fbox}

\newcommand{\bzero}{\mathbf{0}}
\newcommand{\bone}{\mathbf{1}}
\newcommand{\vpi}{\varphi}
\newcommand{\scl}[1]{{#1}^{\star}}
\newcommand{\ab}{\{a,b\}^{\star}}
\newcommand{\abc}{\{a,b,c\}^{\star}}
\newcommand{\abcd}{\{a,b,c,d\}^{\star}}
\newcommand{\zo}{\{0,1\}^{\star}}
\newcommand{\sstar}{\Sigma^{\star}}

\newcommand{\bl}{\mathbf{a}}
\newcommand{\bc}{\mathbf{c}}
\newcommand{\bv}{\mathbf{v}}
\newcommand{\bd}{\mathbf{d}}
\newcommand{\be}{\mathbf{e}}
\newcommand{\bo}{\mathbf{o}}

\DeclareMathOperator{\suff}{Suffix}


\begin{document}

\par\noindent{\bf CS81 HW\#8 Spring 2012} {\em Out: 03/29/2012. Due: 04/04/2012 (before class)}
\paragraph{Policy on homeworks}
\begin{itemize}
\item {\em Collaboration}:
        You may discuss a question with any other student currently taking CS81 provided:
        (i) both of you contribute equally;
        (ii) you come away from any discussion with an understanding in your mind (and no archived solution of any form is retained);
        (iii) your submission is your own work prepared by yourself on a separate occassion.

\item {\em Reference materials}:
        You should only refer to materials from this semester of CS81
        (class notes, handouts, textbooks, grutors, instructor, etc).

\item {\em Submission}:
        Your submission should be legible or is prepared using TeX.
\end{itemize}

\vspace{.1in}

\par\noindent
Consider the following requirements for ``safe'' passwords. Assume that the alphabet
consists of numeric and lower-case alphabetical ASCII letters.
For each description (or requirement), decide if it is regular, context-free or neither. 
Mark each question with {\bf REG} (for regular),
{\bf CFL} (for context-free but not regular) and {\bf NON} (for not context-free).

\vspace{.1in}

\par\noindent
Provide justifications for your answers separately:
\begin{itemize}
\item if {\bf REG}, show either a finite automata or a regular expression.
\item if {\bf CFL}, show both a context-free grammar and a proof of non-regularity.
\item if {\bf NON}, show a proof of not being context-free.
\end{itemize}

\vspace{.1in}

\par\noindent
Let $\Sigma = \bd \cup \bl$, where $\bd = \{0,\ldots,9\}$ and $\bl = \{a,\ldots,z\}$. 
\begin{enumerate}
\item The password must be at least $8$ characters long.

\item The password must contain at least $3$ digits and at least $5$ letters.

\item The password must contain two non-overlapping palindromes.

\item The password must contain the same number of digits and letters.

\item The password must contain the same number of digits, vowels and consonants.

\item The password has letters followed by digits where the number of letters should be no more than 
	the number of digits, but the number of digits should be no more than twice the number of letters.

\item If the password contains a vowel, then it has to have the same number of even digits,
	odd digits, and consonants; otherwise, it may contain any number of even digits, odd digits, and consonants.

\item The length of the password must be a square.

\end{enumerate}

\end{document}

