Tuesdays & Thursdays, 1:00 PM - 2:50 PM

Science 113

• 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

Significant information will be disseminated during class sessions or on the course website that you are responsible for whether or not you attended the sessions or accessed the website. That is, all information necessary to successfully complete the course is not necessarily covered in the texts.

Assignments & Practice

Note that extensive hands-on practice is necessary to achieve the required level of understanding and technical ability. Experience has shown that such practice is also necessary for successful performance on the exams.

Exercises are assigned that specifically target these objectives. You are strongly advised to work through all assigned exercises, by hand, and to attempt as many additional exercises as you need to develop facility with the concepts and techniques.

You are expected to use JFLAP to verify your solutions, as well as to experiment and explore the course material.

Assignments represent your opportunity to learn the material and you are not responsible for mastery of the material until the midterm and final exams. Thus, assignment solutions themselves are not graded. Instead, a write-up is required for each assignment set, in which you are expected to reflect on the experience of working on the assignment and report personal insights and observations.

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. Assigned exercise solutions are not graded in part to encourage collaborative learning and study. You are not expected to learn the course content or work on assignments in isolation on your own. Note that collaboration is not acceptable during any exam.

Grading

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

Distribution:
Assignment write-ups = 10%
Midterm = 35% (given during week 4)
Final Exam = 55% (given during week 8)

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