CSC 320, Fall 2011 Midterm Study Aid

You are also responsible for all material that has been covered on assignments. I will update when we get close to the midterm time to indicate exactly what you need to know for the midterm.

1. Study all of chapters 1, and 2, and sections 3.1, 3.2, and 3.3 except: skip the ``If'' part of the proof of Theorem 2.3.2.
2. The pumping lemma is stated in Theorem 2.4.1.

Proof Techniques and Introductory Mathematics.

(a) Induction.
(b) The pigeonhole principle.
(c) Countable and uncountable sets: dovetailing, and diagonalization.

Given languages L ₁ and L ₂, define
(a) L ₁ union L ₂
(b) L ₁ intersect L ₂
(c) L ₁ L ₂
(d) (L₁)^*

(a) What symbols are allowed in a regular expression?
(b) What is a language generator?
(c) Be able to give a regular expression for a simple regular language, understand the languages represented by regular expressions.

(a) Define a DFA.
(b) Be able to create a DFA for a simple regular language.
(c) Understand state diagrams of DFA.
(d) Define a configuration for a DFA. Understand how to represent a computation of the DFA using configurations.
(e) Define the ``yields in one step'' operator for a DFA.

(a) What is a NDFA?
(b) How is it different from a DFA?
(c) Define L(M) for a NDFA M.
(d) Which strings are accepted by a NDFA? Which are not accepted?

(a) What is the relationship between DFA and NDFA?
(b) Be able to apply algorithm for converting a NDFA to a DFA.

(a) List 5 operations that are closed for regular languages.
(b) Outline proofs for operations in (a) and be able to apply the constructions implicit in the proofs.
(c) Give algorithms to answer the questions listed in Theorem 2.6.1, p. 104.
(d) Be able to describe algorithms which answer similar questions.

(a) Be able to find a NDFA for a language represented by a regular expression.
(b) State the relationship between regular languages and the languages accepted by FA.

(a) State the pumping lemma for regular languages.
(b) Be able to use the pumping lemma to prove that a language is not regular.

(a) Define a c.f.g.
(b) Be able to find a c.f.g for a simple c.f.l.

(a) Define a regular grammar.
(b) Be able to find a regular grammar for a regular language.
(c) Be able to find a NDFA for any language generated by a regular grammar.
(d) What is the relationship between c.f.l. and regular languages?
(e) Give an example of a c.f.l. that is not a regular language. [The canonical example is {aⁿ bⁿ cⁿ : n >= 0}]. You don't need to know how to prove this is not context-free until the final exam.

Regular Languages and Context-Free Languages

(a) Given a derivation, know how to draw the parse tree, and get a leftmost derivation that is equivalent from the parse tree.
(b) Given a parse tree, be able to identify u, v, x, y, z as per the pumping theorem so that u vⁿ x yⁿ z is in L for all n greater than or equal to zero.

(a) Define a c.f.g.
(b) Be able to find a c.f.g for a simple c.f.l.

(a) Define a regular grammar.
(b) Be able to find a regular grammar for a regular language.
(c) Be able to find a NDFA for any language generated by a regular grammar.
(d) What is the relationship between c.f.l. and regular languages?
(e) Give an example of a c.f.l. that is not a regular language.

PDA's.

(a) Define a PDA.
(b) Be able to write PDA ``programs'' for accepting simple c.f.l.
(c) Define a configuration of a PDA.
(d) Define ``yields in one step'' for a PDA.
(e) Define L(M) for a PDA M.
(f) Which strings are accepted by a PDA? Which are not accepted?

(a) Be able to use construction to find a PDA for a language generated by a c.f.g.
(b) Know that it is possible to find a c.f.g. for a language accepted by a PDA (you do not need to know the construction in this case).

1. List 3 properties which are closed for c.f.l.
2. Be able to apply constructions involved in proofs from (1).
3. Know that c.f.l.'s are closed under intersection with a regular language. Be able to apply construction in proof of this result.

Return to Home page for CSC 320.