CptS 317: Automata and Formal Languages
Final Exam (Take Home)
Assigned: May 1, 10 AM
Due by: May 4, 2 PM
Instructions:
1. Make sure that your exam has 2 pages (including this cover page). The exam questions begin
on the second page.
2. There are 10 questions in this exam; Questions Q2 and Q3 have multiple parts. The point
each question carries is shown in parenthesis. The points add up to 100. Read each question
carefully before you begin writing your solution.
3. The exam is take-home. Your solution in PDF format is to be submitted on OSBLE. You
may either type-up your solution to produce a PDF document, or hand-write your solution
and scan to get a PDF document. Both options are fine. If you hand-write, make sure to
write legibly.
4. The exam is due Monday May 4, 2020 by 2 PM.
5. As a reminder, the same WSU Standards of Conduct for Students, particularly the section
on Academic Integrity, apply to this take-home exam as any in-class exam. See the section
on Academic Integrity in the syllabus of the course for further information.
1
1. (8 pts) Now that you have completed this course and experienced what it had to cover,
suppose you were asked to develop a crisp and informative “course description” for it for use
for future semesters. The course description is to consist of a brief paragraph (roughly 3 to
5 sentences) followed by a list of topics. What would your course description be?
2. (6 pts) Consider the 8 homeworks you have worked on this semester. For each homework, do
the following two things:
i) Write a sentence listing the topics the homework covered; and
ii) Write a sentence describing something relevant to the course that you have learned from
solving one of the problems, or from reflecting on the posted solutions.
3. (12 pts) Let L and M be two languages. The XOR operator ⊕ between two languages is
defined as follows:
L⊕M = {w|w is either in L or M but not in both }
Is the XOR operation closed for the class of:
a) regular languages?
b) context free languages?
Answer each part with a yes/no, followed by a brief justification.
4. (10 pts) Write a context free grammar generating the language {a2nb3ma2mbn : n > 0,m > 0}.
Please check your solution by actually generating an example word from your grammar.
5. (10 pts) Show the language accepted by a pushdown automaton that never pops a stack is
regular.
6. (10 pts) Provide an implementation level description of a Turing machine that accepts the
language given by the regular expression a∗bb.
7. (14 pts) Say that a variable A in context free language G is usable if it appears in some
derivation of some string w ∈ G. Given a CFG G and a variable A, consider the problem
of testing whether A is usable. Formulate this problem as a language and show that it is
decidable.
8. (10 pts) Let A be a language and ATM be the language
ATM = {< M,w > |M is a Turing machine and M accepts w}
Show that A is Turing recognizable if and only if A ≤m ATM. Recall that the notation ≤m
denotes mapping reducible.
9. (12 pts) Provide an analysis of the time complexity of EQDFA and show that it is in P . Note
that here, EQDFA is an algorithm which takes two DFAs as inputs, and determines whether
they accept the same language.
10. (8 pts) Suppose you were invited to participate at an Oxford-style debate a student body at
a major research university organized on the following topic:
“Introduction to Theory of Computation” should be a required course for all Com-
puter Science students seeking a Bachelors degree.
Write a brief paragraph arguing for or against this debate question. You will be graded on
this not for the side you pick, but rather for the quality of the argument you make (i.e., the
points you make in your argument).