- 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).