\documentclass{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\}}
\newcommand{\sstar}{\Sigma^{\star}}

\newcommand{\derive}{\Rightarrow}
\newcommand{\dstar}{\stackrel*\Rightarrow}
\newcommand{\yield}{\vdash}

\newcommand{\bfa}{\mathbf{a}}


\begin{document}

\par\noindent{\bf CS81 HW\#9 Spring 2012} {\em Out: 04/05/2012. Due: 04/11/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}

\paragraph{Grammars}
\begin{enumerate}
\item Consider the following context-free grammar $G=(V,\Sigma,R,S)$, where
	$V = \{E,T,F\}$, $\Sigma = \{\bfa,\ast,(,)\}$, $S=E$, and rules $R$ defined as:
	\begin{eqnarray*}
	E & \to & E \ T \ | \ T \\
	T & \to & T \ast \ | \ F \\
	F & \to & ( \ E \ ) \ | \ \bfa
	\end{eqnarray*}
	\begin{enumerate}
	\item Draw a {\em pushdown automata} (PDA) for $L(G)$.
	\item Convert $G$ to {\em Chomsky Normal Form}. Show and explain your steps.
	\item Decide if $w \in L(G)$ for $w=\mathbf{a}\mbox{$\ast$}\mathbf{a}\mbox{$\ast$}\mathbf{a}$ 
		using the Cocke-Younger-Kasami (CYK) algorithm.
		If $w \in L(G)$, show how to recover the derivation $S \dstar w$ from the dynamic programming table.
	\item Convert $G$ to {\em Greibach Normal Form}. Show and explain your steps.
	\item Is $G$ an {\em ambiguous} grammar?
	\end{enumerate}

\item An unrestricted {\em grammar} is a $4$-tuple $G=(V,\Sigma,R,S)$ where $V$ is a finite set
	of variables, $\Sigma$ is a finite alphabet, $S$ is a start symbol, and 
	$R \subseteq (V \cup \Sigma)^{\star}V(V \cup \Sigma)^{\star} \times (V \cup \Sigma)^{\star}$
	is a set of rules.

	Consider the following grammar $G = (\{S,L,A,B,[,]\},\{a,b\},R,S)$ with the rules.
	\begin{eqnarray*}
	S & \to & L \mbox{ $]$} \\	
	L & \to & La \ | \ Lb \ | \ \mbox{$[$} \\
	\mbox{$[$ } a & \to & a \mbox{ $[$ } A \\
	\mbox{$[$ } b & \to & b \mbox{ $[$ } B \\
	A a & \to & a A \\
	A b & \to & b A \\
	B a & \to & a B \\
	B b & \to & b B \\
	A \mbox{ $]$} & \to & \mbox{ $]$ } a \\ 
	B \mbox{ $]$} & \to & \mbox{ $]$ } b \\
	\mbox{$[$ $]$} & \to & \epsilon
	\end{eqnarray*}
	\begin{enumerate}
	\item Determine if $L(G) = L$ where $L = \{ww : w \in \ab\}$ or not. \\
		If {\em yes}, explain carefully the rules of $G$ (their specific roles or purpose, etc.). \\
		If {\em not}, show a counterexample of either $w \not\in L$ (for which $S \dstar w$) 
		or $w \in L$ (for which $S \dstar w$ does not hold); and then, show how to fix $G$ so it generates $L$. 

	\item Adapt $G$ to obtain a grammar for $L = \{www: w \in \ab\}$. Explain your rules carefully.

	\end{enumerate}

\end{enumerate}

\end{document}

