The nice thing about Chomsky normal form is that you can use it to determine if a particular CFG generates a particular string. Let's figure out if the grammar S --> AB | BC A --> BA | a B --> CC | b C --> AB | a can generate the string w = a b a b a What we will do is figure out what substrings of w we can generate from A, B, and C. Start with the substrings of length 1: A 01 23 45 B 12 34 C 01 23 45 What do I mean by this? ``01'' means the substring from index 0 inclusive to index 1 exclusive a b a b a 0 1 In other words, the first ``a''. Since ``A --> a'' is a rule, A can generate a, and there are three a's in w. Hence A 01 23 45 the rest is similarly generated from ``B --> b'' and ``C --> a'' A 01 23 45 B 12 34 C 01 23 45 Now we put together new substrings using the rules ``A --> BA'', ``B --> CC'', and ``C --> AB'': A 01 23 45 | 13 35 B 12 34 | C 01 23 45 | 02 24 O.K., where did the 13 come from for A? Well, ``A --> BA'' and BA could be the substring 12 from B followed by the substring 23 from A. We can put these together into 13 because they have 2 in common. Similarly 34 (B) and 45 (A) makes 35 for A. 01 (A) and 12 (B) makes 02 (AB) for C 23 (A) and 34 (B) makes 24 (AB) for C. To do the next round, we always have to use one of the substrings generated in the previous round. If we don't, then we will re-generate strings we generated in the previous round. So we need to use 13 or 35 from A or 02 or 23 from C. A 01 23 45 | 13 35 | B 12 34 | | 03 25 04 C 01 23 45 | 02 24 | 14 02 (C) and 23 (C) makes 03 (CC = B) 24 (C) and 45 (C) makes 24 (CC = B) 02 (C) and 24 (C) makes 04 (CC = B) 13 (A) and 34 (B) makes 14 (AB = C) A 01 23 45 | 13 35 | | 05 B 12 34 | | 03 25 04 | 15 C 01 23 45 | 02 24 | 14 | 03 (B) and 35 (A) makes 05 (BA = A) 04 (B) and 45 (A) also makes 05 (BA = A) 14 (C) and 45 (C) makes 15 (CC = B) A 01 23 45 | 13 35 | | 05 | B 12 34 | | 03 25 04 | 15 | C 01 23 45 | 02 24 | 14 | | 05 01 (A) and 15 (B) generates 05 (AB = C) The next round generates no new substrings, and so we are done. Finally, we need S to generate 05, which is the whole string ababa. 01 (A) and 15 (B) generates 05 (AB = S) 04 (B) and 45 (C) also generates 05 (BC = S) So the answer is yes, S generates w.