Chris Pollett> Old Classses >
CS154

( Print View )

Student Corner:
[Submit Sec1]
[Grades Sec1]

[Online Final-PDF]

[Online Midterm-PDF]

[Lecture Notes]
[Discussion Board]

Course Info:
[Texts & Links]
[Description]
[Course Outcomes]
[Outcomes Matrix]
[Course Schedule]
[Grading]
[Requirements/HW/Quizzes]
[Class Protocols]
[Exam Info]
[Regrades]
[University Policies]
[Announcements]

HW Assignments:
[Hw1] [Hw2] [Hw3]
[Hw4] [Hw5] [Quizzes]

Practice Exams:
[Midterm] [Final]

Learning Outcomes versus Collected Course Materials
LO1LO2LO3LO4LO5LO6LO7LO8LO9L10N/A
HW1X
HW2XXXXX
HW3XX
MP1XX
MP2X
MP3X
MP4XX
MP5X
HW4XXXX
HW5X

MPn = Midterm Problem n. FPn = Final Exam Problem n.

LO1 (Learning Outcome 1) -- Write a grammar for a language described otherwise.

LO2 -- Construct deterministic and non-deterministic machines for various languages.

LO3 -- Describe a language in terms of a regular expression.

LO4 -- Find a regular expression for a language described by a finite automaton and conversely.

LO5 -- Construct a deterministic finite automaton from a non-deterministic one.

LO6 -- Minimize a deterministic automaton.

LO7 -- Be able to use a pumping lemma to show that some languages are not regular and/or not context-free. Use closure properties to simplify proofs of non-regularity of languages.

LO8 -- Be able to construct a pushdown automaton accepting a given language.

LO9 -- Construct a Turing machine accepting some simple languages.

LO10 -- State in precise mathematical terms what is meant by undecidability of the Halting Problem, and be able to show the undecidability of simple extensions of the Halting Problem, using the reduction technique.

N/A -- Important material covered in the course but not directly related to a specific learning outcome.