Markov dövrü

Məhdudlaşdırılmış Markov alqoritmi aşağıdakı qaydalar ardıcıllığından ibarətdir:

s_1s_2...s_N → d_1d_2..d_N,

burada s_i və d_i hərfləri əlifbanın A, B, C simvollarına aiddir. s_1s_2...s_N ardıcıllığı qaydanın sol hissəsi, d_1d_2..d_N isə sağ hissəsi adlanır.

Alqoritm böyük latın hərflərindən (A, B, C) ibarət verilmiş mətn üzərində belə işləyir: qaydalar birincidən başlayaraq ardıcıllıqla yoxlanılır. Əgər qaydanın sol hissəsi mətnin içərisində tapılırsa, həmin hissənin ən sol tapılan variantı qaydanın sağ hissəsi ilə əvəzlənir və alqoritm birinci qaydadan yenidən başlayır. Əgər heç bir qayda tətbiq oluna bilmirsə, alqoritm dayanır.

Alqoritmin iki mümkün nəticəsi var: ya o, dayanır, ya da müəyyən bir periodla sonsuz dövrəyə daxil olur. İlkin sətir və Markov alqoritmi qaydaları verilibsə, "döngədənkənar" addımların (döngü başlamadan əvvəl atılan addımların) və döngünün öz uzunluğunun sayını müəyyənləşdirin. Əgər alqoritm tamamlanırsa, döngü uzunluğu sıfır sayılır və bütün atılan addımlar döngüdənkənar hesab olunur.