Qatlama

Bill ardıcıllıqla böyük latın hərflərindən (A–Z) ibarət olan ardıcıllıqları təkrarlanan altardıcıllıqları qatlamaq vasitəsilə sıx şəkildə təsvir etməyə çalışır. Məsələn, AAAAAAAAAABABABCCD ardıcıllığını ifadə etməyin bir üsulu 10(A)2(BA)B2(C)D-dir. O, simvolların qatlanmış ardıcıllıqlarını və onların uyğun şəkildə açılma çevrilməsini rəsmi olaraq aşağıdakı kimi müəyyənləşdirir:

• A–Z hərflərindən birini tək halda ehtiva edən ardıcıllıq qatlanmış ardıcıllıq hesab olunur. Belə bir ardıcıllığın açılması nəticəsində eyni simvol əldə edilir.

• Əgər S və Q qatlanmış ardıcıllıqlardırsa, onda SQ də qatlanmış ardıcıllıqdır. S-in açılması ilə S', Q-nun açılması ilə Q' alınırsa, SQ ardıcıllığının açılması nəticəsində S'Q' əldə olunur.

• Əgər S qatlanmış ardıcıllıqdırsa, onda X(S) də qatlanmış ardıcıllıqdır, burada X $1$-dən böyük olan tam ədədin onluq şəkildə ifadəsidir. Əgər S açıldıqda S' alınırsa, X(S) açıldıqda S' ardıcıllığı X dəfə təkrarlanır.

Bu tərifə əsasən, istənilən qatlanmış ardıcıllığın açılması sadədir. Lakin Bill daha çox əks çevrilmə ilə maraqlanır. O, verilmiş ardıcıllığı elə qatlamaq istəyir ki, nəticədə alınan qatlanmış ardıcıllığın uzunluğu mümkün olan ən az simvoldan ibarət olsun.