Michigan State University
CPS 360 - Midterm Examination Review

Instructor: Travis Doom

Summer Semester, 1998

This document contains a list of topics and questions that could appear on the midterm examination in CPS 360. The majority of the test material will cover the topics listed below, but any material appearing in the textbook (Ch. 1.0-9.2) or discussed in class may appear on the exam. The management reserves the right to include questions not explicitly included in this list.

1.

Given two languages (either in terms of set operations or as regular expressions), and given some strings, do the strings belong to:

(a): either language?
(b): to the union of the languages?
(c): to the intersection of the languages?
(d): to the closure of the languages?

2.

Explain the difference between:

(a): the null string and the empty language
(b): a regular expression (RE) and a regular language (RL)

3.

Given an RE or English-language statement describing a language:

(a): write down a simple, compact English-language characterization of the language or an RE for the language
(b): draw the graph of an NFA- $\Lambda$ that accepts the language represented by the RE
(c): find an FA having a minimum number of states that accepts the language represented by the RE

4.

Given the graph representing a finite automaton M (or representing an NFA or NFA- $\Lambda$ ):

(a): formally and explicitly list the five components of the definition
(b): determine whether your have a FA, NFA, or NFA- $\Lambda$
(c): does a give string belong to L(M)?
(d): exhibit the results of a computation
(e): write an expression for the accepted language (no partial credit given without an explanation)

5.

Given the graph or transition function for an NFA- $\Lambda$ :

(a): write down the lambda-closure of a set of states
(b): find an equivalent NFA

6.

Given the graph or transition function for an NFA or FA:

(a): find an equivalent FA
(b): find an equivalent FA with a minimal numbers of states

7.

Given FA M₁ and M₂ that recognize languages L₁ and L₂, construct an NFA- $\Lambda$ to recognize:

(a): the complement of L₁
(b): the union of L₁ and L₂
(c): the intersection of L₁ and L₂
(d): the difference between L₁ and L₂
(e): the closure (Kleene's star) of L₁

8.

Given either the RE for a language or the graph for an FA:

(a): exhibit a pair of strings that are distinguishable
(b): exhibit a pair of strings that are not distinguishable
(c): find the equivalence classes for the indistinguishability relation (I_L)
(d): explain why these equivalence classes are important

9.

Given a description of a language:

(a): is the language regular?
(b): prove regularity (FA, RE, RG, etc)
(c): prove non-regularity (Myhill-Nerode theorem, pumping lemma, closure properties of regular languages, etc)

10.

Understand context-free grammars (CFG) and languages (CFLs):

(a): what is a derivation?
(b): how is a CFL defined?
(c): given a language, describe a CFG that generates it
(d): under what set operations are the class of CFLs closed?

11.

Given a CFG:

(a): describe the language it generates
(b): construct a derivation tree for a given string
(c): is the grammar ambiguous? can an equivalent unambiguous grammar be constructed
(d): find an equivalent CFG without $\Lambda$ -productions
(e): find an equivalent CFG without unit-productions
(f): find an equivalent CFG in Chomsky normal form
(g): design a PDA to accept it

12.

Given two CFGs:

(a): construct a CFG to generate the union of the individual languages
(b): construct a CFG to generate the concatenation of the individual languages
(c): construct a CFG to generate the Kleene star of the individual languages

13.

Determine if a CFG is a regular grammar:

(a): given a regular language, construct a regular grammar for it
(b): given a regular grammar, write a regular expression for the language it generates
(c): given a regular grammar, construct an FA that accepts the language it generates

14.

Given a pushdown automaton (PDA):

(a): is the PDA deterministic or not?
(b): is the string x accepted by final state or empty stack or not accepted?
(c): describe the language it accepts
(d): show a computation for a string x

15.

Given a language:

(a): design a PDA to accept the language it generates
(b): prove the language context-free (CFG, PDA)
(c): prove the language is not context-free (pumping lemma)

16.

Turing Machine (TM) Basics:

(a): what sorts of moves are allowed?
(b): show a computation for a configuration (q,xay)

17.

Given a list of statements about the properties of a language or FA or just about anything else, such as relations and functions, determine whether each is correct or not (True/False questions).

18.

Be able to present the ``high-level'' concepts discussed in class, such as:

(a): what is it about a language that makes it regular?
(b): of what use is an NFA- $\Lambda$ ?
(c): why bother minimizing the number of states in a FA?
(d): why is ambiguity in a grammar undesirable?
(e): why bother with normal forms?
(f): what is non-determinism?
(g): why is the Church-Turing Thesis important?

Travis Doom, travis.doom@wright.edu.

Last modified: 06/07/98

Michigan State University CPS 360 - Midterm Examination Review

Michigan State University
CPS 360 - Midterm Examination Review