Figure 1

Illustration of the minimum CFG for a string “abcabcab” In the minimum CFG, the substring “abc” is generated from a nonterminal symbol A _abc . Then, z _abc = 1, x_1,3 = 1, and x_4,6 = 1. To generate “abcabc”, that is, x_1,6 = 1, at least one variable of y_1,k,6 (k = 1,⋯,5) must be 1, that is, the substring s_1,6 must be divided into s_1,k and s _{k +1,6}. Here, y_1,3,6 = 1 because x_1,3 = x_4,6 = 1. Then, the production rule A _abcabc → A _abc A _abc appears.