Dates: 2/5/24 - 2/11/24. Test 1 in discussion section this week, Friday Feb 9 in discussion section 4pm-4:50pm WLH 2001. The test covers material in Weeks 1 through 4 and Monday of Week 5. In particular, you should make sure you can:
Distinguish between alphabet, language, sets, and strings
Translate a decision problem to a set of strings coding the problem
Use regular expressions and relate them to languages and automata
Write and debug regular expressions using correct syntax
Determine if a given string is in the language described by a regular expression
Use precise notation to formally define the state diagram of DFA, NFA and use clear English to describe computations of DFA, NFA informally.
State the formal definition of (deterministic) finite automata
Trace the computation of a finite automaton on a given string using its state diagram
Translate between a state diagram and a formal definition
Determine if a given string is in the language described by a finite automaton
Design and analyze an automaton that recognizes a given language
Specify a general construction for DFA based on parameters
Design and analyze general constructions for DFA
Motivate the use of nondeterminism
Trace the computation(s) of a nondeterministic finite automaton
Determine the language recognized by a given NFA
Design and analyze general constructions for NFA
Choose between multiple models to prove that a language is regular
Explain nondeterminism and describe tools for simulating it with deterministic computation.
Find equivalent DFA for a given NFA
Convert between regular expressions and automata
Classify the computational complexity of a set of strings by determining whether it is regular
Explain the limits of the class of regular languages
Identify some nonregular sets
Use the pumping lemma to prove that a given language is not regular.
Justify why the Pumping Lemma is true
Apply the Pumping Lemma in proofs of nonregularity
Use precise notation to formally define the state diagram of PDA and use clear English to describe computations of PDA informally.
Define push-down automata informally and formally
Trace the computation of a push-down automaton
Determine the language recognized by a given PDA
Design push-down automata to recognize specific languages
Determine whether a language is recognizable by a (D or N) FA and/or a PDA
Use context-free grammars and relate them to languages and pushdown automata.
Identify the components of a formal definition of a context-free grammar (CFG)
Derive strings in the language of a given CFG
Determine the language of a given CFG
Design a CFG generating a given language
To study for the exam, we recommend reviewing class notes (e.g. annotations linked on the class website, podcast, supplementary video from the class website), reviewing homework (and its posted sample solutions), and in particular *working examples* (extra examples in lecture notes, textbook examples listed in hw, review quizzes -- PDFs now available on the class website, discussion examples) and getting feedback (office hours and Piazza).