105 Practice Final

These questions are from old 105 exams. Consider them representative of the type of questions that might be asked on the final. Note that the topics emphasized on our final differ vary from this practice test, i.e. your mileage may vary! Our exam will be on MONDAY, JUNE 8 at 8 a.m.. You will have 3 hours, however I am planning an exam that is only slightly longer than the midterm so you should have plenty of time. The exam will be closed book and closed notes.

By the way, you've been a great class! Study hard and good luck on the final.

1. Consider the context-free grammar G=(V,T,P,S) where P is the set of productions:
S-->aB
B-->Sbb
S--> epsilon

• What is L(G)?
• Is G a regular grammar? Why or why not?
• Transform G into a Chomsky Normal Form grammar G' which accepts L(G).

2. Consider the PDA M=({q₀,q₁,q₂},{a},{A,B},delta,q₀,A,{q₀}) with instructions delta(q₀,a,A)={(q₁,BA)}, delta(q₁,a,B)={(q₀,epsilon)} and delta({q₁,epsilon,B)={(q₂,B)}.

• What is N(M)?
• What is L(M)?
• Is M deterministic? Why or why not?

3. Fill in the following chart with Y if the set of languages in the row is closed under the property in the column and N if it is not.
Give a brief justification for 2 of your answers in each row.

	union	intersection	concatenation	complement
regular languages
context-free languages
recursive languages
r.e. languages

4. Consider the language L={0ⁿ1ⁿ2ⁿ| n > 0}.

• Show that L is not context-free.
• Is L recursive? Why or why not?
• Is L r.e.? Why or why not?

5. Let M=({q₀},{1},{1,B},delta,q₀,B,F) be a Turing machine with instructions delta(q₀,1)=(q₀,1,R) and delta(q₀,B)=(q₀,B,R).

• What is L(M)?
• Convert M to a TM M' accepting L(M) which halts iff it accepts. Describe M' by giving Q, SIGMA, GAMMA, delta, q₀ and F.

6. What kind of machines accept r.e. languages?
What kind of machines accept recursive languages?
Which one of these classes is a subset of the other?
Is this a proper subset (i.e. the two classes are not equal)? Why or why not?

7. Consider the following classes: recursively enumerable (r.e.) languages, languages accepted by deterministic FSAs, context-free languages (CFLs), recursive languages, all languages, regular langugages, deterministic context-free languages (DCFLs), languages accepted by DTMs.

Draw a diagram which shows the subset relationships between these languages.

For the given language classes, show by exhibiting particular languages, which subset relationships in the diagram are proper. For example, if you have claimed that language class A is a proper subset of language class B, then give an example of a language that is in class B but not in class A.

8. Show that it is undecidable to determine the following question: "Given TMs M₁ and M₂, is L(M₁)=L(M₂)?".