CS 291 Exam Three Terms and Concepts

Hein Section 3.3 Grammars

• Know how to do derivations given a grammar.
• Be able to find a grammar for a language given a description of the language.
• Understand how to show that a grammar is ambiguous by finding two parse trees for the same sentence.

Hein Section 11.1 Regular Languages

• Given a description of a language, be able to find a regular expression for it.
• Know how to do simple manipulations to show that two regular expressions are equivalent.

Hein Section 11.2 Finite Automata

• Given a DFA or NFA, be able to write down the transition table.
• Given a regular expression, be able to construct a DFA or NFA for recognizing that language.
• Given an FA, be able to find an equivalent regular expression.
• Understand Mealy Machines and Moore Machines and be able to show what their output would be given an input string.

Hein Section 11.3 Constructing Efficient Finite Automata

• Be able to find the lambda closure of an NFA state or set of states.
• Know how to convert an NFA into an equivalent DFA.

Hein Section 11.4 Regular Language Topics

• Know how to use the Pumping Lemma for Regular Languages to show that particular languages are not regular.