The following is simply a conveniently formatted list of learning goals. More likely than not, some might be hard to assess through a quiz or exam. Students should prioritize their studying based on:
- how much time in lecture was spent discussing or understanding the topic,
- how much the topic was stressed in learning group assignments
- and the student's comfort level with the topic
Assessable Learning Goals covered for Quiz 1 Learning Goals
Given a grammar, be able to derive a valid sentence of the grammar.
How are left-associative and right-associative connected to recursive production rules?
Know the difference between a leftmost derivation and a rightmost derivation.
Know the notational conventions for CFGs used in the book.
What are terminals, non-terminals, λ, and $ in a CFG?
What is a sentential form?
When might we suspect that a grammar is ambiguous?
Be able to deduce associativity and precedence rules for operators in a CFG.
Be able to design simple languages and grammars with nested productions and recursive rules.
Given a binary operator, △, know how to write its production rule for left or right associativity.
Given two binary operators △ and □ , know how to write a simple grammar to express their relative precedence.
Can a BNF grammar represent different languages than a CFG?
What is a regular grammar? What two production rule patterns are associated with regular grammars?
Be able to convert a RE (in the book's notation) to an equivalent NFA.
What features of a language are REs able to describe?
Be able to optimize a DFA to a smaller form by reconciling indistinguishable states.
Cite two ways that a FA (DFA or NFA) may be represented in computer memory. Understand their tradeoffs.
What are dead states and unreachable states in FAs?
What is the difference(s) between a NFA and a DFA?
Be able to convert an NFA to a (unoptimized) DFA.
Be able to construct a RE (in the book's notation) for particular token patterns.
How are the terms regular language, regular set connected to DFAs?
How are the terms regular language, regular set, and regular expression interrelated?
Know the (book's) notation and terminology for regular expressions.
Know the meaning of RE notations: AB, A|B, A∗, A+ and Aκ (κ a constant positive integer)
Know the meaning of λ, single characters s ∈ Σ, and T ⊆ Σ as they relate to the book's RE notation.
What are the three basic operations in REs from which all other operations may be derived.