Theory of Computation

Mondays and Wednesdays, 6:00 PM - 6:50 PM

Science 112

Mondays/Wednesdays 6:50PM - 7:50PM
Tuesdays/Thursdays, 1:00PM - 2:00PM
Thursdays 9:30PM - 10:30PM
Other days and times by appointment

• Determine the language represented by a regular expression
• Create a regular expression from a language description
• Construct a deterministic finite automaton accepting a given language
• For a given finite automaton (deterministic or nondeterministic) determine if a string is accepted
• Draw a state diagram for a finite automaton (deterministic or nondeterministic) that accepts a given language
• For a given finite automaton (deterministic or nondeterministic) find a minimum-state equivalent deterministic finite automaton
• Use a grammar to generate or accept a string
• For a given grammar give the derivation(s) of a specified string and draw the corresponding parse tree(s)
• Construct a context-free grammar for a language
• Construct a pushdown automaton that accepts a given language
• Show that a specific language is context-free
• Trace the computation for a specified Turing machine
• Create a Turing machine to solve a specified problem
• Determine whether a problem about Turing machines is solvable or undecidable
• Arrange classes of languages in order of increasing generality
• Discuss relative computational power of language recognizers

Your final course grade is determined by combining your grades on assignments and exams. You are guaranteed a grade no lower than that computed by the following distribution of total points and weighted average conversion to letter grade:

Distribution:
Assignments = 40%
Midterm = 25% (given during week 8)
Final Exam = 35%

Weighted average conversion to letter grade
100-90%: A;  89-80%: B;  79-70%: C;  69-60%: D;  59-0%: F

Every assignment turned in must include a section labeled Reflection that includes your personal insights and observations. This section is expected and required, whether or not the assignment specification mentions it explicitly.

Formats of files turned in for assignments must not depend on specific operating systems or software that requires purchase or paid licensing. The following are examples of acceptable formats: ASCII text, UNICODE text, HTML, PDF, GIF, JPEG. The following are examples of unacceptable formats: Microsoft Word, AppleWorks. If the assignment consists of multiple files, you are encouraged to bundle them into an archive in tar, zip or sit format.

Late assignments will not earn course credit. You may submit an assignment after its due date for comments and advice, and you are encouraged to do so. However, the score for that assignment will be recorded officially as 0. Likewise, missing an exam will result in a score of 0 for that exam. Late homework and make-up exams will not be accommodated without prior arrangement and written agreement. Unforeseeable crises and emergency situations will be dealt with on a case-by-case basis in accordance with MSCD, College, and Departmental policies.

Note that significant information will be disseminated during class sessions or on the course website that you will be responsible for whether or not you attended the sessions or accessed the website. Not all information necessary to successfully complete the assignments or examinations is covered in the texts.

Collaboration

I encourage collaboration and regard it as essential aspect of Computer Science. Collaboration and discussion with fellow students concerning course information, materials, assignments, and studying for exams is encouraged. You are not expected to learn the course content or work on assignments in isolation on your own. However, you must write up your own solution, individually, to every problem you turn in even if the solution is the result of a collaborative effort. In your write-up, you must credit the people with whom you worked. If you consult any reference material other than the textbook, please note in your assignment which sources you used for each problem. Note that collaboration is not acceptable during any exam.