CPTR
324 Spring 2003 Exam 2 Name ________________________

1. Give an example of a
language that is context free but __not__ regular. (4 points)

2. A *pushdown automaton* *P*
is formally defined as a 6-tuple

*P = (Q, **S**, **G**, **d**, q _{0}, F)*

Define (or describe) each of
the 6 components. (6 points)

3. Circle **T** if the statement is true (that is, always true) and **F** otherwise. No justification is necessary. (14 points)

**T F** If *L* is a regular
language, then *L* is a context free
language.

**T F** If *L* is a context
free language, then *L* is a regular
language.

**T F** If *L _{1}*
is a CFL and

**T F** If *L _{1}*
is a CFL and

**T F** Every CFL contains the empty string *e*.

**T F** *L* = {*a ^{i}b^{i}c^{i}*
| 0 £

**T F** If *L _{1}*
is a CFL and

4. Consider the following
grammar:

*S **®** aSb | A*

*A **®** cAc | B*

*B **®** d | BB*

(a) Give the leftmost derivation
for the string *aacdddcbb*. (6
points)

(b) Give the corresponding parse
tree for that derivation. (5 points)

5. Consider the following PDA.

a. Give 3 strings accepted by
the PDA. (6 points)

b. Describe the language accepted by
the PDA. (4 points)

6. Using the techniques
presented in the algorithm that converts a CFG to Chomsky Normal Form (CNF),
construct a modified set of production rules that generate the same strings as
the given set of rules after performing the designated algorithm step: (5 points each - __each step is independent
of the others__)

- Remove
*e**-rules*:

*A **®** BaB | AaA*

*B **®** bAB | **e*

- Remove
*unit rules*:

*A **®** aB | aA*

*B **®** C | bB*

*C **®** b*

- Place in CNF format:

*A **®** aBaA*

- Prove that {
*a*^{n}b^{m}c^{n+m}| n, m*³**0*} is a CFL. If giving a grammar, give only the production rules. If giving a PDA, give only the transition diagram. (10 points) - Congratulations! You have
been doing so well in CPTR 324 that you have decided to try out for a
special tutoring position. Below
are two
__incorrect__answers to the question "Is the language {*0*^{n}10^{n}1 | n*³**0*} a CFL? Justify your answer." For each student, indicate what is wrong with their answer? (5 points each)

__Student 1__: Yes. The language {*0*^{n}10^{n}1 | n*³**0*} is a CFL because it is generated by the following CFG:

*S **®** AB*

*A **®** 0A | 1*

*B **®** 0B | 1*

__Student 2__: No. Assume that the language {*0*^{n}10^{n}1 | n*³**0*} is a CFL. Let*p*be the pumping length. … (student has rest of “set-up” correct) … Consider the string

*s = 0 ^{p}10^{p}1*. We can
write

*s = uvxyz,* where *uvxy* contain all 0's
from before the first 1 in the string.

Since |*vy*| must be
greater than 0 (by the Pumping Lemma), then when we pump up or down we no
longer have the same number of 0's before the first 1 as after the first 1,
which takes us out of the language.
Therefore this string (which is clearly longer than length *p*) cannot be pumped, a
contradiction. Therefore the language is
not a CFL.

*(So which is it?)*Show that the language {*0*^{n}10^{n}1 | n*³**0*} is a CFL by drawing the transition diagram for a PDA that accepts it. (10 points).- Use the Pumping Lemma
to prove that {
*a*^{n}b^{2n}c^{3n}| n*³**0*} is not a CFL. (10 points)