%tex for assignment 2 in cs 81. Due Wed, Jan 31.
\documentclass{article}
\usepackage{amsmath}
\begin{document}

1. [10 Points] Kozen pg 302 \# 1.

The following nondeterministic automaton accepts the set of strings in 
$\{a,b\}^*$ ending in aaa.  Convert this automaton to an equivalent 
determistic one using the subset construction. Show clearly which subset 
of $\{s,t,u,v\}$ corrosponds to each state of the deterministic automaton.  
Omit inaccessible states. %diagram omitted.

2. [20 Points] Kozen pg 303, \#1d

Give a regular expression for the following subset of $\{a,b\}^*$.

$\{x|x $ contains an even number of a's and an odd number of b's. $\}$

3. [20 Points] Kozen pg 303 \#2c.  Use the derivatives method if 
possible, otherwise fall abck to the NFA method.  Give deterministic 
finite automata accepting the sets of strings matching the following 
regular expression.

$(0+1(01^*0)^*1)^*$

4. [20 Points] Kozen page 305 \#3 right. For the automaton

\begin{tabular}{c|cc}
&a&b\\
\hline
$\rightarrow$ 1F & 3 & 5\\
2F&8&7\\
3&7&2\\
4&6&2\\
5&1&8\\
6&2&3\\
7&1&4\\
8&5&1\\
\end{tabular}

\noindent (a) say which states are accessible and which are not

\noindent (b) list the equivalence classes of the collapsing relation 
$\approx$ defined in Lecture 13:

$$p \approx q \Leftrightarrow \forall x \in \Sigma^* (\hat{\delta}(p,x) 
\in F \Leftrightarrow \hat{\delta}(q,x) \in F)$$

\noindent (c) give the automaton obtained by collapsing equivalent 
states and removing inaccessible states.

5. [10 points] 

One of the rules for computing dervatives of regular-language 
expressions requires information about whether the empty string is in a 
language represented by the expression.  Give a way to derive this 
information syntactically using structural induction, without requiring 
construction of an automaton to et the information.

6. [20 points]

Depict the abstract states and transitions of the non-regular language 
$\{x0x | x \in \{1\}^*\}$.

\end{document}
