Intro to Theory of Computation

CS 321 HW 5 – 25 points

1. (5 pts) Convert the grammar below to CNF. Show your steps.

G = (V,T,S,P) where

V = { S, A, B, C, D}

T = { a, b }

and P is given below.

S  ABC | aBB

A  BAA | C

B  BB | b | 

C  CD | a

D  Da | abD

2. (6 pts) Consider the CNF grammar G = (V,T,S,P) where

V = {S, A, B, C, D }, T = { 0, 1, 2 }, S = S and P is given below.

S  BB | AD | CA

A  AA | 0

B  BB | AB | 1

C  AC | DC | 2

D  DD | 1

Use the CYK to determine if the strings w1 = 10112 and w2 = 00011 are in the language L(G). Give the

CYK dynamic programming table (upper diagonal) for each string using the algorithm presented in class

and in the handout. If the string is in L(G) construct the parse tree.

3. (14 pts) Construct npda’s that accept the following languages on  = {a, b }. Give both a verbal

explanation on how your npda works and the formal definition including the transition graph from JFLAP

to define the transition function. You must also submit the JFLAP code file for each problem to receive

full credit.

a) L = { a2nbn : n  0 }

b) L = { w : na(w) = 2nb(w) }