\documentclass[11pt]{article}
\usepackage{handout2e}
\usepackage{graphicx, epsfig}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{CSG714}{Theory of Computation}{Spring 2009}{9 January 2009}{2}

\begin{center}
\Large{\bf Problem Set 1 (due Friday, January 23)}
\end{center}

{\bf 1. (10 points) Neural nets and finite state automata}

This problem is taken from the text by Aho, Hopcroft, and Ullman.
Figure~\ref{fig:neural} depicts a neural network.  Each neuron (the
triangles depicted in the figure) has excitatory (clear circles) and
inhibitory (filled circles) synapses.  A neuron produces a 1-output if
the number of excitatory synapses with 1-inputs exceeds the number of
inhibitory synapses with 1-inputs by at least the threshold of the
neuron (the number inside the triangle).

Determine a finite state automaton whose behavior is equivalent to
that of the given neural network.  The final states of the automaton
correspond to a 1-output of the network.  Assume that there is
sufficient time between changes in input value for signals to
propagate and for the network to reach a stable configuration.  Assume
that the initial values of x, y, and z are all 0.

\begin{figure}[h]
\begin{center}
\includegraphics[width=4.5in]{neural.eps}
\caption{A neural network.\label{fig:neural}}
\end{center}
\end{figure}

{\bf 2. (3 $\times$ 5 = 15 points) Number of states in FSAs}

Consider the language $L_k$ defined over the alphabet $\{0,1\}$, for a
given integer $k > 0$.

\[
L_k = \{w \in \{0,1\}^*: w \mbox{ has a 1 in the $k$th position from
the end}\}.
\]

\begin{itemize}
\item[{\bf (a)}] Describe an NFA for $L_k$, given integer $k > 0$.

\item[{\bf (b)}] Describe a DFA for $L_k$, given integer $k > 0$.  How
many states does your DFA have?

\item[{\bf (c)}]
Show that the number of states in any DFA for $L_k$ is exponential in
$k$ while there exists an NFA for $L_k$ whose number of states is
linear in $k$.
\end{itemize}

{\bf 3. (2 $\times$ 7 = 14 points) Regular languages}

For each of the languages below, determine whether it is regular.
Justify your answer.

\begin{itemize}
\item[{\bf (a)}] $\{u w u^R: u,w \in \{0,1\}^+\}$.

\junk{
The first and last symbols have to be identical.  So we have strings
of the form 0x0 or 1x1.  Clearly, these are regular.
}

\item[{\bf (b)}]
$\{u u^R w: u,w \in \{0,1\}^+\}$.
\end{itemize}

{\bf 4. (2 $\times$ 8 = 16 points) Context-free grammars} 

Design a context-free grammar for each of the following languages over
the alphabet $\{a,b,c\}$.

\begin{itemize}
\item[{\bf (a)}] 
Set of all strings with twice as many $b$'s as $a$'s.

\item[{\bf (b)}]
The set $\{a^ib^jc^k: i,j,k \ge 0 \mbox{ and if } i = 1 \mbox{ then }
j = k\}$.
\end{itemize}

{\bf 5. (3 $\times$ 5 = 15 points) Context-free languages and PDAs}

\begin{itemize}
\item[{\bf (a)}] Show that the following language is not context-free.

\[
\{a^ib^jc^k: 0 \le i \le j \le k\}
\]

\item[{\bf (b)}] Show that the following language is context-free, by
constructing a (nondeterministic) PDA that accepts the language.

\[\{a^n b^n: n \ge 1\} \cup \{a^n b^{2n}: n \ge 1 \}.\]

\item[{\bf (c)}] Prove that there does not exist any {\em
deterministic}\/ PDA that accepts the language of (b).

({\em Remark:} This is a challenging problem.  One approach in to
argue that any DPDA cannot ``differentiate'' between all strings of
the form $a^n b^n$.  That is, for two such strings, it will end up in
the same configuration.  Then, argue that such a machine cannot
possibly accept the above language.)
\end{itemize}
\end{document}