\documentstyle [11pt]{article}
\begin{document}
\bibliographystyle{alpha}
\begin{center}
COMP 181 \\
Models of Languages and Computation \\
Spring 2001 \\
Mini Exam\\
Wednesday, April 11, 2001 \\
Closed Book - Closed Notes \\
Don't forget to write your name or ID and pledge on the exam sheet.
\end{center}
\input{epsf}

\vspace {.2in}

\noindent
1.  (10 points) Consider the context free grammar $G = (V,\Sigma,R,S)$
where $V$ is $\{S,A,a,b,c\}$, $\Sigma$ is $\{a,b,c\}$, and $R$
consists of the following rules:

\vspace {.2in}

\centerline{$S \rightarrow A$ \ \ \ $A \rightarrow AbA$ \ \ \ $A \rightarrow a$ \ \ \ $A \rightarrow c$}

\vspace {.2in}

(a) Which of the following words are in $L(G)$?  Circle all that are
in $L(G)$.

\vspace {.2in}

\centerline{$abcba$,  $c$, $bcb$, $abba$, $cc$, $ababcbaba$}

\vspace {.2in}

(b) Show parse trees for all words that are in $L(G)$ in part (a).

\vspace {1in}

\noindent
2.  (10 points) Consider the push-down automaton $M$ =
$(K,\Sigma,\Gamma,\Delta,s,F)$ where $K = \{s,f\}$, $\Sigma =
\{a,b\}$, $\Gamma = \{a,b\}$, $F = \{f\}$, and $\Delta$ consists of the
following transitions:

\vspace {.2in}

\centerline{$((s,a,e),(s,a))$, $((s,b,e),(s,b))$,
$((s,a,e),(f,e))$, $((f,a,a),(f,e))$, $((f,b,b),(f,e))$.}

\vspace {.2in}

(a) Which of the following words are in $L(M)$?  Circle all that are.

\vspace {.2in}

\centerline{$abab$,  $aaa$, $aab$,  $bbbaaabbb$, $aabbaa$,  $aaaabb$}

\vspace {.2in}

(b) Describe the language accepted by $M$ in simpler terms (that is,
without reference to a push-down automaton).

\vspace {1in}

\noindent
3. (10 points) Consider the deterministic finite automaton M with
states $\{p,q,r,s,t\}$, input alphabet $\{0,1\}$, start state $p$,
accepting state $t$, and with the following transitions:

\vspace{1.0in}

Construct an equivalent minimal deterministic finite automaton.

\vspace {1.0in}

For each multiple choice question, choose the best answer.

\vspace {.2in}

\noindent
4. (4 points) The language $\{a^nba^m : n,m \ge 0\}$ is

\vspace {.2in}
\noindent
a) regular \\
b) context-free but not regular\\
c) not context free \\
d) finite

\vspace {.2in}

\noindent
5. (4 points) Suppose $L$ is a context-free language.  Then

\vspace {.2in}
\noindent
a) There is a (nondeterministic) push-down automaton $M$ such that $L = L(M)$ \\
b) There is a nondeterministic finite automaton $M$ such that $L = L(M)$ \\
c) There is a deterministic finite automaton $M$ such that $L = L(M)$ \\
d) The complement of $L$ is context-free.

\vspace {.2in}

\noindent
6. (4 points) Suppose $L$ is the language represented by the regular
expression $((0 \cup 1)(0 \cup 1)(0 \cup 1))^*$.  True or false:

\vspace {.2in}
\noindent
a) $0 \approx_L 00$ \\
b) $1 \approx_L 1001$ \\
c) $01 \approx_L 10$ \\
d) $11 \approx 1101$

\vspace {.2in}

\noindent
7.  (10 points) Consider the context free grammar $G = (V,\Sigma,R,S)$
where $V$ is $\{S,A,B,a,b,c\}$, $\Sigma$ is $\{a,b,c\}$, and $R$
consists of the following rules:

\vspace {.2in}

\centerline{$S \rightarrow A$ \ \ \ $A \rightarrow aS$ \ \ \ $A \rightarrow a$}
\centerline{$S \rightarrow B$ \ \ \ $B \rightarrow bS$ \ \ \ $B \rightarrow b$}

\vspace {.2in}

\noindent
Is this grammar ambiguous?  Justify your answer.

\vspace {1in}

\noindent
8.  (10 points) Consider the language $L = \{(ab)^nc^n : n \ge 0\}$.
This language contains the words $e, abc, ababcc, abababccc$ et
cetera.  We give two possible proofs that this language is not
regular, which we call the Duke proof and the NC State proof.  Which
is better?  Are both proofs good?  Are both proofs bad?  Justify your
answer.  If you think one proof is better, say why.  If you think both
proofs are good or both proofs are bad, say why.

Duke proof:

We show that in the regular expression game, B can always win.
Suppose A picks the integer 5, B picks the word $ababcc$,
A picks $x = ab$ and $y = abc$ and B picks $i = 2$.  Since
the word $ababcabcc$ is not in $L$, B wins the game, so
$L$ is not regular.

NC State proof:

We show that in the regular expression game, B can always win.
Suppose A picks the integer $n$, B picks the word
$(ab)^nc^n$, then A picks $x$, $y$, and $z$ such that
$|xy| \leq n$ and $y$ is not $e$.  Then $B$ picks $i = 2$.
The word $xyyz$ is not in $L$ because the number of $a$'s or $b$'s
is larger than the number of $c$'s.  So B can always win, and $L$
is not regular.

\vspace {2in}

\noindent
9. (14 points) True or false:

\vspace {.2in}

(a) The context free languages are closed under union.

(b) The context free languages are closed under intersection.

(c) The context free languages are closed under Kleene star.

(d) The context free languages are closed under complementation.

(e) The context free languages are closed under concatenation.

(f) All regular languages are context-free.

(g) A language $L$ is context-free if there is a push-down automaton $M$
such that $L = L(M)$.

\vspace {.2in}

\noindent
10. (4 points) Suppose $((p, a, \beta), (q, \gamma))$ is a production
in a push-down automaton.  True or false:

\vspace {.2in}

a) $\beta$ is popped from the stack if this production is used.

b) $\beta$ is pushed onto the stack if this production is used.

c) $\gamma$ is popped from the stack if this production is used.

d) $\gamma$ is pushed onto the stack if this production is used.

\end{document}