Chapter 10. Manipulating Context-free Grammars

Models of Language Generation: Grammars

1

10. Manipulating Context-free Grammars Throughout the last three chapters we studied the characterization among the three models of regular grammars, FA and regular expressions, which belong to the bottom level of the Chomsky hierarchy, and how to manipulate them. In this chapter, we move one level up the hierarchy and study how to manipulate CFG’s and PDA. Since PDA’s have a stack, it is much harder to manipulate them than FA. The nondeterminism in FA does not make any difference in the class of languages recognized by them, i.e., if a language is recognizable by an NFA if and only if it is recognizable by a DFA. Actually, there is an effective method to transform an NFA to a DFA which recognizes the same language. In contrast, there are context-free languages that can only be recognized by an NDPDA. There is no algorithm available for converting an NPDA to a DPDA or for minimizing the number of states of a DPDA. Our study will mainly focus on CFG’s till Chapter 13, where we will come back to a variation of DPDA and a subclass of CFG’s for an application. 10.1 Reducing ε -production rules 254 Algorithm and example 10.2 Eliminating unit production rules 262 Algorithm and example 10.3 Eliminating useless symbols 266 Algorithm and example 10.4 Normal forms of CFG’s 277 Chomsky normal form (CNF) Greibach normal form (GNF) Exercises 285

2

Manipulating CFG

10.1 Minimizing the number of ε -production rules Using ε -production rules may help designing a succinct grammar. However, like

ε -transitions in an FA, it could be computationally intensive to automatically analyze the language generated by a grammar which has many ε -production rules. In this section we will learn how to minimize the number of ε -production rules in a CFG. To understand the basic idea of minimizing the number of ε -production rules, let’s see how we can reduce the number of the ε -production rules in the CFG G shown below, while preserving the language of the grammar.

Eliminating A → ε and B → ε , we need to expand the rule S → AB as shown in G′ so that G and G′ generate the same language. In G′ we keep the rule S → AB for the case when both A and B, respectively, produce a and b. In addition to this rule we need the rule S → A for the case when A and B, respectively, produce a and ε . Likewise, we need the rule S → B for the case when A and B, respectively, produce ε and b. Finally, we need S → ε , for the case of A → ε and B → ε . We claim that L(G) = L(G′ ).

G:

S → AB

G′ : S → AB | A | B | ε

A →a | ε A →a

B →b | ε B →b 3

Manipulating CFG

Minimizing ε -production rules

In the previous example since the language contains ε , the grammar G’ needs one ε -production rule S → ε . If the language does not contain ε , we can eliminate ε -production rules completely, as the following example shows. G:

S → ABc

G′ : S → ABc | Ac | Bc | c

A →a | ε

B →b | ε

A →a

B →a

We apply the same idea when a nonterminal generates ε indirectly, as C and D do in the CFG G below. (Notice that C and D can derive ε , respectively, using A and B.)

G:

S → CD

C →A | c

G′ :

S → CD | C | D | ε

D →B | d C →A | c

A →a | ε D →B | d

A →a

B →b | ε B →b

4

Minimizing ε -production rules

Manipulating CFG

Now, for the proof of the following theorem we present an algorithm which given a CFG G, minimizes the number of ε -production rules of G using the idea presented above. Theorem 10.1 Given a CFG G, we can construct a CFG G' that satisfies the following conditions. • L(G) = L(G'). • If ε ∉ L(G), G' has no ε -production rule. Otherwise, S → ε is the only ε production rule in G'. Proof (Algorithm): Let G = (VT, VN, P, S) be the CFG. The following algorithm constructs a CFG G' = (VT , VN , P', S), which satisfies the conditions.

5

Minimizing ε -production rules

Manipulating CFG

Algorithm (minimizing ε -production rules) Input: a CFG G = (VT, VN, P, S) Output: a CFG G′ = (VT , VN , P', S), G′ satisfies the conditions of the theorem (1) With the following procedure find all nonterminal symbols in VN, which directly (by line 1) or indirectly (by lines 2 - 5) generate ε , to construct the set W. 1. W = {A | A ∈ VN , A → ε }; 2. Do { 3.

W′ = W;

4.

W = W' ∪{A | A ∈ VN , A → α , α ∈ (W′ ) +};

5.

} while ( W != W′ );

6

Minimizing ε -production rules

Manipulating CFG

Algorithm (continued) (2) Eliminate all ε -production rules from the rule set P, and let the resulting set be P1. (3) With P1, construct the rule set P' of G′ as follows: For each rule A → α (A ∈ VN ), construct the following set R. R = {α ' | α ' (≠ ε ) is a string constructed with α by deleting zero or more symbols from α that belong to the set W constructed in step (1) of the algorithm.} For every α ' ∈ R add the rule A → α ' to the set P'. (Notice that ε ∉ R, i.e., A → ε is excluded in this step, and every rule in P1 is included in P'.) (4)Now, If thewe start symbol S is examples in W, put of theminimizing rule S → ε the in number P'. (Notice that if S ∈ W, then will show two ε -production εrules is in the language L(G), and hence, G' needs the rule S → ε .) using this algorithm.

7

Manipulating CFG Minimizing ε -production rules Example 1. Minimize the number of ε -production rules of the following CFG G. G:

S → CD

C →A | c

D →B | d

A →a | ε

B →b | ε

Applying steps (1) - (4) of the algorithm, we get the following. (1) : W = { A, B };

W′ = W;

// W = { A, B }

W = W′ ∪ { C, D }; W′ = W;

// W = { A, B, C, D }

W = W′ ∪ { S };

// W = { A, B, C, D, S }

W′ = W;

W = W′ ∪ { }; (2) : P1 = { S → CD

// W = { A, B, C, D, S } C →A | c

D →B | d

A →a

B →b }

(3), (4): G′ : S → CD | C | D | ε

C →A | c

D →B | d

A →a

B →b

8

Manipulating CFG

Minimizing ε -production rules

Example 2. Minimize the number of ε -production rules from the following CFG G. G: S →ADC | EFg

A →aA | ε

D → FGH | b

C →c | ε

E →a

F →f | ε

G → Gg | H

H →h | ε

(1) W = {A, C, F, H};

W′ = W;

W = W′ ∪ {G};

W′ = W;

// W = {A, C, F, G, H};

W = W′ ∪ {D};

W′ = W;

// W = {A, C, D, F, G, H};

W = W′ ∪ {S};

W′ = W;

// W = {A, C, D, F, G, H, S};

W = W′ ∪ { } ;

W′ = W;

// W = {A, C, D, F, G, H, S};

9

Manipulating CFG

Minimizing ε -production rules G: S →ADC | EFg E →a

A →aA | ε

D → FGH | b

C →c | ε

F →f | ε

G → Gg | H

H →h | ε

C →c

(1) : W = {A, C, D, F, G, H, S} (2) : P1 = { S →ADC | EFg

A →aA

D → FGH | b

E →a

F →f

G → Gg | H

H →h }

(3), (4) : G′ :

S → ADC | AD | AC | DC | A | D | C | EFg | Eg | ε A →aA | a C →c

E →a

D → FGH | FG | FH | GH | F | G | H | b F →f

G → Gg | g | H

H →h

10

Manipulating CFG

10.2 Eliminating unit production rules

A unit production rule is a rule of the form C → A, which generates a single nonterminal symbol. Unit productions rules in a CFG can be eliminated without affecting the language. For example, minimizing the number of ε -production rules in Example 1 in the previous section, we got the following grammar. G′ : S → CD | C | D | ε

C →A | c

D →B | d

A →a

B →b

Rules C → A and A → a can be reduced to a single rule C → a without affecting the language generated by the grammar. Hence, we can safely change the rules C → A | c to C → a | c. For the same reason, we can substitute S → a | c for the rules S → C and C → a | c to eliminate the unit production rule S → C. Finally, applying the same idea to the unit production rules S → C | D, we get the following grammar, which has no unit production rules. (Notice that A → a and B → b are removed because they are useless.) G1: S → CD | a | c | b | d | ε

C →a | c

D →b | d 11

Eliminating unit production rules

Manipulating CFG

Now, for the proof of the following theorem, we present an algorithm which given an arbitrary CFG G, systematically applies the idea that we have presented above and eliminates all unit production rules to construct a CFG G′ , without affecting the language. Theorem 10.2 Let G be an arbitrary CFG. We can construct a CFG G′ that generates L(G) with no unit production rules. Proof (Algorithm): Let G = (VT, VN, P, S). The following algorithm constructs a CFG G′ = (VT , VN , P′ , S), which generates L(G) with no unit production rules.

Today’s Quote

Break Time

The simple solution for disappointment depression: Get up and get moving. Physically move. Do. Act. Get going. - Peter McWilliams -

12

Eliminating Unit production rules

Manipulating CFG

Algorithm (eliminate unit production rules) ε .

Input: a CFG G = (VT, VN, P, S) // G has no ε -production rules except S → Output: CFG G′ = (VT , VN , P′ , S) // G′ has no unit production rules

// and L(G′ ) = L(G). // Let A, B ∈ VN and β ∈ ( VT ∪ VN )* . while (there is a unit production rule in P) { find a unit production rule A → B in P such that B has no unit production rules; for every B → β which is not unit production, change A → B to A → β ; } //end while P′ = P ; G′ = (VT , VN , P′ , S);

13

Manipulating CFG

Eliminating Unit production rules

This algorithm, going bottom-up, iteratively changes unit production rules to nonunit production rules until it sees no unit production rule. The following example would be enough for understanding how it works. (Notice that by definition the rules generating a terminal symbol (e.g., A → a ) are not unit production rules.) G : S → CD | C | D | ε A →a

C →A | c

B → bB | b

1.

C →A | c ⇒ C →a | c

2.

S → CD | C | D | ε

E →F D →B | d

F →E ⇒ D → bB | b | d

⇒ S → CD | a | c | bB | b | d | ε

G' : S → CD | a | c | bB | b | d | ε A →a

D →B | d

B → bB | b

C →a | c

E →F

D → bB | b | d F →E

Notice that the algorithm fail to eliminate cyclic unit production rules. For example, see the rules involved with E and F in G' above. Together with A, these symbols are useless for generating the language. We will shortly presents an algorithm eliminating useless symbols in a CFG. 14

Manipulating CFG

10.3 Eliminating Useless Symbols from a CFG Manipulating a CFG may induce useless symbols (and their rules), as we saw in the previous section. The following grammar has two typical examples of useless symbols, B, C, D, and E.

G:

S →AE | A | B C →B

A →aA | ε D → Db | b

B →C E →Ec

Symbol D is useless because no sentential forms (i.e., strings consisting of terminal and nonterminal symbols) containing D are derivable starting with S. Although it is possible to derive a sentential form containing E starting with S, this symbol is also useless because no terminal strings can be generated starting with it. Symbols B and C are involved in a cyclic unit production rules, they are useless. Therefore B, C, D, and E and the rules involving these nonterminal symbols can be safely eliminated to get the following simple CFG G′ .

G′ : S → A

A → aA | ε

15

Eliminating useless symbols

Manipulating CFG

In the previous example we observed the following; in a CFG G = (VT, VN, P, S), a nonterminal symbol X ∈VN is useful if it satisfies the two conditions (1) and (2) below. (Recall that by α ⇒* β we denote the derivation of β , starting with α , in zero or more steps of applying a rule at a time.) (1) X ⇒* w, where w ∈VT* (2) S ⇒* α Xβ , where α , β ∈(VT ∪ VN)* These two conditions are illustrated in the figure below, i.e., a nonterminal symbol X is useful, if (1) a terminal string w (or ε ) is derivable starting with X, and (2) a sentential form including X is derivable starting with S,.

S ⇒ (2)

*

α

X

β

a sentential form

⇒* w (1) 16

Eliminating useless symbols

Manipulating CFG

Now we present an algorithm for eliminating useless symbols in a CFG. The algorithm is presented in two parts by the following two lemmas. Lemma 1 and Lemma 2 present an algorithm for eliminating all symbols that do not satisfy the conditions (1) and (3), respectively. Lemma 1. Given a CFG G = (VT , VN , P, S), it is possible to construct a CFG G′ = (VT ,V′ N , P′ , S) that satisfies the following conditions. (i) L(G) = L(G′ ) (ii) For every X ∈ V′ N , X ⇒* w, where w ∈ (VT)*

Proof (algorithm 1). Let A be a nonterminal symbol. We compute V′ N and P′ of grammar G′ with the following algorithm. (Notice that this algorithm uses a similar technique to one which we used for minimizing the number of ε -production rules.)

17

Eliminating useless symbols

Manipulating CFG

Algorithm for constructing V′ N and P′ // Collect all nonterminal symbols directly generating a terminal string. W = {A | A → w ∈ P, w ∈ (VT)* }; // Collect all nonterminal symbols which can derive a terminal string. do { W′ = W; W = W′ ∪{A | A → α ∈ P and α ∈ ( VT ∪ W′ )*}; }while ( W != W′ ) V′ N = W; P′ = {A → α | A → α ∈ P and α ∈(V′ N ∪ VT)*};

18

Eliminating useless symbols

Manipulating CFG

Lemma 2. Given a CFG G = (VT , VN , P, S), it is possible to construct a CFG G′ = (V′ T ,V′ N , P′ , S) that satisfies the following conditions. (1) L(G) = L(G′ ) (2) For every symbol X ∈ V′ T ∪ V′ N , it is possible to derive a sentential form starting with S, i.e., S ⇒* α Xβ , where α , β ∈ (V′ T ∪ V′ N)* Proof (algorithm 2). Starting with empty sets V′ T and V′ N , the algorithm progressively builds them up as follows. Put the start symbol S in V′ N. Suppose that A is a nonterminal symbol that has just been put in V′ N. Then for every rule A → β and every symbol X that appears in β , if X is a nonterminal symbol, put it in V′ N. Otherwise, if it is a terminal symbol, put it in V′ T. The algorithm repeats this process till no more nonterminal symbols added into V′ N. Then the algorithm constructs P′ by collecting all the rules in P that uses only the symbols in V′ T ∪ V′ N.

19

Eliminating useless symbols

Manipulating CFG

Algorithm (Lemma 2) Input: G = (VT , VN , P, S) Output: G′ = (V′ T ,V′ N , P′ , S) // G′ satisfies the two conditions of the lemma. Let V′ T = V′ N = V = φ ; do { V′ N = V;

V = V ∪ { S };

// initialize

// Iteratively build up V′ T and V′ N

V = V ∪ { B | A ∈ V′ N , A → β ∈ P, and β contains B ∈ VN }; V′ T = V′ T ∪ { a | A ∈ V′ N , A → β ∈ P, and β contains a ∈ VT }; } while (V′ N != V ) P′ = {A → β | A → β ∈ P, A ∈ V′ N , β ∈ (V′ T ∪ V′ N)* }; G′ = (V′ T ,V′ N , P′ , S) ;

20

Eliminating useless symbols

Manipulating CFG

Theorem 10.3 Given a CFG G = (VT , VN , P, S), it is possible to construct a CFG G′ = (V′ T , V′ N , P′ , S) that satisfies the following conditions. (1) L(G) = L(G′ ) (2) For every X ∈ V′ N , X ⇒* (V′ T)* (3) For every X ∈ V′ T ∪ V′ N , S ⇒* α Xβ , where α , β ∈ (V′ N ∪ V′ T)* Proof. We construct such CFG G′ using the two algorithms presented in Lemmas 1 and 2, in that order.

Today’s Quote

Break Time

He who receives a benefit should never forget it; he who bestow should never remember it. - Pierre Charron -

21

Eliminating useless symbols

Manipulating CFG

Example 1. Eliminate all useless symbols in the following CFG. G:

S →AD | EFg

A →aGD

E → Ee

F → Ff | ε

D → FGd G → Gg | g

C →cCEc H → hH | h

Step 1: Apply the algorithm of Lemma 1: W = {F, G, H} ; W´ = W ; W = W´ ∪ {D}

// W = {D, F, G, H};

W´ = W ; W = W´ ∪ {A}

// W = {A, D, F, G, H};

W´ = W ; W = W´ ∪ {S}

// W = {A, D, F, G, H, S};

W´ = W ; W = W´ ∪ { } V´N = W

// W = {A, D, F, G, H, S}; // V´N = {A, D, F, G, H, S}

G1 :

S →AD G → Gg | g

A →aGD H → hH | h

D → FGd

F → Ff | f

22

Eliminating useless symbols G1: S →AD G → Gg | g

A →aGD H → hH | h

Manipulating CFG D → FGd

F → Ff | f

Step 2: Apply the algorithm of Lemma 2 to G1: 1. V′ T = V′ N = V = { }; 2. V = V ∪ {S};

V′ N = V;

3. V = V ∪ {A, D};

V′ T = V′ T ∪ { };

V′ N = V; 4. V = V ∪ {G, F} ; V′ N = V; 5. V′ N = V′ N ∪ {} ; V′ N = V;

// V′ N = {S, A, D},

// V′ N = {S} V′ T = { }

V′ T = V′ T ∪ {a, d}; // V′ N = {S, A, D, G, F}, V′ T = {a, d} V′ T = V′ T ∪ {g, f} = {a, d, g, f}; // V′ N = {S, A, D, G, F},

V′ T = {a, d, g, f}

23

Eliminating useless symbols

G1: S →AD G → Gg | g

A →aGD H → hH | h

Manipulating CFG

D → FGd

F → Ff | f

Apply the algorithm of Lemma 2 V′ N = {S, A, D, G, F}, V′ T = {a, d, g, f} Select the rules that contain only the symbols in V′ N ∪ V′ T Final result: G′ : S →AD

A →aGD

D → FGd

F → Ff | f

G → Gg | g

24

Eliminating useless symbols

Manipulating CFG

To eliminate useless symbols, we applied the algorithm of Lemma 1 followed by the algorithm of Lemma 2. If we apply the algorithm of Lemma 2 first, we may fail to eliminate all useless symbols. The following figure shows an example. G: S → AB | a

Apply the algorithm of Lemma 2

Apply the algorithm of Lemma 1 G1: S → a Apply the algorithm of Lemma 2 G′ : S → a

A →a

A →a

G1: S → AB | a

A →a Apply the algorithm of Lemma 1

G′ : S → a

A →a

25

Manipulating CFG

10.4 Normal Form of CFG We know that CFG rules have no restriction on their right side. There can be any string (of finite length) of terminal and/or nonterminal symbols. This “free form” of CFG rules makes it more complex to solve certain problems concerning context-free languages. It is often desirable to have the rules simplified on their form without affecting the language of the grammar. In this section we will study two of such forms, called Chomsky normal form and Greibach normal form, presented below. Let G = (VN, VT, P, S) be a CFG and let A, B, C∈VN, a ∈VT and α ∈ (VN)*. • If every rule of G has the form A → BC or A → a, then G is called a Chomsky normal form (CNF) grammar. • If every rule of G has the form A → aα , then G is called a Greibach normal form (GNF) grammar. Note that the definitions are only concerned with CFG’s whose language does not contain ε . 26

Manipulating CFG

Normal Form of CFG

Converting a CFG to CNF Given a CFG, we will show how to convert the grammar to CNF. The conversion is done for each rule. The following example would be enough to understand the idea. • Converting A → aBCDbE to a set of rules in CNF. A → A1B1

A1 → a

// and let B1 derive BCDbE as follows,

B1 → BC1

// and let C1 derive CDbE as follows,

C1 → CD1

// and let D1 derive DbE as follows,

D1 → DE1

// and let E1 derive bE,

E1 → F1E F1 → b

// and finally let F1 derive b.

* Subscripted symbols are nonterminal symbols newly introduced. Starting with A, the above set of CNF rules applied in the order, we can derive aBCDbE, which can be derived by applying the single rule A → aBCDbE.

27

Manipulating CFG

Normal Form of CFG Example 1. Convert the following CFG to CNF. (1) S → AaBCb

(2) A → abb

(3) B → aC

(4) C → aCb | ac

For each rule, we apply the idea that we have presented above.

(1) S → AA1

A1 → A2A3

A2 → a

(2) A → B1B2

B1→ a

B2 → B3B4

(3) B → C1C

C1 → a

(4) C → D1D2 | E1E2 D1 → a

A3 → BA4

D2 → CD3

A4 → CA5

B3 → b

B4 → b

D3 → b

E1 → a

A5 → b

E2 → c

We leave it for the reader to prove that the conversion does not affect the language of the grammar. 28

Normal Form of CFG

Manipulating CFG

Converting a CFG to GNF GNF: A → aα , A ∈ VN , a ∈VT, α ∈ (VN)*

The algorithm for converting a CFG to GNF is not simple, not to mention the proof of its correctness. We shall only present an example to show the basic idea. We need some terminology introduced before the algorithm. We call a rule frontrecursion, if its right side starts with the same nonterminal symbol as the one in the left side (e.g., A → AB). A front-nonterminal is a nonterminal symbol that is located at the left end of the right side of the rule, and a non-front terminal is a terminal symbol that is not located at the left end of the rule. The algorithm works in the following three phases. 1. Eliminate front-recursion 2. Eliminate front–nonterminal 3. Eliminate non-front terminal 29

Manipulating CFG

Normal Form of CFG GNF: A → aα , A ∈ VN , a ∈VT, α ∈

(VN)* The algorithm repeatedly applies phases 1 and 2 until it sees neither frontrecursions nor front-nonterminals. Then it applies Phase 3 to eliminate non-front terminals in the rules to transform them finally into GNF. Phase 1. Consider the following rules with a front-recursion. We introduce a new nonterminal (N in the example) and eliminate the front-recursion as follows. A → AB | CD

A → CDN | CD

N → BN | B

Notice that a front-recursion rule must accompany a non-front-recursion, for example A → CD in the above example. Otherwise, the rule with the front-recursive is useless and can be eliminated. In general, let A → β be a non-front-recursion rule. Then the front-recursion A → Aα can be eliminated as follows. A → Aα | β

A →β N | β

N →α N | α 30

Manipulating CFG

Normal Form of CFG

Phase 2. Find a rule with a front-nonterminal (B in the example below) such that every rule of B has a front-terminal. Convert the rule with a front-nonterminal into a rule having a front-terminal as follows.

A → BbC | aA

A → cDAbC | aEbC | aA B → cDA | aE

B → cDA | aE

....

.... Phase 3. Convert every non-front terminal to a new nonterminal as follows. A → cDAbC

A → cDANC

N →b

We can show that the above three phases of conversion do not affect the language of CFG G. (We omit the proof, which is challenging.)

31

Manipulating CFG

Normal Form of CFG

Example: Converting a CFG to GNF CFG: S → SA | BeA A → AS | a

Phase 1

S → BeAC | BeA

C → AC | A

A → aD | a

D → SD | S

B →b

B →b

Phase 2 S → beAC | beA

C → aDC | aC | aD | a

A → aD | a

D → SD | S

B →b Phase 2 S → beAC | beA

C → aDC | aC | aD | a

A → aD | a

D → beACD | beAD | beAC | beA

B →b 32

Manipulating CFG

Normal Form of CFG The result of phase 2 iteration: S → beAC | beA

C → aDC | aC | aD | a

A → aD | a

D → beACD | beAD | beAC | beA

B →b Phase 3 S → bEAC | bEA

C → aDC | aC | aD | a

A → aD | a

D → bEACD | bEAD | bEAC | bEA

B →b

E →e

Rule B → b, which is useless, can be eliminated using the algorithm presented in Section 10.3. 33

Manipulating CFG

Exercises

10.1 With the CFG G given below follow the steps (i) – (iii) below to construct a CFG such that L(G) = L(G’) with the smallest possible number of ε -production rules . (i) Find the set of nonterminal symbols that derive ε . You should also show the procedure that you took for you answer. (ii) Eliminate all ε -production rules from the grammar. (iii) Find CFG G’ using the result from step (ii) above. G:

S →ABCd | BEF

A →aA | ε

B →FGH | b

C →cC | ε

E →a | ε

F →f | ε

G →Gg | H

H →h | ε

10.2 Using the algorithm presented in Section 10.2, eliminate all unit production rules from the following CFG G. You should also show how you got your answer for the grammar.

G:

S → AB | A | B | ε D → bD | B | b

A →C | c

B →D | d

C →a

34

Manipulating CFG

Exercises

10.3 This problem is designed to eliminate all useless symbols from the CFG G given below in two steps (a) and (b). You should show the results from each step. (a) Using the algorithm presented in Lemma 1 in Section 10.3, construct a CFG G1 that satisfies the following conditions. (i) L(G) = L(G1) (ii) Every nonterminal symbol of G1 derives a terminal string. (b) Apply the algorithm of Lemma 2 in Section 10.3 and construct a CFG G G2 that satisfies the following conditions. (i) L(G) = L(G2), (ii) For every terminal or nonterminal symbol X of G2, it is possible to derive a sentential form containing X. G:

S →BA | CDg

B →aEA

A → DEd

C → Ce

E → Eg | g

F → hF | h

G →cGCc

I → cDEFab

D → Df | ε

10.4 Transform the following CFG into Chomsky normal form. S → abABCde

A → aAa

B → ba

C → cab

35