Computer Science 456/656 Fall 2001 First Examination, October 16, 2001

Name: No books, notes, or scratch paper. Use pen or pencil, any color. Use the rest of this page and the backs of the pages for scratch paper. If you need more scratch paper, it will be provided. The entire test is 135 points.

1. True or False. [5 points each] (a) The intersection of any two context-free languages is context-free.

(b) Every subset of a regular language is regular.

(c) The intersection of any two regular languages is regular.

(d) Every regular language is context-free.

(e) The set of all regular expressions over the alphabet {a, b} is a regular language.

(f) If a context-free language has an ambiguous context-free grammar, then it must have an unambiguous grammar.

(g) The programming language C is a context-free language.

2. [15 points] Let Σ = {a, b, c}. Let L_{1} be the set of all strings over Σ which contain the substring aab. Let L_{2} be the set of all strings over Σ which do not contain the substring ca.

(a) Draw a DFA which accepts L_{1}.

(b) Draw a DFA which accepts L_{2}.

(c) Combine the above two DFAs into an NFA-Λ which accepts L_{1} + L_{2}.

3. [30 points] Let L be the language generated by the following context-free grammar, G: S → Λ S → aS S → aSb

(a) Write a non-recursive definition of L.

(b) Demonstrate that G is ambiguous.

(c) Find an unambiguous grammar for L.

4. [25 points] Every NFA is equivalent to some DFA. Consider the NFA drawn below, where the input alphabet is {a, b, c}. Draw an equivalent minimal DFA.

5. [30 points] Use the pumping lemma for regular languages directly to prove that {a^{n}b^{2n}} is not a regular language.