# COSC 3340: Introduction to Theory of Computation COSC 3340: Introduction to Theory of Computation University of Houston Dr. Verma Lecture 10 1 Lecture 10 UofH - COSC 3340 - Dr. Verma Chomsky Normal Form (CNF) Rules of CFG G are in one of two forms: (i) A a (ii) A BC, B S and C S + Only one rule of the form S is allowed if in L(G).

Easier to reason with in proofs Leads to more efficient algorithms Credited to Prof. Noam Chomsky at MIT Reading Assignment: Converting a CFG to CNF. 2 Lecture 10 UofH - COSC 3340 - Dr. Verma Exercises Are the following CFG's in CNF? (i) S aSb | (ii) S aS | Sb | (iii) S AS | SB | Aa Bb (iv) S AS | SB Aa|

Bb 3 Lecture 10 UofH - COSC 3340 - Dr. Verma Closure properties of CFL's CFL's are closed under: (i) Union (ii) Concatenation (iii) Kleene Star What 4 about intersection and complement? Lecture 10

UofH - COSC 3340 - Dr. Verma The setting L1 = L(G1) where G1 = (V1, T, P1, S1) L2 = L(G2) where G2 = (V2, T, P2, S2) Assume 5 wlog that V1 V2 = Lecture 10 UofH - COSC 3340 - Dr. Verma Closure under Union -- Example

L1 = { anbn | n 0 } L2 = { bnan | n 0 } G1 ? G2 ? Ans: S2 bS2a | How to make grammar for L1 L2 ?

6 Ans: S1 aS1b | Ans: Idea: Add new start symbol S and rules S S1 | S2 Lecture 10 UofH - COSC 3340 - Dr. Verma Closure under Union General construction Let 7 G = (V, T, P, S) where V = V1 V2 { S },

S V1 V2 P = P1 P2 { S S1 | S2 } Lecture 10 UofH - COSC 3340 - Dr. Verma Closure under concatenation Example L1 = { anbn | n 0 } L2 = { bnan | n 0 } Is L1L2 = { anb{2n}an | n >= 0 } ?

Ans: No! It is { anb{n+m}am | n, m 0 } How 8 to make grammar for L1L2 ? Idea: Add new start symbol and rule S S1S2 Lecture 10 UofH - COSC 3340 - Dr. Verma Closure under concatenation General construction Let 9

G = (V, T, P, S) where V = V1 V2 { S }, S V1 V2 P = P1 P2 { S S1S2 } Lecture 10 UofH - COSC 3340 - Dr. Verma Closure under kleene star Examples L1 = {anbn | n 0}

What is (L1)*? L2 = { a{n2} | n 1 } What is (L2)*? Ans: a*. Why? How to make grammar for (L1)*? 10 Ans: { a{n1}b{n1} ... a{nk}b{nk} | k 0 and ni 0 for all i }

Idea: Add new start symbol S and rules S SS1 | . Lecture 10 UofH - COSC 3340 - Dr. Verma Closure under kleene star General construction Let 11 G = (V, T, P, S) where V = V1 { S }, S V1

P = P1 { S SS1 | } Lecture 10 UofH - COSC 3340 - Dr. Verma Tips for Designing CFG's Use closure properties -- divide and conquer Analyze strings Is order important? Number? Do we need recursion? Flat versus hierarchical? Are any possibilities (strings) missing? Is the grammar generating too many strings? 12 Lecture 10 UofH - COSC 3340 - Dr. Verma