CS154 Spring 2020

Learning Outcomes versus Collected Course Materials
	LO1	LO2	LO3	LO4	LO5	LO6	LO7	LO8	LO9	L10	N/A
HW1		X
HW2			X	X	X	X	X
HW3	X						X
MP1				X	X
MP2											X
MP3						X
MP4			X				X
MP5		X
HW4	X						X	X	X
HW5										X

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.