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, q0, 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 L1 is a CFL and L2 is a CFL, then L1 L2 is a context free language.

 

T F If L1 is a CFL and L2 is a CFL, then L1 L2 is a context free language.

 

T F Every CFL contains the empty string e.

 

T F L = {aibici | 0 i 100,000} is a context free language.

 

T F If L1 is a CFL and L1 L2 is a CFL, then L2 is a CFL.

 

 

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)

 

 

  1. Remove e-rules:

A BaB | AaA

B bAB | e

 

 

  1. Remove unit rules:

A aB | aA

B C | bB

C b

 

 

 

  1. Place in CNF format:

A aBaA

 

 

 

 

 

 

  1. Prove that {anbmcn+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)

  2. 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 {0n10n1 | n 0} a CFL? Justify your answer." For each student, indicate what is wrong with their answer? (5 points each)

 

 

  1. Student 1: Yes. The language {0n10n1 | n 0} is a CFL because it is generated by the following CFG:

 

S AB

A 0A | 1

B 0B | 1

 

 

 

 

 

 

 

 

 

 

  1. Student 2: No. Assume that the language {0n10n1 | n 0} is a CFL. Let p be the pumping length. (student has rest of set-up correct) Consider the string

s = 0p10p1. 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.


  1. (So which is it?) Show that the language {0n10n1 | n 0} is a CFL by drawing the transition diagram for a PDA that accepts it. (10 points).

  2. Use the Pumping Lemma to prove that {anb2nc3n | n 0} is not a CFL. (10 points)