This is an old midterm study aid that you can use for now as a reading list.
I will update this when we get close to the midterm time to indicate
exactly what you need to know for the midterm.
You are also responsible for all material that has been covered on assignments.

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.

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.
Alphabets and Languages
Given languages L _{1} and L _{2}, define
(a)
L _{1} union L _{2}
(b)
L _{1} intersect L _{2}
(c)
L _{1} L _{2}
(d)
(L_{1})^{*}
Regular Languages
(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.
DFA
(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.
NDFA
(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?
DFA and NDFA
(a)
What is the relationship between DFA and NDFA?
(b)
Be able to apply algorithm for converting
a NDFA to a DFA.
Properties of languages accepted by FA.
(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.
FA and Regular Expressions
(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.
Pumping Lemma
(a)
State the pumping lemma for regular languages.
(b)
Be able to use the pumping lemma to prove that a language
is not regular.
ContextFree Grammars
(a)
Define a c.f.g.
(b)
Be able to find a c.f.g for a simple c.f.l.
Regular Languages and ContextFree Languages
(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^{n} b^{n }c^{n} : n >= 0}].
You don't need to know how to prove this is not
contextfree until the final exam.
Regular Languages and ContextFree 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^{n} x y^{n} z
is in L for all n greater than or equal to zero.
The cut off for the midterm material is here.
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?
PDA's and CFG's.
(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).
Closure Properties.
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.
CSC 320 Midterm Study Aid/ maintained by
Wendy Myrvold /
wendym@uvic.ca
/ revised June 15, 2017