SUNY Geneseo, Department of Computer Science

Sample Exam 1

CSci 342, Fall 2001

Prof. Doug Baldwin

General Directions: This is an open-book, open-notes, closed-neighbor test. You have until the end of class to complete it. Each question is marked with a value in points, for a total of 50 points. There are as many points on the test as minutes in the class period, so you can use point values to tell how long it’s worth spending on each question. Put your answer to each question in the space provided. Be sure to Show Your Work! Partial credit will be given for incorrect answers if you show correct steps leading up to them. Conversely, full credit will not be given for correct answers if it isn’t clear how you got them. Good luck.

This exam contains 4 questions on 3 pages.

Question 1

(15 Points).

Design a finite automaton (either deterministic or non-deterministic) that accepts all and only strings of the form aⁿb^mc^{(n+m) mod 3}.

Question 2

(20 Points).

Show that Kleene * can be replaced by Kleene + (meaning “one or more”) in the definition of “regular expression” without weakening the expressive power of the expressions.

More formally, change the definition of “regular expression” over alphabet Sigma to be …

• a, where a is any element of Sigma,
• epsilon, denoting the empty string,
• Phi, denoting the empty language.
• R1 R2, denoting the concatenation of the languages described by regular expressions R1 and R2,
• R1 Union R2, denoting the union of the languages described by regular expressions R1 and R2,
• R1⁺, denoting the language containing all strings made up of one or more copies of strings from the language described by regular expression R1.

Show that for every standard regular expression, there is an equivalent regular expression of the new sort that describes the same language.

Question 3

(10 Points).

Consider the Latin alphabet (i.e., the letters A through Z and their lower-case equivalents), and the language over it consisting of all strings of the form wW where string W is the upper-case equivalent of string w. For example, abcdABCD and xyzXYZ are in this language, whereas xyzABC and PqRs are not. Show that this language is not regular.

Question 4

(5 Points).

Does the following NFA accept the string aabb? Briefly explain your answer.