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

- Help With Ece 380,Help With Java/Pytho... 2023-02-23
- Help With Econ5102,Python/Java Program... 2023-02-23
- Cisc 360Help With ,C/C++ Programminghe... 2023-02-23
- Help With Stat 411,Help With Java/Pyth... 2023-02-22
- Comp90048help With ,Help With Java，C/... 2023-02-22
- Help With Ma1510,Help With C++/Java Pr... 2023-02-21
- Csci561 Programminghelp With ,Help Wit... 2023-02-21
- Econ 178Help With ,Help With R Program... 2023-02-20
- Help With Ecmm461,C/C++ Programminghel... 2023-02-20
- Msmk7021help With ,C++，Python Program... 2023-02-20
- Comp5400help With ,Help With Java/Pyth... 2023-02-20
- Cse214help With ,Help With C/C++，Java... 2023-02-20
- Help With Math5965,Help With R Program... 2023-02-20
- Help With Comp9012,Help With Python Pr... 2023-01-23
- Comp9414: Artificial Intelligence Assi... 2023-01-05
- Comp9444 Assignment 1 Neural Networks ... 2023-01-05
- Final Assignment - Apply All Your Skil... 2023-01-05
- Data7202 Statistical Methods For Data ... 2023-01-04
- Comp307/Aiml420 Assignment 4: Planning... 2023-01-04
- Comp3170 Assignment 3 Moonlit Forest 2023-01-04

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

© 2021 www.asgnhelp.com

Programming Assignment Help！