Home Page > > Details

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).

Contact Us(Ghostwriter Service)

- QQ：99515681
- WeChat：codinghelp
- Email：99515681@qq.com
- Work Time：8:00-23:00

- Programhelp With ,Help With C++ Course... 2022-05-10
- Help With Data Programming,Help With C... 2022-05-10
- 5Cce2sashelp With ,Python，Java Progra... 2022-05-10
- Help With Program Programming,Help Wit... 2022-05-09
- Help With Csci 3110,Help With Java，Py... 2022-05-09
- Mth2222help With ,Help With C/C++，Pyt... 2022-05-09
- Cse3bdchelp With ,Help With Sql Progra... 2022-05-08
- Help With Cis 468,Help With Java，Pyth... 2022-05-08
- Comp Sci 4094/4194/7094 Assignment 3 D... 2022-05-07
- Cs 178: Machine Learning & Data Mining... 2022-05-07
- Data7703 Assignment 4 2022-05-07
- Data Programminghelp With ,Help With S... 2022-04-25
- Help With Ait681 Course,Help With Pyth... 2022-04-25
- Cse121l Programminghelp With ,Help Wit... 2022-04-25
- Help With Iti1120,Help With Java，C/C+... 2022-04-25
- Cmt304help With ,Help With C++，Python... 2022-04-25
- Help With Engn4528,Matlab Programmingh... 2022-04-24
- Help With Fin 2200,Help With Java，Pyt... 2022-04-24
- Bism 7255Help With ,Help With Java，Py... 2022-04-23
- Comp202help With ,Help With Java Progr... 2022-04-23

Contact Us - Email：99515681@qq.com WeChat：codinghelp

© 2021 www.asgnhelp.com

Programming Assignment Help！