\documentstyle [11pt]{article}
\begin{document}
\bibliographystyle{alpha}
\begin{center}
COMP 181 \\
Models of Languages and Computation \\
Spring 2001 \\
Mid Semester Exam\\
Monday, Feb. 26, 2001 \\
Closed Book - Closed Notes \\
Don't forget to write your name or ID and pledge on the exam sheet.\\
\vspace{.2in}
This exam has four pages.
\end{center}

\vspace {.2in}

1. (5 points) 

\vspace{.2in}

a) Suppose $R$ is the relation $\{(1,3),(2,3)\}$ and $S$ is the
relation $\{(3,4),(3,5)\}$.  What is the relation $R \circ S$ obtained
by composing $R$ and $S$?  List all ordered pairs in the relation.

\vspace{0.4in}

b) Suppose that $R$ and $S$ are arbitrary relations having exactly
four ordered pairs.  (In part (a), both relations have two ordered pairs.)
What is the {\em largest} possible number of ordered pairs in the
relation $R \circ S$?

\vspace{0.4in}

2. (5 points)  If $R$ is a relation, let $R^T$ be $R$ with all ordered
pairs reversed.  Thus if $R$ is $\{(0,1),(0,4)\}$ then
$R^T$ is $\{(1,0),(4,0)\}$.  True or false:

\vspace{.2in}

a)  If a relation $R$ is symmetric, then $R^T$ is always symmetric.

\vspace{.2in}

b)  If a relation $R$ is reflexive, then $R^T$ is always reflexive.

\vspace{.2in}

c)  If a relation $R$ is transitive, then $R^T$ is always transitive.

\vspace{.2in}

3. Consider the following regular expressions:

\vspace{.2in}

a) $(0^*10^*10^*)^*(1^*0)$

\vspace{.2in}

b) $0^* \cup (0^*10^*10^*)^*$

\vspace{.2in}

c) $((0 \cup 1)(0 \cup 1))^*$

\vspace{.2in}

d) $0^*10^*10^*$

\vspace{.2in}

e) $((0 \cup 1)(0 \cup 1))^*(0 \cup 1)$

\vspace{.2in}

Which of these represent the following sets of strings?

\vspace{.2in}

A) The set of binary strings containing exactly two ones.

\vspace{.2in}

B) The set of binary strings of even length.

\vspace{.2in}

C) The set of binary strings of odd length.

\vspace{.2in}

D) The set of binary strings containing an even number of ones.

\vspace{.2in}

E) The set of binary strings containing an odd number of ones.

\vspace{.2in}

4. (10 points) Consider the following sets of strings:

\vspace{.2in}

a) $\{x \in \{0,1\}^* : x \mbox{ has an even number of zeroes}\}$

\vspace{.2in}

b) $\{x \in \{0,1\}^* : x \mbox{ has an odd number of zeroes}\}$

\vspace{.2in}

c) $\{x \in \{0,1\}^* : x \mbox{ has even length}\}$

\vspace{.2in}

d) $\{x \in \{0,1\}^* : x \mbox{ has odd length}\}$

\vspace{.2in}

For each of the following finite automata $M$, state which set of
strings above is $L(M)$:

\vspace{.2in}

A)

\vspace{.4in}

B)

\vspace{.4in}

C)

\vspace{.4in}

D)

\vspace{.4in}

5. (10 points) Consider the following nondeterministic finite automaton $M$:

\vspace{.8in}

Which of the following automata are {\em both} deterministic {\em and}
equivalent to $M$?

\vspace{.4in}

a)

\vspace{.4in}

b)

\vspace{.4in}

c)

\vspace{.4in}

d)

\vspace{.4in}

6.  (10 points)
Consider the following proof:

\vspace{.2in}

Theorem.  Suppose $M$ is a nondeterministic finite automaton.
Let $M'$ be identical to $M$ except that the accepting and
non-accepting states of $M$ have been switched; that is, a state
$q$ is an accepting state of $M'$ exactly when $q$ is not an
accepting state of $M$.  Let $\Sigma$ be the input alphabet of $M$
and $M'$.  Then $L(M') = \Sigma^* - L(M)$.

Proof.  Consider a word $x \in \Sigma^*$.  Suppose $M$ accepts $x$.
Then there is a computation starting from the start state of $M$,
leading to an accepting state $r$ of $M$.  The same computation will
lead to the state $r$ of $M'$, but $r$ is not an accepting state of
$M'$.  Therefore $M'$ does not accept $x$.

Similarly, if $M$ does not accept $x$, then there is a computation
leading from the start state of $M$ to a non-accepting state $t$ of
$M$.  Since $t$ is a non-accepting state of $M$, $t$ is an accepting
state of $M'$.  Therefore $M'$ accepts $x$.

Therefore, $M'$ accepts $x$ exactly when $M$ does not accept $x$,
so $L(M') = \Sigma^* - L(M)$.

Is this proof correct?  If so, say why.  If not, say why not.

\vspace{2.0in}

7.) Suppose $M_1$ and $M_2$ are deterministic finite automata.
Is there always a deterministic finite automaton $M$ such that
$L(M) = L(M_1) - L(M_2)$, that is, $M$ accepts a word exactly
when $M_1$ accepts the word {\em and} $M_2$ does not accept the 
word.  Justify your answer briefly.

\end{document}