=========================preview======================
(COMP272)[2011](s)midterm~=4e822^_84109.pdf
Back to COMP272 Login to download
======================================================
COMP 272: Theory of Computation
Fall 2011 Midterm Exam

1.
Printyour name and studentID at the top of everypage(in case the staplefalls out!).

2.
This is an open-book, open-notes, open-brain exam.

3.
Time limit: 120 minutes.

4.
You should answer all the questions on the exam. At least you should read all the questionsthey are not ordered by their di.culty!


5. When askedtoconstruct anautomaton,you canuse either a statediagram(rec-ommended) or the formal mathematical de.nition.
6.
You can write on the back of the paper if you run out of space. Please let us know if you need more scratch paper.

7.
Relax andbreathe,itsjust a midterm.


1.
(10 pts)Construct a DFA that accepts the language L = {w |w {0,1}. ,w has an even number of 0s and an odd number of 1s}.

2.
(10 pts) Give a context-free grammar that generates the languages L = {w | w = xy, where x,y {0,1}+ ,|x|= |y|,x .= yR}.

3.
(8 pts)Are the following sets countable or uncountable? You do not need to prove your answers. Let N be the set of natural numbers, and = {0,1}.

(a) {(x,y)|x,y N,x .= y}.
(b)
Any in.nite language over .

(c)
The set of all languages over .

(d)
The set of all .nite languages over .



4.
(12 pts)In class we proved that context-free languages are not closed under complemen-tation by resorting to intersection. Here is a concrete counter-example. Fix the alphabet


nbnn
= {a,b,c}, and let L = {ac: n 0}. We know in class that L is not context-free. Show that the complement of L is context-free. [Hint: Express L as the union of three languages, one regular, the other two context-free.]
5. (20pts) Prove that the language {w {a,b}. : w has twice as many bs as as} is not regular.
R
6.
(20pts)Let L be a regular language. Prove that {w|w L}is also a regular language.

7.
(20 pts) Let M =(K,,,,s,F) be a pushdown automaton. In class, the language accepted by M isde.ned tobe the set of strings on which thereis a computation sequence such that when the entireinput stringis read, M is at a .nal state and the stack is empty. Here we show that the stack being empty condition is dispensable. De.ne


LF (M)= {w . :(s,w,e).. (f,e,)for some f F, .}.

(a)
Show that there is a pushdown automaton M such that L(M )= LF (M).
)


(b)
Show that there is a pushdown automaton M such that LF (M = L(M).